# 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.

• Is this question related to math.stackexchange.com/questions/2665048/…? – Robert Z Feb 27 '18 at 17:26
• I recommend highlighting the connection to the earlier Question by including a link in the body of this Question, and ideally explaining the connection in more detail than given here. – hardmath Feb 28 '18 at 1:37
• @hardmath Done. Besides the previous question is updated. – user Feb 28 '18 at 10:17

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}$.

• I think that the factorial sign should be removed from multinomial coefficients. – Robert Z Feb 28 '18 at 7:43
• @RobertZ: you're absolutely right. – robjohn Feb 28 '18 at 9:03
• It is of course clear that the LHS of the expression (2) in question is the sum of products of two multinomials. The only problem is to demonstrate the equivalence of both sums. It seems that some transformation is missed which would explain a connection between "left" and "right" $k's$. Besides the term "sorted lower indices" being applied to a multinomial seems to be misleading, as its value does not depend on the order of the indices, does it? – user Feb 28 '18 at 10:36
• @user: Of course the order of the lower indices does not matter; that is why we can multiply one multinomial coefficient with sorted lower indices by the number of permutations of the lower indices to get the total of all unsorted orders of the lower indices. For example: $$\underbrace{\binom{2}{0,1,1}}_{\text{sorted lower indices}}\ \ \underbrace{\ \binom{3}{1,2}\ }_{\substack{\text{number of permutations}\\\text{of lower indices}}}=\underbrace{\binom{2}{0,1,1}+\binom{2}{1,0,1}+\binom{2}{1,1,0}}_{\text{unsorted lower indices}}$$ – robjohn Feb 28 '18 at 14:44
• It looks very nice and understandable. However in this example the indices in the leftmost multinomial and in the multinomials on the RHS are the same. In the final expression you gave they seem however to be different. They are certainly not the same $k's$ as in the LHS. It would be very helpful if you clarify the point, especially the fact that there are exactly $m$ RHS-$k$'s and they run over all possible values allowed by the restrictions $k_i\ge0$ and $\sum_i k_i=n$. – user Feb 28 '18 at 15:03

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.$$

• Could you add some words to clarify the expression for $k_i$? – user Feb 27 '18 at 17:43
• I am quite sure that the identity is valid independent from condition $k_i\ne k_j$. – user Feb 27 '18 at 17:46
• @user Yes you are correct. Any further doubt? – Robert Z Feb 27 '18 at 18:12
• I have no doubts that your approach is correct, but have some problems with understanding what kind of functions counts a single term of the sum and why it is a product of the multinomials. – user Feb 27 '18 at 20:00
• I believe it can be useful if you add this example to the answer and explain its connection to the product of multinomials. – user Feb 27 '18 at 20:17