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