Probability question

  • Thread starter quasar987
  • Start date
  • #1
quasar987
Science Advisor
Homework Helper
Gold Member
4,784
18
Show that there are [itex]\binom{r}{k}\binom{n-1}{n-r-k}[/itex] solutions to the equation [itex]x_1+...+x_r=n[/itex] for which exactly k of the r terms of the sum are nul.

There are [itex]\binom{r}{k}[/itex] ways of choosing which k of the r [itex]x_i[/itex]'s are zero, and there are

[tex]\binom{n+(r-k)-1}{n}[/tex]

distinc solutions to the resulting equation. What is wrong with that? If nothing, how are the two binomial coefficients equal?
 

Answers and Replies

  • #2
0rthodontist
Science Advisor
1,230
0
It says exactly k must be null. So once you've chosen your 0's, the remaining variables must take values >= 1.
 
  • #3
AKG
Science Advisor
Homework Helper
2,565
4
The whole thing doesn't look right. Treat the xi as distinguishable boxes and n as a bunch of n indistinguishable balls. The question is, how many ways can you put n indistinguishable balls into r distinct boxes if exactly k of the r boxes end up empty?

There are [itex]\binom{r}{k}[/itex] ways to choose which boxes will be empty. Now put your n balls in a row, and observe there are n-1 gaps between adjacent balls. Pick r-k-1 of these gaps (there are [itex]\binom{n-1}{r-k-1} = \binom{n-1}{(n-1)-(r-k-1)} = \binom{n-1}{n-(r-k)}[/itex] ways to do this). The bunch of balls occuring before the first chosen gap goes in the first of the boxes that wasn't chosen to be empty. The next bunch of balls (occuring between the first and second chosen gaps) goes in the next of the boxes that wasn't chosen to be empty.
 
  • #4
quasar987
Science Advisor
Homework Helper
Gold Member
4,784
18
Well spoted 0rthodontist. And AKG too for noticing that there is an error in the question. (the book really says n-r-k)
 

Related Threads on Probability question

  • Last Post
Replies
11
Views
928
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
770
  • Last Post
Replies
4
Views
852
  • Last Post
Replies
9
Views
870
  • Last Post
Replies
4
Views
986
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
802
Top