4
$\begingroup$

I'm trying to understand the asymptotic behaviour of a family of integer sequences related to the Catalan numbers $\left( c_n \right)_{n \in \mathbb{N}}$. The OEIS suggests that these are known as generalised Catalan numbers; I'm not sure if this term is used more widely. I think I've been able to figure a lot of this out by myself, but I'd appreciate suggestions for any suitable reference I could look up to better understand things.

Recall that the Catalan numbers have generating function $F(z)$ where $$F(z) = \frac{1-\sqrt{1-4z}}{2z} .$$ Now for any integer $k \in \mathbb{Z}$ let the 'generalised` Catalan numbers of type $k$ be the integer sequence $(c^{[k]}_n)_{n \in \mathbb{N}}$ with generating function $F_k(z)$ satisfying $$F_k(z) = \frac{1}{1-kzF(z)}.$$

For example, $(c^{[1]}_n)_{n \in \mathbb{N}}$ are just the (ordinary) Catalan numbers and $(c^{[2]}_n)_{n \in \mathbb{N}}$ are the central binomial coefficients. In these two cases we have exact formulas:

$$ c^{[1]}_n = \frac{1}{n+1} {2n \choose n}$$

and

$$ c^{[2]}_n = {2n \choose n} .$$

We can use these, together with Stirling's approximation, to show that

$$ c^{[1]}_n \sim \frac{4^n}{\sqrt{\pi n^3}} $$

and

$$ c^{[2]}_n \sim \frac{4^n}{\sqrt{\pi n}}.$$

For other $k$ I'm not aware of any similar formulas. The case $k=0$ is trivial as $c^{[0]}_n = 0$ for all $n > 0$. And I assume the remaining cases require singularity analysis, which is something I'm not really familiar with.

I've been told -- though I don't think I've ever seen a proof -- that when an integer sequence $(a_n)_{n \in \mathbb{N}}$ has a generating function $P(z)$ the asymptotic behaviour of the sequence depends on the smallest non-zero singularity $z_0$ of $P(z)$. In particular, I understand that in this case $a_n \sim \theta(n) |z_0|^{-n}$ for $\theta$ some subexponential function.

In the case of $F_k(z)$ as long as $k \neq 0$ there are two singularities: a pole at $z=\frac{k-1}{k^2}$ and a branch point at $z=\frac{1}{4}$. Since $$0 < \left|\frac{k-1}{k^2}\right| < \frac{1}{4} $$ for all integers $k$ other than those in $$I := \left\{ -4, -3, -2, -1, 0, 1, 2 \right\}$$ this means that for $k \notin I$ we should have $$c^{[k]}_n \sim \theta_k(n) \left( \frac{k^2}{k-1} \right)^n . $$

I'm not sure how in general one would go about finding $\theta_k$. In fact, by trial and error I've persuaded myself that -- again, for $k \notin I$ -- we have $$ c^{[k]}_n \sim \frac{k-2}{k-1} \left( \frac{k^2}{k-1} \right)^n $$ but again I'm not sure how to prove this to be true.

The remaining cases should, I assume, be of the form $c^{[k]}_n \sim \theta_k(n) 4^n$. This is true for $k=1$ and $k=2$ (shown above). And it's apparently true for the case $k=-1$, as Fung Lam (on the OEIS) gives the estimate $$c^{[-1]}_n \sim - \frac{4^n}{9 \sqrt{\pi n^3}}.$$

I've not been able to even guess what the subexponential term should be for the remaining three cases.

In summary then, I really have two questions:

  1. Are the particular estimates for the asymptotic growth of $c^{[k]}_n$ that I suggest above correct? Is anything known about the cases $k \in \{-4,-3,-2\}$?
  2. In general, how can I derive expressions for the asymptotic behaviour of an integer sequence if I know its generating function? (I suspect what I'm really looking for here is the name of a useful textbook...)
$\endgroup$
  • $\begingroup$ The textbook part is easy -- Analytic Combinatorics by Flajolet & Sedgewick. $\endgroup$ – Marko Riedel Aug 9 '17 at 22:31
1
$\begingroup$

The references here are to the book Analytic Combinatorics by Flajolet and Sedgewick. Suppose we have

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

and we are interested in the asymptotics of the coefficients of

$$F_k(z) = \frac{1}{1-kzF(z)}.$$

We restrict to $k\ge 3$ since $k=1$ and $k=2$ have closed forms in terms of binomial coefficients (ordinary Catalan numbers, central binomial coefficients). We obtain

$$\frac{1}{1-k(1-\sqrt{1-4z})/2} = \frac{1}{1-k/2+k\sqrt{1-4z}/2} \\ = \frac{1-k/2-k\sqrt{1-4z}/2}{(1-k/2)^2-k^2(1-4z)/4} = \frac{1-k/2-k\sqrt{1-4z}/2}{1-k+k^2z} \\ = \frac{1}{1-k} \frac{1-k/2-k\sqrt{1-4z}/2}{1-zk^2/(k-1)}.$$

We thus obtain for the desired coefficient the closed form

$$\frac{k-2}{2k-2} \frac{k^{2n}}{(k-1)^n} + \frac{k}{2k-2} [z^n] \frac{\sqrt{1-4z}}{1-zk^2/(k-1)}.$$

We require the asymptotics of the remaining coefficient. Now the square root term has radius of convergence $1/4$ and the rational term $(k-1)/k^2.$ Furthermore with $k\ge 3$ we have $1/4 \gt (k-1)/k^2.$ We are thus justified in applying Theorem VI.12 ("elementary methods") for our purpose, taking

$$\alpha = 1/4 \quad\text{and}\quad \beta = (k-1)/k^2, \quad\text{as well as} \\ a(z) = \sqrt{1-4z} \quad\text{and}\quad b(z) = \frac{1}{1-zk^2/(k-1)}$$

We get for the asymptotics

$$a(\beta) [z^n] b(z) = \sqrt{1-4(k-1)/k^2} \frac{k^{2n}}{(k-1)^n}.$$

Joining the two terms we find

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2}\frac{1}{k-1} \left(k-2 + k \sqrt{1-4(k-1)/k^2}\right) \left(\frac{k^2}{k-1}\right)^n.}$$

The coefficient on the exponential is close to one for $k$ large. What we see here is that the two contributions were of the same order and we may not omit either one of them. Consulting the quoted text we see that in order for the proof to go through the value $\beta$ must retain its sign (as opposed to merely being the radius of convergence, which is positive). This means the above result also holds for $k\le -5.$

Remaining case is $-4\le k\le -1.$ We observe that $a(z)$ and $b(z)$ have reversed their roles and we require

$$[z^n] \sqrt{1-4z} = [(-z)^n] \sqrt{1+4z} = (-1)^n 4^n {1/2\choose n} = (-1)^n \frac{1}{2n} 4^n {-1/2\choose n-1} \\ = (-1)^n \frac{1}{2n!} 4^n \prod_{j=0}^{n-2} (-1/2-j) = - \frac{1}{2n!} 2^{n+1} \prod_{j=0}^{n-2} (2j+1) \\ = - \frac{1}{n!} 2^n \frac{(2n-3)!}{(n-2)! 2^{n-2}} = - \frac{4}{n} {2n-3\choose n-1}.$$

We get for the asymptotics

$$\frac{k-2}{2k-2} \frac{k^{2n}}{(k-1)^n} - \frac{k}{2k-2} \frac{1}{1-k^2/(k-1)/4} \frac{4}{n} {2n-3\choose n-1}$$

or

$$\bbox[5px,border:2px solid #00A000]{ \frac{k-2}{2k-2} \frac{k^{2n}}{(k-1)^n} + \frac{8k}{(k-2)^2} \frac{1}{n} {2n-3\choose n-1}.}$$

Now for the binomial coefficient we have

$$\frac{(2n-3)!}{n! (n-2)!} = \frac{(n+1)n(n-1)}{2n(2n-1)(2n-2)} \frac{1}{n+1} {2n\choose n} \sim \frac{1}{8} \frac{4^n}{n^{3/2} \sqrt{\pi}}.$$

and we have the alternate asymptotic

$$\bbox[5px,border:2px solid #00A000]{ \frac{k-2}{2k-2} \frac{k^{2n}}{(k-1)^n} + \frac{k}{(k-2)^2} \frac{4^n}{n^{3/2} \sqrt{\pi}}.}$$

The modulus of $k^2/(k-1)$ with $k$ in the given range is less than $4$ and hence the second term that originates with the binomial coefficient dominates eventually.

$\endgroup$

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.