Numero di possibili cumuli su $ {1,…, 2^H-1 } $

Question

Permettere $ C_h $ essere il numero di possibili cumuli per l'insieme di chiavi $ {1, ..., 2^H-1 } $. Determinare una relazione di ricorrenza per $ C_h $ tramite il metodo di sostituzione e dimostrarlo.

Definizione

Un albero binario è ordinato Se la chiave in ogni nodo è più piccola delle chiavi dei suoi figli.

Un albero binario ordinato di altezza $ H $ è chiamato a mucchio Se l'albero indotto da tutti i livelli tranne l'ultimo è un albero binario completo e tutte le foglie sono "il più possibile a sinistra".

Quindi quello che ho escogitato è questa espressione:

$$ c_h = DisplayStyle Prod_ {n = 1}^{H} (2^{i-1})! $$

L'intuizione dietro di esso è che con ogni incremento di $1$ di $ H $ l'albero guadagna $2$ volte più foglie di prima e le possibilità di ordinare queste foglie possono essere determinate attraverso l'operazione fattoriale. Ha senso?