Q. 1.21 - A First Course in Probability

Question

Argue that there are exactly $\left(\begin{array}{c}r\\ k\end{array}\right)\left(\begin{array}{c}n-1\\ n-r+k\end{array}\right)$ solutions of $x_1 + x_2 + · · · + x_r = n$ for which exactly $k$ of the $x_i$ are equal to $0$.

Step-by-Step Solution

Answer

The exact number of solutions for $x_1 + x_2 + · · · + x_r = n$, for which exactly $k$ of the $x_i=0$ is $\left(\begin{array}{c}r\\ k\end{array}\right)\left(\begin{array}{c}n-1\\ n-r+k\end{array}\right)$.

Step 1. Given information.

It is given that,

$x_1 + x_2 + · · · + x_r = n$ ..................... (1)

for which exactly $k$ of the $x_i=0$.

Step 2. State the proposition.

The proposition states that: 

There are $\left(\begin{array}{c}n+r-1\\ r-1\end{array}\right)$ distinct non-negative integer-valued vector $(x_1, x_2, x_3, ........., x_r)$ satisfying the equation  $x_1 + x_2 + · · · + x_r = n$.

Step 3. Find the no. of solutions.

Since, it is given that $k$ of $x_i\text{'}s$ are equal to $0$, so these $k$ can be selected in $\left(\begin{array}{c}r\\ k\end{array}\right)$ ways. Hence the number of $x_i\text{'}s$, which are equal to $0$ is given as $\left(\begin{array}{c}r\\ k\end{array}\right)$.

The remaining of the $x_i\text{'}s$ are greater than or equal to $1$. So, the equation (1) will become:

$x_1 + x_2 + · · · + x_{r-k} = n; x_i\ge 1$ .................. (2)

To use the proposition, convert the vector $(x_1, x_2, x_3, ........., x_r)$ as non negative integer valued vector $(x_1, x_2, x_3, ........., x_{r-k})$  and thus

 $x_1-1 + x_2 -1+ · · · + x_{r-k}-1 =\underset{r-k times}{ \underbrace{n-1-1} }; x_i\ge 1$

So the equation (2) will now become:

$x_1 + x_2 + · · · + x_{r-k} = n-r+k; x_i\ge 0$ ............... (3)

Therefore, the no. of distinct non-negative integer-valued vector satisfying equation (3) will be

$\left(\begin{array}{c}\left(n-r+k\right)+\left(r-k\right)-1\\ \left(r-k-1\right)\end{array}\right)=\left(\begin{array}{c}\left(n-1\right)\\ \left(r-k-1\right)\end{array}\right)$

By using the combinatorial identity

$\left(\begin{array}{c}\left(n-1\right)\\ \left(r-k-1\right)\end{array}\right)=\left(\begin{array}{c}\left(n-1\right)\\ \left(n-1\right)-\left(r-k-1\right)\end{array}\right)$

Therefore, the exact no. of solutions for the given equation is $\left(\begin{array}{c}\left(n-1\right)\\ \left(r-k-1\right)\end{array}\right)=\left(\begin{array}{c}\left(n-1\right)\\ \left(n-1\right)-\left(r-k-1\right)\end{array}\right)$.