Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

Suppose we have $N$ integer-valued variables $i_1$, $i_2$, $\cdot\cdot\cdot$, $i_N$, such that each variable can take integer values from 0 to $k$, and the sum of these $N$ variables is also equal to $k$. Formally, we want to solve the constrained linear equation:

\begin{cases} i_1+i_2+\cdot\cdot\cdot + i_N = k \\ 0 \leq i_j \leq k & \text{where $1\leq j \leq N$} \end{cases}

Is there anyone know why the number of solutions is equal to $\binom{k+N-1}{N-1}$?

Thanks in advance very much.

share|cite|improve this question

marked as duplicate by hardmath, 5pm, Henry T. Horton, Asaf Karagila, Hagen von Eitzen Feb 15 '13 at 15:54

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.

There's a common explanation that often goes by the catch phrase "stars and bars" illustration. – hardmath Feb 15 '13 at 1:47
Yes, it's the number of solutions. How can we get this number? – Richie Feb 15 '13 at 1:53
The question has been asked and answered many times on this site. If you do a search for "stars and bars" you'll probably find several of them. – Gerry Myerson Feb 15 '13 at 1:54
Note that if the sum is $k$, limiting each $i_r \le k$ really doesn't limit anything. – vonbrand Feb 15 '13 at 3:42
up vote 1 down vote accepted

I'm sure this is a duplicate, but I couldn't find it.

Assume you align $k$ red balls on the floor.

Now take $N-1$ blue balls and place them in between the red balls.

This separates the red balls into $N$ sets of cardinality $i_j$, and of course the sum of the $i_j$'s is $k$.

Now how many ways do you have do that?

As many as the number of ways of picking $N-1$ balls among $k+N-1$.

share|cite|improve this answer

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