All possible heaps
How many distinct (not necessarily binary) min-heaps can be constructed from the nodes with keys ?
Give the answer modulo .
Note :
Let be two heaps:
The answer is 44455173.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
\textbf{Method 1. A little bit ugly.} \\ \textit{The idea: take \$1\$ as root and count how many different heaps I can make} \\ \textit{from a partition of \$n-1\$ nodes remaining.} \\ \text{Let \$f(n)\$ be the number of min-heaps with \$n\$ nodes and}\\ \text{\$g(n,k)\$ the number of min-heaps from all partitions of \$n\$ nodes in \$k\$ subsets.}\\ f(n)=\displaystyle\sum_{k=1}^{n-1}g(n-1,k) \\ \textit{The idea: once I picked the first element, I can pick the remainings \$h\$ in \${n-1} \choose {h}\$ ways,} \\ \textit{make \$f(h+1)\$ heaps from them and now I have the remaining \$n-h-1\$ nodes.} \\ g(n,k)= \begin{cases} 1 & if \; {n=0} \land {k=0} \\ 0 & if \; {n \lt k} \lor {k=0} \\ \displaystyle\sum_{h=0}^{n-1} {{n-1}\choose{h}}f(h+1)g(n-h-1,k-1) & otherwise \end{cases} \\ \\ \textbf{Method 2. More elegant.} \\ \textit{The idea: once I have all heaps from \$n-1\$ nodes I can add the node \$n\$ under the others.} \\ f(n)= \begin{cases} 1 & if \; n=1 \\ (n-1)f(n-1) & otherwise \end{cases} \\
\text{The answer is \${f(999999)} \mod {10^9+7} = \boxed{44455173}\$ } \\
EDIT. I noticed now that $f(n)=(n-1)!$, nice coincidence: can anyone explain why? :)