Sum of all Products on Catalan numbers

Question

how can I simplify this?

let: $$ C_n = {{2n \choose n}\over n+1} $$

find:

$$ \sum_{P_1 + P_2 + ... + P_k = r} \left(\prod_{j = 1}^k C_{P_j}\right) $$

thanks!

Answer 1

Following @RobertIsrael we have the generating function of the Catalan numbers

$$f(z) = \frac{1-\sqrt{1-4z}}{2z}$$

and the quantity in question is

$$[z^r] f(z)^k.$$

This has the integral representation

$$[z^r] f(z)^k = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r+1}} \left(\frac{1-\sqrt{1-4z}}{2z}\right)^k \; dz.$$

Now put $1-4z = w^2$ so that $1/4-w^2/4 = z$ and $dz = -w/2 \; dw$ to get

$$-\frac{1}{2^{k+1}} \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{4^{r+k+1}}{(1-w^2)^{r+k+1}} (1-w)^k w \; dw \\ = - 2^{2r+k+1} \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(1+w)^{r+k+1}} \frac{1}{(1-w)^{r+1}} w \; dw \\ = (-1)^r 2^{2r+k+1} \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(1+w)^{r+k+1}} \frac{1}{(w-1)^{r+1}} w \; dw \\ = (-1)^r 2^{2r+k+1} \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(1+w)^{r+k+1}} \frac{1}{(w-1)^{r}} \; dw \\ + (-1)^r 2^{2r+k+1} \frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(1+w)^{r+k+1}} \frac{1}{(w-1)^{r+1}} \; dw.$$

Now we require the derivative

$$\left(\frac{1}{(1+w)^{r+k+1}}\right)^{(q)} = (-1)^q \frac{(r+k+q)!}{(r+k)!} \frac{1}{(1+w)^{r+k+q+1}}.$$

This yields for the two pieces

$$(-1)^r 2^{2r+k+1} (-1)^{r-1} \frac{(2r+k-1)!}{(r-1)!(r+k)!} \frac{1}{2^{2r+k}} + (-1)^r 2^{2r+k+1} (-1)^{r} \frac{(2r+k)!}{r!(r+k)!} \frac{1}{2^{2r+k+1}} \\ = -2 {2r+k-1\choose r-1} + {2r+k\choose r} \\ = {2r+k\choose r} \left(1-2\frac{r}{2r+k}\right) \\ = \frac{k}{2r+k} {2r+k\choose r}.$$

Here we have used the fact that $\sqrt{1-4z} = 1 - 2z - 2z^2 - \cdots$ so that with $z$ rotating once around the origin the variable $w$ rotates once around the value one, with a contour that may be deformed to a circle.

Answer 2

I presume $k$ is a fixed positive integer. This will be the coefficient of $x^r$ in $g(x)^k$, where $g(x) = \dfrac{1-\sqrt{1-4x}}{2x}$ is the generating function of the Catalan numbers. According to Maple, it is $$\frac { (k+2r-1)! \; k}{(k+r)! \; r!} $$