A combinatorial identity involving $m^n$. 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. 
 A: 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.$$
A: 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}$.
