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

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:

lub 4 2 3 1:

data-structures combinatorics heaps

— Pratik Deoghare
źródło

Odpowiedzi:

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, ...

$n$ $n$ $n_1,n_2$ $n_1+n_2=n-1$ ${n-1 \choose n_1}$

za (n) = (\binom{n - 1}{n_{1}}) za (n_{1}) za (n_{2)}) .

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

— A.Schulz
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.