Stanley Enumerative Combinatorics 1.4

Question

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.

Answer 1

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.

Answer 2

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.