Wednesday 17 April 2013

combinatorics - Simplify a combinatorial expression



I came a cross a kind of combinatorial expression in my research. I'm wondering if there is a way to simplify or rewrite it. The expression is pretty simple. So I'm posting it here instead of MO. It is the following.



$\displaystyle \sum\limits_{i=0}^n (-1)^i{n \choose i} {x-i \choose l}, $



where in my case $x,l$ are some positive integers. It's not hard to show when $l< n$, the expression is $0$. But I would like to know about any possible formula for $l\geq n$. I tried to search in some combinatorial identity book. There are a lot of similar expressions, but none of the identities seems to apply. Any idea or answers will be greatly appreciated.



Answer



First let $x=m$ and $l=n+j$ & use $\binom{m-i}{n+j} =[y^{n+j}]: (1+y)^{m-i}$
\begin{eqnarray*}
S= \sum_{i=0}^{n} (-1)^i \binom{n}{i} \binom {m-i}{n+j} = [y^{n+j}]: \sum_{i=0}^{n} (-1)^i \binom{n}{i} (1+y)^{m-i} \\
= [y^{n+j}]: (1+y)^m (1- \frac{1}{1+y})^n \\
=[y^{n+j}]: (1+y)^{m-n} y^n =\binom{m-n}{j}.
\end{eqnarray*}


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...