Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial interpretation

  1. Jul 2, 2010 #1
    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.
     
  2. jcsd
  3. Jul 3, 2010 #2
    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.
     
  4. Jul 3, 2010 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  5. Jul 3, 2010 #4
    Ah, I see where you are going with that. But isn't that going to come out to n C m?
     
  6. Jul 3, 2010 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  7. Jul 3, 2010 #6
    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.

    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.
     
  8. Jul 4, 2010 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.​
     
  9. Jul 4, 2010 #8
    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: Jul 5, 2010
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorial interpretation
  1. Combinatorial Probmlem (Replies: 2)

  2. Combinatorial Question (Replies: 17)

  3. Combinatorial question (Replies: 8)

  4. Combinatorial Problem (Replies: 1)

Loading...