0
$\begingroup$

This question already has an answer here:

I thought of using the balls and flags trick - where you use the flags to separate identical balls into different groups. But I am not able to discard the solutions in which I get $zeroes$. Please provide with a simplified proof. Thank you! :)

$\endgroup$

marked as duplicate by N. F. Taussig, Henrik, Shailesh, Namaste, Daniel W. Farlow Nov 14 '16 at 1:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ Number of positive integer solutions to $x_1+x_2+...+x_k=n$ is $\binom{n-1}{k-1}$ by your 'balls and flags' method. There are so many posts here regarding this type of problem. Have a look at this. $\endgroup$ – StubbornAtom Nov 13 '16 at 14:26
  • $\begingroup$ Yeah, thanks! Sorry for re-posting the question. :( My bad! $\endgroup$ – Ishaan Nov 13 '16 at 14:30
0
$\begingroup$

To emphasize what @StubbornAtom said : consider an array of $n$ ones. To generate a sum of $k$ numbers which add p to $n$, you just have to separate your array in $k$ packets, which requires $k-1$ "walls". There are \binom{n-1}{k-1}$ ways to choose the places of your walls.

Example : $x+y+z=7$ : $$(1+1+1+1+1+1+1) \longrightarrow (1+1|1+1+1|1+1) \longrightarrow 2+3+2$$ You have to change $2=k-1$ of the $6=n-1$ "$+$" into "$|$".

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.