Combinatorics/Probability problem. Text

gumi_kr

Aug17-08, 08:10 PM

1. The problem statement, all variables and given/known data

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

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

and give it's combinatorical idea.

I'm trying to solve this for 3 days - please help..

gumi_kr

Aug18-08, 04:01 PM

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):
\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} =
=2^{2M+1}\cdot (M+1) - \sum_{q=0}^{M} (R^{M}_{q})^{2}

On the other hand: (Banach's matchbox problem and it's expecting value):
(2M+1)\cdot {2M \choose M} = 2^{2M} + \sum_{q=0}^{M} q\cdot {2M-q \choose M}\cdot 2^{q}