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

Homework Help: Combinatorics/Probability problem.

  1. Aug 17, 2008 #1
    1. The problem statement, all variables and given/known data

    Let [tex]R ^{M} _{P}= \sum_{s=0}^{P} {M+1 \choose s}[/tex], for [tex]0 \leqslant P \leqslant M [/tex], [tex]P,M\in \mathbb{N}[/tex].

    Proove that:
    [tex] \sum_{q=0}^{M}R^{M}_{q}\cdot R^{M}_{M-q}=(2M+1) {2M \choose M}[/tex]

    and give it's combinatorical idea.

    I'm trying to solve this for 3 days - please help..
  2. jcsd
  3. Aug 18, 2008 #2
    What do you have so far? What have you tried?
  4. Aug 18, 2008 #3
    It was an usual exercise in probability theory course. It looks easy
    but i'm trying to solve this for a long time without success.

    1) I know that trying simply to count it - isn't the right way (even
    using some advanced properties of binomial coefficient).

    2) It could be connected with Banach's modified matchbox problem, but
    not neccessery (right side of the formula multiplied by 2^{n-1} is
    expected number of matches..)

    3) right sight looks like "choosing the leader and it's group" but i
    cannot find connection with left side with this 'intuition'

    4) typing R^{M}_{P} with Gamma and hypergeometric function is not a
    good option - too many calculations

    5) It could be connected with properties of 'Bernoulli triangle' but i
    couldn't find any materials about that.
    (it's The number triangle (Sloane's A008949) composed of the partial
    sums of binomial coefficients)

    6) I couldn't find anything useful in "Advanced Combinatorics"
    (Comtet) or Combinatorics 2nd R. Merris

    well, i can show you some easy calculations (but i don't think that it makes the problem easier):
    [tex] \sum_{q=0}^{M}R^{M}_{q}\cdot R^{M}_{M-q}= \sum_{q=0}^{M}R^{M}_{q}\cdot (2^{M+1} - R_{q}^{M}) = 2^{M+1}\cdot \sum_{q=0}^{M}(M+1-q)\cdot {M+1 \choose q} - \sum_{q=0}^{M} (R^{M}_{q})^{2} = 2^{M+1}\cdot \sum_{q=0}^{M+1}q\cdot {M+1 \choose q} - \sum_{q=0}^{M} (R^{M}_{q})^{2} =[/tex]
    [tex] =2^{2M+1}\cdot (M+1) - \sum_{q=0}^{M} (R^{M}_{q})^{2}[/tex]

    On the other hand: (Banach's matchbox problem and it's expecting value):
    [tex](2M+1)\cdot {2M \choose M} = 2^{2M} + \sum_{q=0}^{M} q\cdot {2M-q \choose M}\cdot 2^{q}[/tex]
    Last edited: Aug 18, 2008
  5. Aug 20, 2008 #4


    User Avatar
    Science Advisor

    Well, I took a look and couldn't get any farther than you did, sorry! Definitely does not look easy ...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook