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$.

Short 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-by-step solution

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 vectorlocalid="1648364574435" $(x_1,x_2,x_3,.........,x_r)$satisfying the equationlocalid="1648364693963" role="math" $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 role="math" localid="1648364198503" $\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:

role="math" localid="1648364862419" $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-ktimes}{\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)$.