A combinatorial identity involving $m^n$.

Question

While solving a combinatorial problem I came across an interesting identity.

Let $\mathbf{k}=\{k_0,k_1,k_2\dots\} $ be an ordered set of non-negative integer numbers and let ${\cal K}_m^n$ be a set of $\mathbf{k}$ such that: $$ \mathbf{k}\in {\cal K}_m^n\Leftrightarrow\sum_{i\ge0}k_i=m,\sum_{i\ge0}i k_i=n. \tag{1} $$

Then the following summation identity applies: $$ \sum_{\mathbf{k}\in {\cal K}_m^n}\frac{m!n!}{\displaystyle\prod_{i\ge0}(i!)^{k_i}k_i!}=m^n.\tag{2} $$

Is there a simple way to prove it? Combinatorial and non-combinatorial proofs are of equal interest.

The question is related to the previous one, where the combinatorial meaning of the problem and cardinality of the set ${\cal K}_m^n$ is clarified.

Answer 1

This is simply the multinomial theorem after sorting the lower indices: $$ \begin{align} \sum_{\substack{\sum\limits_{j\ge0}k_j=m\\\sum\limits_{j\ge0}jk_j=n}}\overbrace{\binom{n}{\underbrace{0,0,\dots}_{k_0\text{times}},\,\underbrace{1,1,\dots}_{k_1\text{times}},\,\dots}}^{\text{lower indices sorted}}\overbrace{\binom{m}{k_0,\,k_1,\,\cdots}}^{\substack{\text{number of ways}\\\text{to arrange the}\\\text{lower indices}\\\text{ in the preceding}\\\text{multinomial}}} &=\sum_{\sum\limits_{j=1}^ma_j=n}\overbrace{\binom{n}{a_1,\,a_2,\,\cdots,\, a_m}}^{\text{lower indices unsorted}}1^{a_1+a_2+\cdots+a_m}\\ &=(\overbrace{1+1+\cdots+1}^{\text{$m$ copies}})^n \end{align} $$ That is, since the order of the $a_j$'s doesn't matter in $\binom{n}{a_1,\,a_2,\,\cdots,\, a_m}$, on the left side, we sort the $a_j$'s into $k_0$ $0$'s, $k_1$ $1$'s, etc. and compute that multinomial coefficient and then multiply by the number of equal multinomials on the right (from rearrangements of the $a_j$'s) which is $\binom{m}{k_0,\,k_1,\,\cdots}$.

Answer 2

A combinatorial proof. The integer $$\frac{m!n!}{\displaystyle\prod_{i\ge0}(i!)^{k_i}k_i!}=\binom{m}{k_0,k_1,\dots}\cdot \binom{n}{\underbrace{0,\dots,0}_{k_0},\underbrace{1,\dots,1}_{k_1},\dots,\underbrace{i,\dots,i}_{k_i},\dots}$$ counts the number of functions $f$ from $N:=\{1,2,\dots,n\}$ to $M:=\{1,2,\dots,m\}$ such that for any non negative integer $i$, $$k_i=\left|\left\{j\in M:|f^{-1}(j)|=i\right\}\right|.$$ where $|S|$ denotes the cardinality of the set $S$.

Finally note that $m^n$ is the total number of functions from $N$ to $M$. Hence $$\sum_{\mathbf{k}\in {\cal K}_m^n} \frac{m!n!}{\displaystyle\prod_{i\ge0}(i!)^{k_i}k_i!}=m^n.$$

For example, for $m=n=3$, ${\cal K}_3^3=\{(2,0,0,1),(1,1,1), (0,3)\}$ and $$\frac{3!\cdot 3!}{(0!)^2(1!)^0(2!)^0(3!)^1 2! 0! 0! 1!}+\frac{3!\cdot 3!}{(0!)^1(1!)^1(2!)^1 1! 1! 1!} +\frac{3!\cdot 3!}{(0!)^0(1!)^30! 3!}=3+18+6=3^3.$$