Saturday, December 19, 2015

How do i reduce this expression of binomial coefficients



I was solving a problem and am stuck with this expression. Any leads on how can I simplify this expression?



$$\frac{{\sum\limits_{x=Q}^{N-P+Q} (x-Q) \binom{x}{Q} \binom{N-x}{P-Q}}}{{\sum\limits_{x=Q}^{N-P+Q} \binom{x}{Q} \binom{N-x}{P-Q}}}$$



UPDATE: I realized a mistake. expression updated.


Answer



There is a variation of the Vandermonde identity that reads, for $k,m,n\in\mathbf N$:
$$

\sum_{i=0}^k\binom im\binom{k-i}n=\binom{k+1}{m+n+1}.
$$
Here is how you can remember it: let $0\leq a_0<\cdots

One can restrict the range of $i$ to the values $m\leq i\leq k-n$, as other terms contribute $0$.



So your expression simplfies to
$$
\frac{{\sum\limits_{x=Q}^{N-P+Q} \binom{x-1}{Q} \binom{N-x}{P-Q}}}{{\sum\limits_{x=Q}^{N-P+Q} \binom{x}{Q} \binom{N-x}{P-Q}}}=
\frac{\binom{N}{P+1}}{\binom{N+1}{P+1}}=\frac{N-P}{N+1}.

$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...