1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    Avodyne

    User Avatar
    Science Advisor

    Well, I took a look and couldn't get any farther than you did, sorry! Definitely does not look easy ...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Combinatorics/Probability problem.
  1. Combinatorics Problem (Replies: 3)

  2. Combinatorics problem (Replies: 2)

Loading...