Question

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

Short answer

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

Step-by-step solution

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