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