Q. 1.23 - A First Course in Probability

Question

Determine the number of vectors $(x1, . . . , xn)$ such that each $x_i$ is a nonnegative integer and $\sum _{i=1}^n{x}_i\le k$

Step-by-Step Solution

Answer

The number of vectors are $\left(\begin{array}{c}k+n\\ n\end{array}\right)$.

Step 1. Given information.

From the given information, we can observe that the number of vectors $(x_1, x_2 . . . , x_n)$ such that each $x_i$ is non negative integer.

Step 2. Find the number of vectors.

The number of vectors will be represented by $\sum _{p=0}^k\left(\begin{array}{c}p+n-1\\ n-1\end{array}\right)$

Therefore,

$$\begin{gathered} \sum _{p=0}^k\left(\begin{array}{c}p+n-1\\ n-1\end{array}\right)=\left(\begin{array}{c}n-1\\ n-1\end{array}\right)+\left(\begin{array}{c}n\\ n-1\end{array}\right)+\left(\begin{array}{c}n+1\\ n+1\end{array}\right)+.......+\left(\begin{array}{c}k+n-1\\ n-1\end{array}\right) \\ \Rightarrow \sum _{p=0}^k\left(\begin{array}{c}p+n-1\\ n-1\end{array}\right)=1+\left(\begin{array}{c}n\\ n-1\end{array}\right) + \left(\begin{array}{c}n\\ n\end{array}\right)+\left(\begin{array}{c}n+1\\ n+1\end{array}\right)+.......+\left(\begin{array}{c}k+n-1\\ n-1\end{array}\right)- \left(\begin{array}{c}n\\ n\end{array}\right) \\ \Rightarrow \sum _{p=0}^k\left(\begin{array}{c}p+n-1\\ n-1\end{array}\right)=1+\left(\begin{array}{c}k+n\\ n\end{array}\right)-1 \\ \Rightarrow \sum _{p=0}^k\left(\begin{array}{c}p+n-1\\ n-1\end{array}\right)=\left(\begin{array}{c}k+n\\ n\end{array}\right) \end{gathered}$$

So, the number of vectors are$\left(\begin{array}{c}k+n\\ n\end{array}\right)$.