¿Cuántos max-heaps diferentes existen para una lista de n enteros?

19

¿Cuántos max-heaps diferentes existen para una lista de n enteros?

Ejemplo: lista [1, 2, 3, 4]

El max-heap puede ser 4 3 2 1:

    4
   / \
  3   2
 /
1

o 4 2 3 1:

    4 
   / \
  2   3 
 /
1
Pratik Deoghare
fuente

Respuestas:

22

No encontré una forma cerrada, pero de acuerdo con esta entrada en la Enciclopedia en línea de secuencias enteras, la secuencia comienza con

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

nnn1,n2n1+n2=n1(n1n1)

a(n)=(n1n1)a(n1)a(n2).
A.Schulz
fuente