Introduction to Alogrithm

Question

Number of max heap possible with n distinct keys.

Answer 1

Number of max/min heaps possible with n distinct keys is given by the recurrence relation
$f(n) = {n-1 \choose l} * f(l) * f(r)$

where $l$ is the number of nodes in the left sub-tree.

Note: $f(1) = 1$ and $f(2) = 1$