Ile różnych maksymalnych stert istnieje dla listy n liczb całkowitych?

19

Ile różnych maksymalnych stert istnieje dla listy n liczb całkowitych?

Przykład: lista [1, 2, 3, 4]

Maksymalna kupa może być 4 3 2 1:

    4
   / \
  3   2
 /
1

lub 4 2 3 1:

    4 
   / \
  2   3 
 /
1
Pratik Deoghare
źródło

Odpowiedzi:

22

Nie znalazłem zamkniętego formularza, ale zgodnie z tym wpisem w Online Encyclopedia of Integer Sequences sekwencja zaczyna się od

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

nnn1,n2)n1+n2)=n-1(n-1n1)

za(n)=(n-1n1)za(n1)za(n2)).
A.Schulz
źródło