When to Add and/or Multiply Combinatorial Coefficients? Though having read I and II, I still fail to understand when to add and/or multiply Combinatorial Coefficients. I exemplify my confusion:


*

*Multinomial Pascal's Rule $\quad$ Source: 1.18, p 20, A First Course in Pr (8 Ed) by S Ross:
$ \dbinom{n}{n_1,.....,n_{r - 1}, n_r} = \dbinom{n - 1}{n_1 - 1,.....,n_{r - 1}, n_r}  + ...  + \dbinom{n}{n_1,.....,n_{r - 1}, n_r - 1} $



*Why add and not multiply?




*1.10(d), p 18, A First Course in Pr (8 Ed) by S Ross:
$\dbinom{n}{k}k = \dbinom{n}{k - 1}[n - (k - 1)] = n\dbinom{n - 1}{k - 1}$



*Without relying on the derivation below to explain, why cannot $\dbinom{n}{k}\color{green}{k} = \dbinom{n}{k} + k$?

*Why cannot $\dbinom{n}{k}\color{green}{k} = n + \dbinom{n - 1}{k - 1}$?

I know, and so ask NOT, how to derive 3. From the definition of basic multiplication, $\dbinom{n}{k}\color{green}{k} = \underbrace{\binom{n}{k} + \cdots + \binom{n}{k}}_{k \text{  times }} $.
Since $\color{green}{k = \dbinom{k}{k - 1}}$, I tolerate that $\dbinom{n}{k}\color{green}{k} = \dbinom{n}{k}\color{green}{\dbinom{k}{k - 1}}.$
 A: In order to make the additive structure of the formula above more comprehensible, I'd like to analyse the identity
\begin{align*}
\binom{n}{n_1,\dots,n_{r-1},n_r}&=\binom{n-1}{n_1-1,\dots,n_{r-1},n_r}\\
&\qquad+\cdots+\binom{n-1}{n_1,\dots,n_{r-1},n_r-1}\tag{1}
\end{align*}
from three different point of views. 
Please note, that the multinomial coefficients of the RHS of the identity always show $n-1$.

1.) First view based on combinatorial considerations:

We show that $(1)$ is valid by using classical combinatorial arguments. We start with the binomial pendant:

\begin{align*}
\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\qquad 0<k\leq n\tag{2}
\end{align*}

The binomial coefficient $\binom{n}{k}$ can be interpreted as the number of different subsets of size $k$ from a set with $n$ elements. And this is already the LHS of the identity. We now fix an element in the $n$-element set. We observe that when we consider the sets of size $k$ which contain this specific element, we can choose these sets in $\binom{n-1}{k-1}$ ways. On the other hand, considering the sets of size $k$, which don't contain this specific element this can be done in $\binom{n-1}{k}$ ways. These two configurations are disjoint, so that $(1)$ is valid and we see, that we sum up the binomial coefficient since they represent numbers of disjoint configurations.
We now want to emphasize the symmetry aspects of $(2)$ using multinomial coefficients instead and changing variables: Let $n_1,n_2\geq0$ and $n_1+n_2=n$.
So, we can write identity $(2)$ as

\begin{align*}
\binom{n_1+n_2}{n_1,n_2}=\binom{n_1+n_2-1}{n_1-1,n_2}+\binom{n_1+n_2-1}{n_1,n_2-1}\qquad 0<n_1,n_2\leq n\tag{3}
\end{align*}

We can also slightly modify the combinatorial argument above, by using the symmetry. We can say, that the fixed element of the $n$-element set is either in a subset with $n_1$ elements or in the disjoint subset with $n_2=n-n_1$ elements (the complement of course).
This symmetrically formulated argument can now be easily generalized to the identity $(1)$ with multinomial coefficients:

The identity $(1)$ holds, since the LHS gives the number of possibilities to choose $r$ disjoint subsets with $n_1,n_2,\dots,n_r$ elements from a set having $n=n_1+\cdots+n_r$ elements.
  Now the RHS: We fix an element and have $$\binom{(n_1-1)+n_2+\cdots+n_r}{n_1-1,n_2,\dots,n_r}$$ possibilities that this fixed element is part of the $n_1$-element subset, up to $$\binom{n_1+n_2+\cdots+n_{r-1}+(n_r-1)}{n_1,n_2,\dots,n_{r-1},n_r-1}$$ possibilities, that this fixed element is part of the last $n_r$-element subset. Since all these constellations are disjoint, the multinomial coefficients of the RHS are summed up, showing identity $(1)$ is valid.

$$ $$

2.) Second view based on generating functions:

Here we consider multinomial coefficients as coefficients of corresponding polynomials to show the additive structure of the identity $(1)$. First we consider the binomial coefficient $\binom{n}{k}$ as coefficient $[x^ky^{n-k}]$ of the polynomial $(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k}$:

\begin{align*}
\binom{n}{k}&=[x^ky^{n-k}](x+y)^n\\
&=[x^ky^{n-k}](x+y)(x+y)^{n-1}\\
&=[x^ky^{n-k}]x(x+y)^{n-1}+[x^ky^{n-k}]y(x+y)^{n-1}\\
&=[x^{k-1}y^{n-k}](x+y)^{n-1}+[x^ky^{n-k-1}](x+y)^{n-1}\\
&=\binom{n-1}{k-1}+\binom{n-1}{n-k-1}\\
&=\binom{n-1}{k-1}+\binom{n-1}{k}
\end{align*}

It's clear to see that the additive part of the RHS stems from the binom $x+y$

Now analogously for multinomial coefficients. Let $n=n_1+\cdots+n_r$, $n_1,\dots,n_r\geq 0$. The following is valid:
\begin{align*}
\binom{n}{n_1,\dots,n_r}&=[x^{n_1}\cdot...\cdot x^{n_r}](x_1+\cdots +x_r)^n\\
&=[x^{n_1}\cdot...\cdot x^{n_r}](x_1+\cdots +x_r)(x_1+\cdots +x_r)^{n-1}\\
&=[x^{n_1}\cdot...\cdot x^{n_r}]x_1(x_1+\cdots +x_r)^{n-1}\\
&\qquad+\dots+[x^{n_1}\cdot...\cdot x^{n_r}]x_r(x_1+\cdots +x_r)^{n-1}\\
&=[x^{n_1-1}\cdot...\cdot x^{n_r}](x_1+\cdots +x_r)^{n-1}\\
&\qquad+\dots+[x^{n_1}\cdot...\cdot x^{n_r-1}](x_1+\cdots +x_r)^{n-1}\\
&=\binom{n-1}{n_1-1,n_2\dots,n_r}+\cdots+\binom{n-1}{n_1,n_2\dots,n_r-1}
\end{align*}

$$ $$

3.) Third view based on lattice paths in $\mathbb{R}^r$:

We start with the two-dimensional case and use multinomial coefficients from the beginning, since the symmetry is especially valuable in this case. We consider lattice paths from $(0,0)$ to $(x,y)$ with $x,y\in \mathbb{N_0}$. The walk along a lattice path is done in steps always having length $1$ and are either in east or in north direction.
The following is valid:

The number of lattice paths of length $x+y$ from $(0,0)$ to $(x,y)$ is 
  $$\binom{x+y}{x,y}$$

Now, there are exactly two points $(x-1,y)$ and $(x,y-1)$ which are to pass one step before $(x,y)$ can be reached. The number of pathes from $(0,0)$ to $(x,y)$ is therefore the number of pathes from $(0,0)$ to $(x-1,y)$ plus the number of paths from $(0,0)$ to $(x,y-1)$. Therefore we get:
$$\binom{x+y}{x,y}=\binom{x+y-1}{x-1,y}+\binom{x+y-1}{x,y-1}$$
Now analogously for multinomial coefficients we can consider lattice paths in $\mathbb{R}^{r}$ from $(0,...,0)$ to $(x_1,\dots,x_r)$. We have $r$ points $(x_1-1,\dots,x_r)$ up to $(x_1,\dots,x_r-1)$ which are to pass one step before the endpoint can be reached. And we get in the same way as in the two-dimensional case the identity for the multinomial coefficients.

Note: These are three different views which examine the additive structure of the identity with multinomial coefficients above. The essence is that disjoint configurations are used, so that summing up of the coefficients is feasible. As already mentioned by the answer from vonbrand


To give some arguments for multiplicative applications of binomial coefficients as proposed in the question, I think the example $10$ on page $18$ from the referenced book of Ross is quite instructive.

Example 10: From a group of $n$ people, suppose that we want to choose a commitee of $k$, $k\leq n$, one of whom is to be designated as chairperson.

(a) By focusing first on the choice of the committee and then on the choice of the chair argue that there are $\binom{n}{k}k$ possible choices.
(b) By focusing first on the choice of the nonchair committee members and then on the choice of the chair, argue that there are $\binom{n}{k-1}(n-k+1)$ possible choices.
(c) By focusing first on the choice of the chair and then on the choice of the other comittee members, argue that there are $n\binom{n-1}{k-1}$ possible choices.
(d) Conclude from parts (a), (b) and (c) that
$$k\binom{n}{k}=(n-k+1)\binom{n}{k-1}=n\binom{n-1}{k-1}$$
I think, these suggestive formulations already provide good hints to see why these identities are valid. And again, the essence also for these multiplicative examples is already given in the answer from vonbrand.
A: This can be summarized into two rules: Addition rule: The union of disjoint sets $A$ and $B$ has $\lvert A \rvert + \lvert B \rvert$ elements. Multiplication rule: The cartesian product (all ways to match up an $A$ with a $B$) of sets $A$ and $B$ has $\lvert A \rvert \cdot \lvert B \rvert$ elements.
Think how you are building up what you want to count from simpler pieces, this should tell you which one to apply. 
