What is the Combinatorial Interpretation of this Sum?

[techmologist]

Is there a combinatorial interpretation of the sum

$$\sum_{k=0}^{n}\binom{k}{r}\binom{n-k}{m-r}$$ ?

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

 

[techmologist]

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.

 

[Hurkyl]

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

 

[techmologist]

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?

 

[Hurkyl]

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.

 

[techmologist]

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.

 

[Hurkyl]

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

 

[techmologist]

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

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

Summing over k gives

$$\frac{r+1}{m+1}\frac{\binom{n+1}{m+2}}{\binom{n}{m+1}}$$

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

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

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

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

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!