# How many different max-heaps exist for a list of n integers?

How many different max-heaps exist for a list of $$n$$ integers?

Example: list [1, 2, 3, 4]

The max-heap can be either 4 3 2 1:

4
/ \
3   2
/
1

or 4 2 3 1:

4
/ \
2   3
/
1

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).$$