- #1

- 304

- 12

[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.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter techmologist
- Start date

- #1

- 304

- 12

[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.

- #2

- 304

- 12

- #3

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

- 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
relements from {1, ..., k}- Choose
m-relements from {1, ..., n-k}

Well, it's easy to reorganize the data:

...

- Pick an integer
k- Choose
relements from {1, ..., k}- Choose
m-relements 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

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

- #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
melements in {1, ..., n} along with an integerksuch thatrof the chosen elements are less than or equal tok,- A set of
melements in {1, ..., n}?

Well, yes, but if

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

Okay. Maybe I misunderstood what you were saying before. Are we adding an extra object to

- #7

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

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 asA 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

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!

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

[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

[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

[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!

Last edited:

Share: