Combinations formula What is the no. of ways to distribute N identical objects among two persons such that at every instant first person gets more than the second person?
My approach is :
For N=1 ans=1
For N=2 ans=1
For N=3 ans=2
For N=4 ans=3
For N=5 ans=6
Though I've generated this sequence,I'm unable to figure out the formula.
 A: This is similar to "Bertrand's Ballot Theorem" (see http://en.wikipedia.org/wiki/Bertrand's_ballot_theorem ). If one gets $p$ and the other $q$, the probability that the winner ($p>q$) is always ahead is $$\frac{p-q}{p+q}$$ The number of ways to order the $p$ and $q$ instances is the combination (we choose any p for the p's) $$\binom{N}{p}=\frac{N!}{p!\,q!}$$ We can get the total number of ways for some $p$ by taking the probability times the number of ways in all. So you can sum this over possible values of $p$: for $N=2n$ even, we get $$\sum_{k=n+1}^{2n}\frac{k-(2n-k)}{k+(2n-k)}\cdot \binom{2n}{k}=\sum_{k=n+1}^{2n}\frac{2k-2n}{2n}\binom{2n}{k}={1\over n}\sum_{k=n+1}^{2n}\left(k\binom{2n}{k}-n\binom{2n}{k}\right)$$
This becomes $${1\over n}\sum_{k=n+1}^{2n}(2n)\binom{2n-1}{k-1}-\sum_{k=n+1}^{2n}\binom{2n}{k} =2\cdot 2^{2n-2}-\left(2^{2n-1}-\binom{2n-1}{n}\right)$$ Rewriting, $$\binom{2n-1}{n}=\binom{N-1}{N\over 2} $$
From your values it looks like the formula $$\binom{N-1}{\text{floor}\frac{N}{2}}$$ returns the answer for all $N$. The sequence starts out $1,1,2,3,6,10,20,35,...$.
