# Coefficients of Generating Functions

This problem is from Stanley's Enumerative Combinatorics: Volume 1. page 115 here for those desirous of context (prettier conTeXt).

Anyway, it asks for fixed $j,k\in \mathbb{Z}$ to show that $$\sum_{n\ge 0}{(2n-j-k)!x^n\over (n-j)!(n-k)!(n-j-k)!n!}=\sum_{n\ge 0}{x^n\over n!(n-j)!} \sum_{n\ge 0}{x^n\over n!(n-k)!}$$

It also addends that "Any term with $(-r)$ in the denominator, where $r\gt 0$, is set equal to 0."

So for the LHS I have deduced the following seemingly useless fact that the coefficient of $x^n$ is $${1\over2} {4n-2j-2k)\choose (n-j),(n-k),(n-j-k),n}$$ where we have this denoting the usual multi-nomial coefficient. I've messed around with the usual rules for multiplying generating functions on the RHS but I still can't seem to get anywhere. I'm sufficiently embarrassed, but I turn to you for help anywho.

We have

$$\sum_{n \geq 0}{\frac{x^n}{n!(n-j)!}}\sum_{n \geq 0}{\frac{x^n}{n!(n-k)!}}=\sum_{n \geq 0}{\left(\sum_{i=0}^{n}{\frac{1}{i!(i-j)!}\frac{1}{(n-i)!((n-i)-k)!}}\right)x^n}$$

\begin{align} \sum_{i=0}^{n}{\frac{1}{i!(i-j)!}\frac{1}{(n-i)!((n-i)-k)!}}& =\frac{1}{n!(n-j-k)!}\sum_{i=0}^{n}{\binom{n}{i}\binom{n-j-k}{n-i-k}} \\ & =\frac{1}{n!(n-j-k)!}\binom{2n-j-k}{n-k} \\ & =\frac{(2n-j-k)!}{(n-j)!(n-k)!(n-j-k)!n!} \end{align}

Substituting the second equation into the first one gives the desired identity.

Edit: $\sum_{i=0}^{n}{\binom{n}{i}\binom{n-j-k}{n-i-k}}=\binom{2n-j-k}{n-k}$ is a standard identity which can be easily proved with the following combinatorial argument:

The RHS counts the number of ways to choose $n-k$ objects from $2n-j-k$ objects. We now count this in a different way. We choose $i$ objects from the 1st $n$ objects, and $n-i-k$ objects from the other $n-j-k$ objects. Clearly we must have $0 \leq i \leq n$. Summing over $i$ gives the LHS, thus proving the identity.

• In the second line on the RHS, should turning that sum over i into ${2n-j-k}\choose{n-k}$ be clear? I don't quite see it, or is it just one of those standard identities? – AsinglePANCAKE Mar 25 '13 at 20:29
• @AsinglePANCAKE I have added some explanation for that identity. – Ivan Loh Mar 26 '13 at 0:01