3
$\begingroup$

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.

  • 0
    As mentioned, take $y_i=x_i-1,$ then consider $y_1+...+y_k=n.$2011-12-17

2 Answers 2

2

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.

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