# Combinatorics/Probability problem.

1. Aug 17, 2008

### gumi_kr

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.

2. Aug 18, 2008

### Diffy

What do you have so far? What have you tried?

3. Aug 18, 2008

### gumi_kr

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

Last edited: Aug 18, 2008
4. Aug 20, 2008

### Avodyne

Well, I took a look and couldn't get any farther than you did, sorry! Definitely does not look easy ...