How to find and prove generalization of one of the formulas with binomial coefficients?

Question

There is a well-known formula $\binom{n}{k} + \binom{n}{k + 1} = \binom{n+1}{k+1}$. How to formulate and prove its generalization for multinomial coefficients?

Answer 1

Multinomial coefficient could be defined as $\binom{n}{a_1, \ldots, a_m} = {n! \over a_1! \cdot \ldots a_n!}$ or $\binom{n}{a_1, \ldots, a_n} = \binom{n}{a_1} \binom{n-a_1}{a_2} \binom{n-a_1-a_2}{a_3} \ldots \binom{a_{m-1}+a_m}{a_m}$. But the more convenient definition is "the number of ways to choose subsets of sizes $a_1, \ldots, a_m$ in the set of size $n$". Notice that the subsets are different.

The easiest way to prove the standard formula $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ is the following. Fix one element of the set. Let is be $A$. Then all subsets of size $k$ could be divided into two categories: the first one is the subsets containing $A$ and the second one is the subsets which do not contain $A$. The number of subsets in the first category is clearly $\binom{n-1}{k}$ and the number of subsets in the second category is $\binom{n-1}{k-1}$.

Let's try this trick for the multinomial coefficients. Pick an element $A$. There are $m$ options. It could belong to the first, second, $\ldots$, $m$-th subset. The number of ways to choose the subsets if $A$ belongs to the $i$-th subset is $\binom{n-1}{a_1, \ldots, a_{i-1}, a_i - 1, a_{i+1}, \ldots, a_m}$. Thus $$\binom{n}{a_1, \ldots, a_m} = \binom{n-1}{a_1-1, a_2, \ldots, a_m} +\binom{n-1}{a_1, a_2-1, \ldots, a_m} + \binom{n-1}{a_1, a_2, a_3-1 \ldots, a_m} + \ldots + \binom{n-1}{a_1, \ldots, a_{m-1}, a_m - 1}$$

Answer 2

We know that:$$\Large(x_1+x_2+...+x_m)^n=\sum_{r_1+...+r_m=n}\frac{n!}{r_1!... r_m!}x_1^{r_1}...x_m^{r_m}$$ by writing $(x_1+x_2+...+x_m)^{n+1}=x_1(x_1+x_2+...+x_m)^n+...+x_n(x_1+x_2+...+x_m)^n$ and expanding each according to multinomial expansion we conclude:$$\sum_{r_1+...+r_2=n+1}\frac{(n+1)!}{r_1!... r_m!}x_1^{r_1}...x_m^{r_m}$$$$=\sum_{r_1+...+r_m=n}\frac{n!}{r_1!... r_m!}x_1^{r_1+1}...x_m^{r_m}+...+\sum_{r_1+...+r_m=n}\frac{n!}{r_1!... r_m!}x_1^{r_1}...x_m^{r_m+1}=\sum_{(r_1-1)+...+r_m=n}\frac{n!}{(r_1-1)!... r_m!}x_1^{r_1}...x_m^{r_m}+...+\sum_{r_1+...+(r_m-1)=n}\frac{n!}{r_1!... (r_m-1)!}x_1^{r_1}...x_m^{r_m}=\sum_{r_1+...+r_m=n+1}[\frac{n!}{(r_1-1)!... r_m!}+...+\frac{n!}{r_1!... (r_m-1)!}]x_1^{r_1}...x_m^{r_m}$$ therefore $$\frac{(n+1)!}{r_1!... r_m!}=\frac{n!}{(r_1-1)!... r_m!}+...+\frac{n!}{r_1!... (r_m-1)!}$$ or by a formal representation we have: $$\frac{(n+1)!}{r_1!... r_m!}=\sum_{i=1}^{m}\binom{n}{r_1,...,r_{i}-1,...,r_m}$$