$$\binom{n+t-1}{t-1} = \sum\limits_{k=1}^t \binom{t}{k}\binom{n-1}{k-1}$$
how do you prove this? I cant get creative enough to get a combinatorial proof. I have tried picking the problem apart but I can't seem to get a proof at the end
$\begingroup$
$\endgroup$
6
-
$\begingroup$ You need to do a better job typesetting this. For starters, what is the indexing variable on the summation? $n$? $t$? $k$? What does it range between? See this page for formatting information and how to use $\LaTeX$ and MathJax on this site. $\endgroup$– JMoravitzSep 15, 2020 at 18:53
-
$\begingroup$ i'm not sure how to use latex but the indexing is k = 1 till t $\endgroup$– meiSep 15, 2020 at 18:55
-
1$\begingroup$ As for a hint, a binomial coefficient of the form $\binom{a+b-1}{b-1}$ should make you immediately think of Stars and Bars. Meanwhile a summation like this should make you think of breaking into cases based on the size of the indexing variable. $\endgroup$– JMoravitzSep 15, 2020 at 18:55
-
1$\begingroup$ @JMoravitz i'm kind of new to combinatronics, so i'm not what you mean $\endgroup$– meiSep 15, 2020 at 19:00
-
1$\begingroup$ Please do not deface your question after it has been answered. $\endgroup$– N. F. TaussigSep 19, 2020 at 21:03
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
Major Hint:
How many ways can you distribute $n$ identical balls into $t$ distinct baskets where you allow some of the baskets to be empty?
How many ways can you distribute $n$ identical balls into $t$ distinct baskets where exactly $k$ of the baskets are non-empty?
$~$
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
answered Sep 15, 2020 at 19:02