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.

  • $\begingroup$ 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? $\endgroup$ – AsinglePANCAKE Mar 25 '13 at 20:29
  • $\begingroup$ @AsinglePANCAKE I have added some explanation for that identity. $\endgroup$ – Ivan Loh Mar 26 '13 at 0:01

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.