0
$\begingroup$

$$\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

$\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$
    – JMoravitz
    Sep 15, 2020 at 18:53
  • $\begingroup$ i'm not sure how to use latex but the indexing is k = 1 till t $\endgroup$
    – mei
    Sep 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$
    – JMoravitz
    Sep 15, 2020 at 18:55
  • 1
    $\begingroup$ @JMoravitz i'm kind of new to combinatronics, so i'm not what you mean $\endgroup$
    – mei
    Sep 15, 2020 at 19:00
  • 1
    $\begingroup$ Please do not deface your question after it has been answered. $\endgroup$ Sep 19, 2020 at 21:03

1 Answer 1

2
$\begingroup$

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)

$\endgroup$

You must log in to answer this question.

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