Nombre de tas possibles sur $ {1,…, 2 ^ H-1 } $

Question

Laisser $ C_h $ être le nombre de tas possibles pour l'ensemble des clés $ {1, ..., 2 ^ H-1 } $. Déterminer une relation de récidive pour $ C_h $ via la méthode de substitution et prouver.

Définition

Un arbre binaire est commandé Si la clé à chaque nœud est plus petite que les clés de ses enfants.

Un arbre binaire ordonné de hauteur $ h $ est appelé un tas Si l'arbre induit par tous les niveaux, sauf le dernier, est un arbre binaire complet et que toutes les feuilles sont "autant à gauche que possible".

Donc ce que j'ai trouvé, c'est cette expression:

$$ c_h = displayStyle prod_ {n = 1} ^ {h} (2 ^ {i-1})! $$

L'intuition derrière est qu'avec chaque incrément de $1$ de $ h $ Les gains d'arbre $2$ Des temps plus de feuilles qu'auparavant et les possibilités de commander ces feuilles peuvent être déterminées via l'opération factorielle. Cela a-t-il du sens?