Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)
Stirling's formula shows that
$$
\binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}},
$$
where $H(p)$ is the binary entropy function:
$$
H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}.
$$
In particular, this shows that for $k \geq 2$,
$$
\binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\pi n}}.
$$
Therefore
$$
\log \binom{kn}{n} \geq n\log k - O(\log n),
$$
where the big O doesn't depend on $k$. Summing this for $k=2,\ldots,m$, we deduce
$$
h \geq n \log m! - O(m\log n) \geq nm \log m - O(nm),
$$
using Stirling's formula again.