Wie viele verschiedene Max-Heaps gibt es für eine Liste von n ganzen Zahlen?

Wie viele verschiedene Max-Heaps gibt es für eine Liste von ganzen Zahlen?$n$

Beispiel: Liste [1, 2, 3, 4]

Der Max-Heap kann entweder sein 4 3 2 1:

    4
   / \
  3   2
 /
1

oder 4 2 3 1:

    4 
   / \
  2   3 
 /
1

Ich habe keine geschlossene Form gefunden, aber gemäß diesem Eintrag in der Online-Enzyklopädie der ganzzahligen Sequenzen beginnt die Sequenz mit

1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ...

Eine nicht so schöne Rekursion finden Sie in der OEIS-Datenbank. Grundsätzlich ist die Idee wie folgt. Die Wurzel eines - ary heap ist immer das Maximum. Die beiden Teilbäume, die an der Wurzel hängen, sind wieder Maxheaps. Ihre Größe hängt von und ist ein bisschen mühsam, um die Größen (siehe OEIS-Eintrag) zu berechnen , eindeutig . Wir können jetzt auswählen, welche Elemente zum linken und welche zum rechten Haufen gehen. Es gibt Möglichkeiten, die Elemente zu verteilen. Dies gibt die Wiederholungn n 1 , n 2 n 1 + n 2 = n - $n$$n$$n_1,n_2$$n_1+n_2=n-1$${n-1 \choose n_1}$

$$a(n)= {n-1 \choose n_1} a(n_1)a(n_2).$$