3

To find all solutions greater than or equal to $1$ of a linear equation in the form

$$x_1+x_2+x_3+\cdots+x_k=n ,$$

the number of them is $\binom{n-1}{k-1}$.

If I need all solutions to be greater or equal to $0$ why is it then $\binom{n+k-1}{k-1}$?

Please help. Thanks.

Srivatsan
  • 26,311
pythoniku
  • 233

2 Answers2

3

If $y_1,\ldots y_k$, where all $y_i \ge 0$, is a solution of the equation

$$x_1 + x_2 + \ldots x_k = n, x_i \ge 0,i=1 \ldots k$$

then $y_1 + 1, y_2 + 1, \ldots, y_n + 1$ is a solution to the equation

$$x_1 + x_2 + \ldots x_k = n+k,x_i \ge 1,i=1 \ldots k$$

of which there are $\binom{n+k-1}{k-1}$ by your own formula.

Reversely, for any solution for the second equation, substracting 1 from each (which is possible) gives a solution for the first one, so the operation of adding 1 to each solution is a bijection between the solution sets of these 2 equations.

Henno Brandsma
  • 242,131
1

put $y_i=x_i+1$ then $y_1+1+y_2+1...+y_k+1=n$ then $y_1+y_2+...+y_k=n-k,$$y_i \ge 0,i=1 \ldots k$.

therefore the number of items is equal to $$\binom {n-1}{k-1}$$ if in sentence instead of $n$ put $(n+k)$ then the number of items is equal to $$\binom {n+k-1}{k-1}$$

hadisanji
  • 999