5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ For the updated question, note that $(x-Q)\binom xQ=(Q+1)\binom x{Q+1}$, and you can let the sum start at $Q+1$ since the $x=Q$ term is zero. $\endgroup$ – joriki Jan 19 '13 at 13:43
  • $\begingroup$ @joriki Thanks, using that with vandermonde identity simplified the equation. $\endgroup$ – nims Jan 19 '13 at 19:35
  • $\begingroup$ Are you sure? I make it $$ (Q+1)\frac{\binom{N+1}{P+2}}{\binom{N+1}{P+1}}=\frac{(Q+1)(N-P)}{P+2}\;. $$ (This refers to a comment you'd made but now edited, in which you said the result was $(Q+1)/(P+2)$. $\endgroup$ – joriki Jan 19 '13 at 19:39
  • $\begingroup$ @joriki my bad, i was using that expression in another expression where $(N-P)$ was getting cancelled. :) $\endgroup$ – nims Jan 19 '13 at 19:42
6
$\begingroup$

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<a_{m+n}\leq k$ be one of the $\binom{k+1}{m+n+1}$ subsets of $m+n+1$ numbers $a_j$ from the $k+1$-set $\{0,\ldots,k\}$, arranged increasingly. Put $i=a_m$, then there are $\binom im$ choices left for $a_0,\ldots,a_{m-1}$, and $\binom{k-i}n$ choices for $a_{m+1},\ldots,a_{m+n}$.

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

$\endgroup$
  • $\begingroup$ Thanks for the reply. I realized i made a mistake. What to do if the numerator becomes $$\sum\limits_{x=Q}^{N-P+Q} (x-Q) \binom{x}{Q} \binom{N-x}{P-Q}$$ $\endgroup$ – nims Jan 19 '13 at 13:05
  • 1
    $\begingroup$ @nims: If you meant another question than the one you posed, please change (edit) the question (and indicate there that you did so). $\endgroup$ – Marc van Leeuwen Jan 19 '13 at 13:41
  • $\begingroup$ Thanks, turns out the new expression can be easily solved by little operation as suggested in the comments and then applying Vandermonde identity as you suggested. $\endgroup$ – nims Jan 19 '13 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.