# Binomial Convolution

I am trying to evaluate $c_n = \sum_{k=0}^m {n \choose k}{n-k \choose m-k}$ using binomial convolution. I know that this can be written as $c_n = \sum_{k=0}^m {m \choose k}{n \choose m}$. I also know that for some sequences $a_n,b_n$, $a_n*b_n = {n \choose m}$ from binomial convolutions. Beyond this I don't know what it means to evaluate $c_n$.

The idea is that if we have two exponential generating functions $$f(z) = \sum_{k=0}^\infty a_k \frac{z^k}{k!}, \quad g(z) = \sum_{k=0}^\infty b_k \frac{z^k}{k!},$$ then their product is $$f(z)g(z) = \sum_{k=0}^\infty c_k \frac{z^k}{k!},$$ where $$c_k = \sum_{m=0}^k \binom{k}{m} a_k b_{m-k}$$ is the binomial convolution of their sequences of coefficients. So if we can choose an appropriate pair of sequences $\{a_k\}$ and $\{b_k\}$ such that their convolution is $\{c_k\}$, and the product of their respective EGFs has a "nice" form, then we can obtain an identity for $c_k$. What could you choose?
• I think that if $a_n=1$ and $b_n = {n \choose m}$ that it would work out nicely, but i'm a bit thrown off by the indices. Would I be able to say that the product of EGF's for $a_n$ and $b_n$ is $(\sum_{m \geq 0} \frac{x^m}{m!})(\sum_{m \geq 0} {n \choose m} \frac{x^m}{m!})$? – Mroog Oct 19 '15 at 18:47