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