Suite et arbre

Bonjour je cherche à obtenir le nombre de nœuds d'un arbre à la hauteur n se construisant comme ceci :

on dispose d'un nombre (supérieur à n) d’éléments que l'on cherche à apparier (à mettre ensemble) dans un arbre.
On place (1) à la racine. Si (1) peut s'apparier avec (2) (selon une relation d'équivalence dont on n'a pas besoin ici) alors (1) on aura 2 nœuds fils : un nœud F1 qui contient (1,2) et l'autre F2 qui contient (2).
On continue pour le nœud de gauche F1. F1 possède 2 fils : un nœud qui contient (1,2,3), et un nœud qui contient seulement (3). En effet, si (3) ne s'apparie pas à (1,2) il ne s'apparie ni à (1), ni à (2) selon la relation d'équivalence.
F2 lui possède 3 fils : soit 3 s'apparie à (1) et on obtient (1,3), soit il s'apparie à (2) et on obtient (2,3) soit il ne ne s'apparie à rien et on n'obtient seulement (3). Évidement lors du parcours de l'arbre, celui ci sera élagué la relation étant transitive, si l'on arrive sur (1,3) il est inutile d'aller explorer (2,3), (1) n'étant pas apparié à (2). Mais cela n'est pas le problème.
a la hauteur 3 on a donc 2+3=5 nœuds. Je n'arrive seulement pas à généraliser le problème pour n. Il y a bien sûr dans la formule une somme des k parmi n mais il manque un quelque chose que je n'arrive pas obtenir.
Je vous remercie!