# Application of multinominal theorem for a tricky sum

In our lecture notes, it says that one can compute the sum $$\sum_{\substack{k_1,k_2,\dots,k_M\geq0:\\k_1+\dots+k_M=N}} \binom{N}{k_1,\dots,k_M} \left(\binom{k_1}{2} + \dots + \binom{k_M}{2} \right)^2$$ by using $$\binom{k}{2}^2 = \frac{k^{\underline{4}}}{4} + k^{\underline{3}} + \frac{k^{\underline{2}}}{2},$$ where we used the falling factorials $$n^{\underline{k}} := n (n-1) \cdots (n-k+1).$$

Since this remark is just after the multinomial theorem was stated, that is $$\sum_{\substack{k_1,k_2,\dots,k_M\geq0:\\k_1+\dots+k_M=N}} \binom{N}{k_1,\dots,k_M} x_1^{k_1} x_2^{k_2}\dots x_M^{k_M} = (x_1+x_2+\dots +x_M)^N,\qquad \binom{N}{k_1,\dots,k_M} = \frac{N!}{k_1!\cdots k_M!},$$ I guess that one should use it on this problem, but I do not know how to get there, since using the binomial theorem on the $$(\ldots)^2$$-term does not give me something of the form $$x_1^{k_1} x_2^{k_2}\cdots x_M^{k_M}$$ or I am missing something. Does anyone have any idea, how one could start?

I found a solution, maybe someone will need it in the future: \begin{align*} &\sum_{\substack{k_1,k_2,\dots,k_M\geq0:\\k_1+\dots+k_M=N}} \binom{N}{k_1,\dots,k_M} \left(\binom{k_1}{2} + \dots + \binom{k_M}{2} \right)^2 \\ &= \sum_{\substack{k_1,k_2,\dots,k_M\geq0:\\k_1+\dots+k_M=N}} \binom{N}{k_1,\dots,k_M} \left(\sum_{i=1}^M \binom{k_i}{2}^2 + \sum_{\substack{j,m=1\\j\neq m}}^M\binom{k_j}{2}\binom{k_m}{2} \right)\\ &= \sum_{\substack{k_1,k_2,\dots,k_M\geq0:\\k_1+\dots+k_M=N}} \frac{N!}{k_1!\cdots k_M!}\left(\sum_{i=1}^M \left(\frac{k_i^{\underline{4}}}{4} + k_i^{\underline{3}} + \frac{k_i^{\underline{2}}}{2}\right) + \sum_{\substack{j,m=1\\j\neq m}}^M \frac{k_j^{\underline{2}}}{2} \frac{k_m^{\underline{2}}}{2}\right)\\ &= \sum_{\substack{k_1,k_2,\dots,k_M\geq0:\\k_1+\dots+k_M=N}} \sum_{i=1}^M\left( \frac{1}{4}\frac{N!}{\prod_{\substack{l=1\\l\neq i}}^M k_l!}\frac{1}{(k_i-4)!} + \frac{N!}{\prod_{\substack{l=1\\l\neq i}}^M k_l!} \frac{1}{(k_i-3)!} + \frac{1}{2}\frac{N!}{\prod_{\substack{l=1\\l\neq i}}^M k_l!} \frac{1}{(k_i-2)!}\right) \\ &\qquad+ \sum_{\substack{j,m=1\\j\neq m}}^M \left(\frac{1}{4}\frac{N!}{\prod_{\substack{l=1\\l\neq j,m}}^M k_l!}\frac{1}{(k_j-2)!} \frac{1}{(k_m-2)!}\right)\\ &= \sum_{\substack{k_1,k_2,\dots,k_M\geq0:\\k_1+\dots+k_M=N}} \sum_{i=1}^M\Bigg( \frac{N^{\underline{4}}}{4} \binom{N-4}{\prod_{\substack{l=1\\l\neq i}}^M k_l,k_i-4} + N^{\underline{3}} \binom{N-3}{\prod_{\substack{l=1\\l\neq i}}^M k_l,k_i-3} \\ &\qquad+ \frac{N^{\underline{2}}}{2}\binom{N-2}{\prod_{\substack{l=1\\l\neq i}}^M k_l,k_i-2}\Bigg) + \sum_{\substack{j,m=1\\j\neq m}}^M \frac{N^{\underline{4}}}{4} \binom{N-4}{\prod_{\substack{l=1\\l\neq j,m}}^M k_l,k_j-2, k_m-2}\\ &= M \left(\frac{N^{\underline{4}}}{4} M^{N-4} + N^{\underline{3}} M^{N-3} + \frac{N^{\underline{2}}}{2} M^{N-2}\right) + M(M-1) \frac{N^{\underline{4}}}{4} M^{N-4}\\ &= M^{N-2}N^{\underline{3}} + \frac{M^{N-1}N^{\underline{2}}}{2} + \frac{M^{N-2}N^{\underline{4}}}{4}, \end{align*} where one gets the second to last equation by multinomial theorem and counting the summands.