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.

$\endgroup$
2
  • $\begingroup$ I'm not quite sure what you're asking, but look at the equation $x_1+x_2+\cdots+x_k=n+k$ and consider "the number of solutions greater than or equal to 1". $\endgroup$
    – David Mitra
    Dec 17, 2011 at 8:30
  • $\begingroup$ As mentioned, take $y_i=x_i-1,$ then consider $y_1+...+y_k=n.$ $\endgroup$
    – Ehsan M. Kermani
    Dec 17, 2011 at 8:43

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .