Proving sums of multinomial coefficients If m and n are positive integers, how do I prove:
$$\sum_{k_1+\ldots+k_m=n}\binom{n}{k_1,\ldots,k_m}=m^n\;.$$
 A: This is the argument by Jack D'Aurizio spelled out. Use the multinomial theorem
$$
(x_{1} + \dots + x_{m})^{n}
=
\sum_{k_1 + \dots + k_{m} = n} \binom{n}{k_1, k_2, \dots, k_{m}} x_{1}^{k_{1}} \cdots x_{m}^{k_{m}}
$$
and set all $x_{1} = 1$.
A: The LHS is the number of ways to partion n entities into m sets that can be done by asking individiual element one by one where it wants to go from a list of m subsets that we can form beforehand. Thus ways now would be m for first element, sm for second element and so on. So total ways would be $\prod_1^nm=m^n$.
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
If we don't know the Multinomial Theorem we can do something like
\begin{align}&\color{#66f}{\large%
\sum_{k_{1} + k_{2} + \cdots + k_{m} = n}\ \frac{n!}{k_{1}!\,k_{2}!\ldots k_{m}!}}
\\[5mm]&=\sum_{k_{j}\ \in\ \braces{0,1,2,\ldots} \atop j=1,2,\ldots,m}
\,\,\,\,\,\,\,\,\,
\frac{n!}{k_{1}!\,k_{2}!\ldots k_{m}!}
\oint_{\verts{z}=1^{-}}\frac{1}{z^{-k_{1} - k_{2} - \cdots - k_{m} + n + 1}}\,\,
\,{\dd z \over 2\pi\ic}
\\[5mm]&=n!\oint_{\verts{z}=1^{-}}\ \frac{1}{z^{n + 1}}
\pars{\sum_{k=0}^{\infty}\frac{z^{k}}{k!}}^{m}\,{\dd z \over 2\pi\ic}
=n!\oint_{\verts{z}=1^{-}}\ \frac{\expo{mz}}{z^{n + 1}}\,{\dd z \over 2\pi\ic}
=n!\sum_{k=0}^{\infty}\frac{m^{k}}{k!}\
\overbrace{\oint_{\verts{z}=1^{-}}\ \frac{1}{z^{n - k + 1}}\,{\dd z \over 2\pi\ic}}
^{\dsc{\delta_{k,n}}}
\\[5mm]&=n!\,\frac{m^{n}}{n!}=\color{#66f}{\large m^{n}}
\end{align}
