patternMajor
How many different max-heaps exist for a list of n integers?
Viewed 0 times
howexistintegersdifferentmaxformanylistheaps
Problem
How many different max-heaps exist for a list of $n$ integers?
Example: list
The max-heap can be either
or
Example: list
[1, 2, 3, 4]The max-heap can be either
4 3 2 1:4
/ \
3 2
/
1or
4 2 3 1:4
/ \
2 3
/
1Solution
I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with
1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ...
You can find a not-so-nice recursion in the OEIS database. Basically the idea is as follows. The root of an $n$-ary heap is always the maximum. The two subtrees hanging off the root are again maxheaps. Their size depends on $n$, is a bit tedious to compute the sizes $n_1,n_2$ (see the OEIS entry), clearly $n_1+n_2=n-1$. We can now pick, which elements go to the left heap and which go to the right heap. There are ${n-1 \choose n_1}$ ways how to distribute the elements. This gives the recurrence
$$ a(n)= {n-1 \choose n_1} a(n_1)a(n_2).$$
1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ...
You can find a not-so-nice recursion in the OEIS database. Basically the idea is as follows. The root of an $n$-ary heap is always the maximum. The two subtrees hanging off the root are again maxheaps. Their size depends on $n$, is a bit tedious to compute the sizes $n_1,n_2$ (see the OEIS entry), clearly $n_1+n_2=n-1$. We can now pick, which elements go to the left heap and which go to the right heap. There are ${n-1 \choose n_1}$ ways how to distribute the elements. This gives the recurrence
$$ a(n)= {n-1 \choose n_1} a(n_1)a(n_2).$$
Context
StackExchange Computer Science Q#6456, answer score: 27
Revisions (0)
No revisions yet.