Recursion formula for analogue of Catalan numbers

Question

Let $C_n = {2n \choose n}\frac{1}{n+1} = \frac{(2n)!}{n!(n+1)!}$ be the $n$th Catalan number. Then there is a recursion formula: $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$. Now let $C_{n,k} = {2n+k-1 \choose n}\frac{k}{n+k}$. Then $C_{n,1}=C_n$. Are there some recursion formulas known for $C_{n,k}$? Thank you very much.

Answer 1

Here is one way to use the generating function to get a recurrence. Let $y=f(x)^k$. Then $f(x)y'=kf'(x)y$. We can equate coefficients of $x^n$ to get a recurrence involving Catalan numbers. This can be simplified using $$ \frac{f'(x)}{f(x)} = \sum_{n\geq 0}{2n+1\choose n}x^n=g(x), $$ say, so $y'=kyg(x)$. Again equate coefficients of $x^n$.

Answer 2

Let the generating function of $C_n$ be $f(x)$. The g.f. of $C_{n,k}$ is $f(x)^k$ so we can derive recursion formulas. The coefficient array of $C_{n,k}$ is OEIS sequence A009766 which has many references to the literature. Using $f(x)^{j+k}=f(x)^jf(x)^k$ gives $C_{n,j+k}$ as the discrete convolution product of $C_{n,j}$ and $C_{n,k}$. For example, with $j=k=1$, then $\;C_{n+1,1}=C_{n,2}=\sum_{i=0}^nC_{i,1}C_{n-i,1}.$

Use the equation $\;1=1/f(x)+xf(x)$ to derive $\;C_{n,k}=C_{n,k-1}+C_{n-1,k+1}\;$ for all $\;k>0$.