Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

By induction I can prove : $$\sum^{M}_{t=0}\frac{(t+D-1)!}{t!(D-1)!} = \frac{(D+M)!}{D!M!} $$

However, I couldn't derive the right hand side directly.

It would be of great help if anyone can solve it!!

share|cite|improve this question

$(1+x)^{M} (1+x)^{D} = (1+x)^{M+D} $

compute coefficient of $x^{D}$ on both sides. $$$$ on LHS, it is $$\sum^{M}_{t=0}\frac{(t+D-1)!}{t!(D-1)!} $$ and on it is RHS $$ \frac{(D+M)!}{D!M!} $$

share|cite|improve this answer

Here is a combinatorial proof.

Assume you have $D+1$ types of cakes, and you allowed to choose $M$ cakes. Of course you can take several cakes of the same type. The amount of possible choices is combination with repetitions: $$ {(D+1)+M - 1 \choose D}=\frac{(M+D)!}{M!D!}\tag{1} $$ How can we classify all possible choices? We say our choice belongs to the $t$-th class if we choose $M-t$ cakes of the first type. How many choices of $t$-th type are there? Well this is amount of possible choices of remaining $t$ cakes from remaining $D$ types of cakes, which is equal to $$ {D+t-1 \choose D-1}=\frac{(D+t-1)!}{(D-1)!t!} $$ Since we are allowed to take only $M$ cakes, there are $M+1$ classes - $t$ varies from $0$ to $M$. Now we see that total amount of choices is sum of amount of choices over all classes: $$ \sum\limits_{t=0}^M{D+t-1\choose D-1}=\sum\limits_{t=0}^M\frac{(D+t-1)!}{(D-1)!t!} $$ On the other hand this amount is equals to $(1)$.

share|cite|improve this answer

Start with the binomial coefficient relation $${n\choose D}={n-1\choose D}+{n-1\choose D-1}$$ rewritten as $${n\choose D}-{n-1\choose D}={n-1\choose D-1}.$$

Adding these increments gives $$ {D+M\choose D}-{D-1\choose D}=\sum_{n=D}^{D+M}{n-1\choose D-1}.$$ Since ${D-1\choose D}=0$ this gives you the sum that you want.

This technique is called upper summation, see also here.

Here's another combinatorial argument to complement Norbert's. The number of ways to select $D$ distinct values from the set $\{1,2,\dots,D+M\}$ is $${D+M\choose D}.$$ For $0\leq t\leq M$, the number of such selections with maximum value $D+t$ is
$${D-1+t\choose D-1}.$$

share|cite|improve this answer
Byron/Nobert/Stone - Thanks a bunch! I'm self-learning pattern-recognition and much much appreciate your help! – BuckCherry Jun 18 '12 at 4:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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