Combinatorial interpretation

  • #1
304
12
Is there a combinatorial interpretation of the sum

[tex]\sum_{k=0}^{n}\binom{k}{r}\binom{n-k}{m-r}[/tex] ?

If it were a sum over r instead, it would be n C m. But I don't know about this one.
 

Answers and Replies

  • #2
304
12
After plugging in a few numbers and playing around with it, I found that the sum is, surprisingly, equal to (n+1) C (m+1). Maybe knowing this will make it easier to come up with an interpretation.
 
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Well, there is a sort of literal translation: it's counting the number of ways to:

  • Pick an integer k
  • Choose r elements from {1, ..., k}
  • Choose m-r elements from {1, ..., n-k}

Well, it's easy to reorganize the data:

  • Pick an integer k
  • Choose r elements from {1, ..., k}
  • Choose m-r elements from {k+1, ..., n}

and

  • Choose m elements from {1, ..., n}
  • Pick an integer such that r of the elements are less than or equal to k
 
  • #4
304
12
Well, there is a sort of literal translation: it's counting the number of ways to:

  • Pick an integer k
  • Choose r elements from {1, ..., k}
  • Choose m-r elements from {1, ..., n-k}

Well, it's easy to reorganize the data:

  • Pick an integer k
  • Choose r elements from {1, ..., k}
  • Choose m-r elements from {k+1, ..., n}
...

Ah, I see where you are going with that. But isn't that going to come out to n C m?
 
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Actually, I wasn't going anywhere -- those were just simplifications I saw off the top of my head. I stopped once I noticed a path to start following in earnest!

Do you not see the difference between:
  • A set of m elements in {1, ..., n} along with an integer k such that r of the chosen elements are less than or equal to k,
  • A set of m elements in {1, ..., n}?

Anyways, the path forward I saw was to look for a way to insert an extra object into the setup to represent k.
 
  • #6
304
12
Actually, I wasn't going anywhere -- those were just simplifications I saw off the top of my head. I stopped once I noticed a path to start following in earnest!

Do you not see the difference between:
  • A set of m elements in {1, ..., n} along with an integer k such that r of the chosen elements are less than or equal to k,
  • A set of m elements in {1, ..., n}?

Well, yes, but if k is an element of {1,...,n}, then aren't you choosing from n elements? And if it is not in {1, ..., n}, then all m elements are less than k.

Anyways, the path forward I saw was to look for a way to insert an extra object into the setup to represent k.

Okay. Maybe I misunderstood what you were saying before. Are we adding an extra object to n ordered objects that are labeled {1,....,n} in such a way that it is still distinguishable from another object (an integer, presumably) of the same value? Or are we actually dealing with the integers 1,...,n themselves? That's what I assumed at first. Thank you.
 
  • #7
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
The final transformation is to realize
A set of m elements in {1, ..., n} along with an integer k such that r of the chosen elements are less than or equal to k​
contains the same data as
A set of m+1 elements in {1, ..., n+1}/indent]

To convert from the second to the first, let k be the r+1-th number (in sorted order). Remove k from the original list, and subtract one from k and from every chosen number bigger than k.

To convert from the first to the second, add one to every chosen number greater than k, then add k+1 to the list of chosen numbers.


Maybe balls in boxes will make it more clear. From the data
A set of m elements in {1, ..., n} along with an integer k such that r of the chosen elements are less than or equal to k​
we can depict it by lining up n boxes and placing m white balls into the boxes. Then insert one extra box between k and k+1 with a red ball.​
 
  • #8
304
12
Thank you, Hurkyl, for taking the time to explain it in detail. That makes sense now.

EDIT:

BTW, the above identity allows one to prove Laplace's celebrated (and abused) Rule of Succession without having to take limits.

An urn contains n balls. The number k of red balls is determined randomly so that the possibilities k = 0, 1, ..., n, are equally likely. The remaining n-k balls are white. You do not know the fraction of red balls. You draw m balls, r of which are red. What is the probability that the (m+1)st is red? Conditional on k, the probability that r of the first m, as well as the (m+1)st balls are red is

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

Summing over k gives

[tex]\frac{r+1}{m+1}\frac{\binom{n+1}{m+2}}{\binom{n}{m+1}}[/tex]

which is proportional to the unconditional probability that r of the first m as well as the (m+1)st balls are red. The constant of proportionality is P(k) = 1/(n+1). Similarly, the unconditional probability that r of the first m balls are red is proportional to

[tex]\frac{\binom{n+1}{m+1}}{\binom{n}{m}}[/tex] by the same constant P(k) = 1/(n+1).

Finally, divide the first by the second and apply Bayes' theorem to get

[tex]P{\text{(m+1)st ball is red} | \text{r of the first m were red}} = \frac{(r+1)\binom{n}{m}\binom{n+1}{m+2}}{(m+1)\binom{n+1}{m+1}\binom{n}{m+1}} = \frac{r+1}{m+2}[/tex]

So, of course, if you flip a coin once and it comes up heads, that means it comes up heads on the next flip with probability 2/3! :biggrin:
 
Last edited:

Related Threads on Combinatorial interpretation

  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
872
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
651
  • Last Post
Replies
19
Views
4K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
5
Views
2K
Top