Question

Argue that

$\left(\begin{array}{c}n\\ n_1,n_2,........,n_r\end{array}\right)=\left(\begin{array}{c}n-1\\ n_1-1,n_2,........,n_r\end{array}\right)+\left(\begin{array}{c}n-1\\ n_1,n_2-1,........,n_r\end{array}\right)+......+\left(\begin{array}{c}n-1\\ n_1,n_2,........,n_r-1\end{array}\right)$

Hint: Use an argument similar to the one used to establish Equation (4.1).

Short answer

It is proved that

$\left(\begin{array}{c}n\\ n_1,n_2,........,n_r\end{array}\right)=\left(\begin{array}{c}n-1\\ n_1-1,n_2,........,n_r\end{array}\right)+\left(\begin{array}{c}n-1\\ n_1,n_2-1,........,n_r\end{array}\right)+......+\left(\begin{array}{c}n-1\\ n_1,n_2,........,n_r-1\end{array}\right)$

Step-by-step solution

Step 1. Given information.

We have to prove that$\left(\begin{array}{c}n\\ n_1,n_2,........,n_r\end{array}\right)=\left(\begin{array}{c}n-1\\ n_1-1,n_2,........,n_r\end{array}\right)+\left(\begin{array}{c}n-1\\ n_1,n_2-1,........,n_r\end{array}\right)+......+\left(\begin{array}{c}n-1\\ n_1,n_2,........,n_r-1\end{array}\right)$

Step 2. Prove that nn1, n2, ........ , nr=n-1n1-1, n2, ........ , nr+n-1n1, n2-1, ........ , nr+......+n-1n1, n2, ........ , nr-1

$\left(\begin{array}{c}n\\ n_1,n_2,........,n_r\end{array}\right)$represents the no. of possible divisions of $n$distinct objects into $r$distinct groups of respective sizes $n_1,n_2,.........,n_r$.

Now, let's concentrate on one object, suppose it is grouped in $n_1$group, it can be done in $\left(\begin{array}{c}n-1\\ n_1-1,n_2,........,n_r\end{array}\right)$ways.

If it is not grouped in $n_1$group but it is grouped in $n_2$group, it can be done in$\left(\begin{array}{c}n-1\\ n_1,n_2-1,........,n_r\end{array}\right)$ways.

Similarly, if it is grouped in $n_r$group, it can be done in $\left(\begin{array}{c}n-1\\ n_1,n_2,........,n_r-1\end{array}\right)$ways.

Hence, it is proved that$\left(\begin{array}{c}n\\ n_1,n_2,........,n_r\end{array}\right)=\left(\begin{array}{c}n-1\\ n_1-1,n_2,........,n_r\end{array}\right)+\left(\begin{array}{c}n-1\\ n_1,n_2-1,........,n_r\end{array}\right)+......+\left(\begin{array}{c}n-1\\ n_1,n_2,........,n_r-1\end{array}\right)$