I've been having difficulty with the following exercise from Stanley's Enumerative Combinatorics (chapter 1, problem 4):

Fix $j,k \in \mathbb{Z}$. Show that

\begin{equation} \sum_{n\geq0} \frac{(2n-j-k)!x^n}{(n-j)!(n-k)!(n-j-k)!n!} = \bigg[ \sum_{n\geq0} \frac{x^n}{n!(n-j)!} \bigg] \bigg[\sum_{n\geq0}\frac{x^n}{n!(n-k)!}\bigg]. \end{equation}

Any term with $(-r)!$ in the denominator, where $r > 0$, is set equal to $0$.

I cannot for the life of me figure out why this is giving me so much trouble. To me, the obvious way to proceed is by applying the rule for multiplying generating functions: $(\sum_{n\geq0} a_nx^n)(\sum_{n\geq0}b_nx^n) = \sum_{n\geq0}c_nx^n$, where $c_n = \sum_{i=0}^n a_ib_{n-i}$. Set $a_n = \frac{1}{n!(n-j)!}$ and $b_n = \frac{1}{n!(n-k)!}$, and we get that the coefficient of $x^n$ in the product is $\sum_{i=0}^n \frac{1}{i!(i-j)!(n-i)!(n-i-k)!}$. However, I have no idea how to manipulate these sums of factorials. I suppose on the other side, we can manipulate it a bit to get $\sum_{n\geq0} \binom{2n-j-k}{n}\frac{x^n}{(n-j)!(n-k)!}$, which looks a little bit more like the other side with the $(n-j)!$ and $(n-k)!$ terms, but it doesn't solve the problem of summing over factorials.

Am I on the right track here? This is one of the few questions that doesn't have a solution in the back, so I can't even check to see if I'm attacking the problem from the right angle.

Thanks in advance.


Hint: As you have noticed that $$\sum _{i=0}^n\frac{1}{i!(i-j)!(n-i)!(n-i-k)!},$$ that's perfect. Now, group them to form two binomials. For the first one, multiply and divide by $n!$. You should get something like a Vandermonde identity.

  • 1
    $\begingroup$ This was perfect. Multiplied top and bottom of the sum by $(n-j)!(n-k)!$, using Vandermonde convolution left me with $\frac{1}{(n-j)!(n-k)!} \binom{2n-j-k}{n}$, which was exactly what I needed. Thank you so much. $\endgroup$ – dkbruce Sep 14 '17 at 3:10
  • $\begingroup$ You are welcome. $\endgroup$ – Phicar Sep 14 '17 at 3:39

Showing some of the algebra by way of enrichment. We treat the case where $j,k\ge 0.$ The identity then becomes

$$\sum_{n\ge j+k} \frac{(2n-j-k)!}{(n-j)! (n-k)! (n-j-k)! n!} x^n = \sum_{n\ge j} \frac{1}{n!(n-j)!} x^n \sum_{n\ge k} \frac{1}{n!(n-k)!} x^n$$

or alternatively

$$\sum_{n\ge 0} \frac{(2n+j+k)!}{(n+k)! (n+j)! n! (n+j+k)!} x^{n+j+k} = \sum_{n\ge 0} \frac{1}{(n+j)!n!} x^{n+j} \sum_{n\ge 0} \frac{1}{(n+k)!n!} x^{n+k}$$

which is

$$\sum_{n\ge 0} \frac{(2n+j+k)!}{(n+k)! (n+j)! n! (n+j+k)!} x^{n} = \sum_{n\ge 0} \frac{1}{(n+j)!n!} x^{n} \sum_{n\ge 0} \frac{1}{(n+k)!n!} x^{n}$$

Hence we have to show that

$$\sum_{q=0}^n \frac{1}{(q+j)! q!} \frac{1}{(n-q+k)! (n-q)!} = \frac{(2n+j+k)!}{(n+k)! (n+j)! n! (n+j+k)!}.$$

Multiply by $n! (n+j+k)!$ to get

$$\sum_{q=0}^n {n\choose q} {n+j+k\choose n-q+k} = {2n+j+k\choose n+k}.$$

We get on the left

$$\sum_{q=0}^n {n\choose q} [z^{n-q+k}] (1+z)^{n+j+k} = [z^{n+k}] (1+z)^{n+j+k} \sum_{q=0}^n {n\choose q} z^q \\ = [z^{n+k}] (1+z)^{n+j+k} (1+z)^n \\ = [z^{n+k}] (1+z)^{2n+j+k} = {2n+j+k\choose n+k}$$

which is the claim.


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.