1
$\begingroup$

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!!

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Byron/Nobert/Stone - Thanks a bunch! I'm self-learning pattern-recognition and much much appreciate your help! $\endgroup$
    – KGhatak
    Jun 18, 2012 at 4:37

You must log in to answer this question.

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