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