Multinomial coefficient recurrence formula

Question

I am having trouble with a problem involving multinomial coefficients. I am not seeking an answer directly, just some guidance. The question asks for $$\binom{n} {k_1,k_2,k_3} = \binom{n-1}{k_1-1,k_2,k_3} + \binom{n-1}{k_1,k_2-1,k_3} + \binom{n-1}{k_1,k_2,k_3-1}$$ where $n = k_1+k_2+k_3$. I tried to use the rule for the expansion where $$\binom{n}{k_1,k_2,k_3} = n!/k_1!k_2!k_3!$$ However, the equations just expand for long lines, and I'm not clear on how to simplify any of them such that a proof would arise.

Answer 1

Your relationship with 3 terms is the classical recurrence relationship of the so-called Pascal's pyramid (analogous to $\binom{n}{p}=\binom{n-1}{p}+\binom{n-1}{p-1}$) displayed on the figure below with the example of the 3 red lines expressing $12=6+3+3$)

Please note that the bottom part is, in a natural way, the usual (2D) Pascal Triangle.

This picture has a combinatorial interpretation : $n_1$ letters 'A', $n_2$ letters 'B', $n_3$ letters 'C' with $n=n_1+n_2+n_3$. How many different words like $AACBCCCABBCAB$ can I build ? This is done by labelling all lines segments in the $x$,$y$,$z$ directions with letters $A$,$B$,$C$ resp. For example for $n_1=2$, $n_2=n_3=1$ giving rise to the $12$ following "words" :

$$AABC,ABAC,ABCA, ACAB,ACBA, \cdots CABA, CBAA$$

coding all paths from the origin to one of the points labelled $12$.

Answer 2

There's no other way than expanding everything out and perform the regrouping manually.

Alternative approach:

If you think the algebraic approach is hard to do, you can try to develop a combinatorial proof.

Think about what would be the outcome of $\dbinom{n}{k_1, k_2, k_3}$ in a concrete scenario, as can be seen in @Jean Merie's answer. Then show that the outcome of this process is the actually the same as the combined outcomes of the other three.

Below is an example if you want to see how that works.

Suppose we are trying to put $n$ items in order, among which $k_1$ items are of type a, $k_2$ of type b, and $k_3$ of type c, we can do it in two different methods.

(i) First, pick $k_1$ spots for the items of type a. Then pick $k_2$ and $k_3$ remaining spots for items of type b and c, respectively. There are $\dbinom{n}{k_1, k_2, k_3}$ ways to do it.

(ii) We can also achieve the same result by picking an item to be the first in the list, and then ordering the rest $n-1$ items. If the first item we picked is of type a, then there are $\dbinom{n-1}{k_1-1, k_2, k_3}$ ways to order the remaining items. Similarly, for type b, there are $\dbinom{n-1}{k_1, k_2-1, k_3}$ ways, and for type c, $\dbinom{n-1}{k_1, k_2, k_3-1}$ ways. Note that since we are dividing the entire process into 3 cases, the total number of ways is just the sum.

Since both methods yield to the same outcome, the number of ways must be equal (i.e. they are counting the same thing). Therefore $$ \dbinom{n}{k_1, k_2, k_3} = \dbinom{n-1}{k_1-1, k_2, k_3} + \dbinom{n-1}{k_1, k_2-1, k_3} + \dbinom{n-1}{k_1, k_2, k_3-1} $$

Answer 3

Hint: We consider exemplarily the binomial identity \begin{align*} \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\tag{1} \end{align*} and use an algebraic approach. We write binomial coefficients $\binom{n}{k}$ using the multinomial coefficient notation $$\binom{n}{k,n-k}=\frac{n!}{k!(n-k)!}$$ We also use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series $A(x)$. This way we can write for instance \begin{align*} [x^ky^{n-k}](x+y)^n=\binom{n}{k,n-k}\tag{2} \end{align*}

We derive the binomial identity (1) using the notation for multinomial coefficients. We obtain \begin{align*} \color{blue}{\binom{n}{k_1,k_2}}&=[x^{k_1}y^{k_2}](x+y)^n\tag{3}\\ &=[x^{k_1}y^{k_2}]\left((x+y)(x+y)^{n-1}\right)\tag{4}\\ &=[x^{k_1}y^{k_2}]\left(x(x+y)^{n-1}\right)+[x^{k_1}y^{k_2}]\left(y(x+y)^{n-1}\right)\tag{5}\\ &=[x^{k_1-1}y^{k_2}](x+y)^{n-1}+[x^{k_1}y^{k_2-1}](x+y)^{n-1}\tag{6}\\ &\color{blue}{=\binom{n-1}{k_1-1,k_2}+\binom{n-1}{k_1,k_2-1}} \end{align*} and the claim (1) follows.

Comment:

• In (3) we write the multinomial coefficient using the coefficient of operator as in (2).

• In (4) we factor out $(x+y)$ from the polynomial $(x+y)^n$.

• In (5) we multiply out and use the linearity of the coefficient of operator.

• In (6) we apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.

Now consider \begin{align*} \binom{n}{k_1,k_2,k_3}=[x^{k_1}y^{k_2}z^{k_3}](x+y+z)^n \end{align*} and proceed similarly as above.