MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

q-Catalan numbers are defined recurrently as C0=1, $C_{N+1}=\sum_{k=0}^N q^k C_k C_{N-k}$.

What can be said about the asymptotics of Cn when 0<q<1?

P.S. In the case q>1 it is known that as n goes to infinity, $q^{-{n\choose 2}}C_n(q)$ tends to the partition function $\prod_{i=1}^\infty\frac1{1-q^{-i}}$. However, this doesn't help in the case 0<q<1.

share|cite|improve this question
up vote 3 down vote accepted

Re Leonid's comment on a previous answer.

If the ratios $C_{n+1}/C_n$ converge, their limit $c(q)$ is such that $C(q,q/c(q))=c(q)$. Equivalently, $1/c(q)$ is the radius of convergence of the series $z\mapsto C(q,z)$. Or, writing $C(q,\cdot)$ as the ratio of two $q$-hypergeometric functions, one can show that $F(q,1/c(q))=0$, where $$ F(q,z)=\sum_{n\ge0}(-1)^nq^{n^2-n}z^n/(q)_n. $$ This implies that $c(q)$ is the sum of a series in $q$ with integer coefficients, whose signs seem to be alternating starting with the coefficient of $q$. The first terms are $$ c(q)=1+q+q^3-q^4+2q^5-3q^6+6q^7-12q^8+25q^9-52q^{10}+111q^{11}+\ldots $$ The function $q\mapsto c(q)$ is nondecreasing on $q\ge0$, obvious values are $c(0)=1$ and $c(1)=4$, and as a holomorphic function, $c(\cdot)$ might have a pole inside the unit disk at about $q\approx-.4$. But apart from that...

share|cite|improve this answer
Well, this really counts as a nice answer. Numerically I perfectly see the above series for $c(q)$, and also the pole. The coefficients of the Taylor expansion of $c(q)$ at zero stabilize. – Leonid Petrov Oct 31 '10 at 5:41

It's not hard to compute numerical values. If you do this, in the regime $0 < q < 1$ it looks like $C_n$ grows exponentially, i. e. $C_n \sim \alpha_q \beta_q^n$ for some constants $\alpha_q$ and $\beta_q$ which depend on q.

Unfortunately, I don't know what $\alpha_q$ and $\beta_q$ are. For example, when q = 1/2 the ratio $C_n/C_{n-1}$ approaches a constant which is approximately 1.6022827223; I claim this is $\beta_{1/2}$. Then $C_{50}/\beta_{1/2}^{50} = 0.5757566503$, which I claim is $\alpha_{1/2}$. Neither of these constants appears in the inverse symbolic calculator.

The generating function $C(q,z) = C_0 + C_1 z + C_2 z^2 + \ldots$, where the $C_n$ are $q$-Catalan numbers, ought to satisfy some functional equation, and then one could use techniques from singularity analysis (see, for example, Analytic Combinatorics by Flajolet and Sedgewick). But I am having trouble finding that functional equation.

share|cite|improve this answer
Looks to me like the functional equation is C(q,z)= 1 + zC(q,qz)C(q,z). I don't know anything about how to extract information about asymptotics from this, though. – Hugh Thomas Nov 30 '09 at 23:08
Slightly off topic: may I advertise the guessing package included in FriCAS again? guessADE(q)([c n for n in 0..10], debug==true) finds the functional equation given by Hugh... – Martin Rubey Oct 28 '10 at 17:05

Frohman and Bartoszynska did a lot of work on the asymptotics of the quantum $6j$-symbols over the last 5 to 7 years. I think their papers on these matters are found on the arxiv. This is where one should look first.

share|cite|improve this answer
But does that include $q$-Catalan numbers? – Greg Kuperberg Nov 30 '09 at 15:19
Good question, and I don't know for sure. As I recall they did an extensive bit of analysis in that work. – Scott Carter Nov 30 '09 at 16:01

Indeed, $C_n^{1/n}$ converges. Call the limit $\beta_q$ like Michael Lugo did. One can show that $\beta_q\ge 1+q$ for every positive $q$, that $\beta_q\le 2(1+q)$ and $\beta_q\le 1/(1-q)$ for every $q$ in $(0,1)$, that $\beta_q$ is related to the smallest positive zero of a given $q$-hypergeometric function, and various other estimates. The $q$-Catalan numbers are related to some properties of products of correlated Wigner matrices just like the ordinary Catalan numbers describe the (statistical properties of the) spectrum of (large random) Wigner matrices. This is explained in this paper (caveat: I am one of the authors).

share|cite|improve this answer
Thank you for the answer, I will try to read the paper. However, the fact that $C_n^{1/n}$ converges also follows from random trees (the theory of Aldous' CRT) and I already knew it. It does not help, however. But nevertheless, thanks for the interest in this old question. – Leonid Petrov Oct 29 '10 at 4:19
OK. Sooo... you might care to state more precisely the kind of property of the $C_n$s you are interested in. :-) – Did Oct 29 '10 at 15:30
Actually, the time I asked the question I wanted to know the limit $C_{n+1}/C_n$ for a fixed $q$. Now you say that this lies in $q$-hypergeometric matters, and I know very little about these. So I think I need to investigate into that direction. – Leonid Petrov Oct 30 '10 at 16:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.