1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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!})$? $\endgroup$ – Mroog Oct 19 '15 at 18:47
0
$\begingroup$

nCk is simply coefficient of x^k in the expansion (1+x)^n

n-kCm-k is coefficient of x^(m-k) in thr expansion (1+x)^(n-k)

Multiplying both and taking sum of nCk x (n-k)C(m-k) = coefficient of x^m in the expansion (1+x)^(2n-k) which is

2n-kCm

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.