How many different heaps are there for an array of 6 entries

How many different heaps are there for an array of 6 entries? 12 entries? 18 entries? Explain your answer.

Solution

From Recurrence equation:
T(n) = T(k) * T(n-k-1) * (n-1)Ck where k = number of nodes on left

Max-Height(left-subtree) - Max-Height(right-subtree) <= 1

number of leafs in a heap of size n = Math.floor((n+1)/2)

Therefore,

T(6) = 5C3 * T(3) * T(2) = 20

T(12) = 11C7 * T(7) * T(4) = 79200

T(18) = 17C9 * T(9) * T(8) = 4574169600