The Limiting Distribution of the Coefficients of the q-Catalan Numbers

William Y.C. Chen^{1}, Carol J. Wang^{2}, and Larry X.W. Wang^{3} Center for Combinatorics, LPMC-TJKLC Nankai University, Tianjin 300071, P. R. China

1chen@nankai.edu.cn, ^{2}wangjian@cfc.nankai.edu.cn, 3wxw@cfc.nankai.edu.cn

Abstract

We show that the limiting distributions of the coefficients of the q-Catalan numbers and the generalized q-Catalan numbers are normal. Despite the fact that these coefficients are not unimodal for small n, we conjecture that for sufficiently large n, the coefficients are unimodal and even log-concave except for a few terms of the head and tail.

Keywords : Bernoulli number, q-Catalan number, unimodality, log-concavity, moment generating function.

1 Introduction

The main objective of this paper is to show that the limiting distribution of the coefficients of the q-Catalan numbers is normal. The Catalan numbers

C_{n} = \frac{1}{n + 1}\binom{2n}{n}

have many combinatorial interpretations, see Stanley [9]. The usual q-analog of the Catalan numbers is given by

C_{n}(q) := \frac{1}{[n + 1]}\left[{2n \atop n}\right],  (1.1)

where [n] = 1 + q + q^{2} + ⋯ + q^{n−1}, and

\left[{n \atop k}\right] = \frac{[n]!}{[k]![n − k]!}.

There are also other types of q-analogs of the Catalan numbers, see, for example, Andrews [2], Gessel and Stanton [4], Krattenthaler [5].

We also consider the limiting distribution of the coefficients of the quotient of two products of q-numbers, which includes the result for the q-Catalan numbers as a special case. We conclude this paper with two conjectures on the unimodality and log-concavity for almost all the coefficients of the q-Catalan numbers and the generalized q-Catalan numbers provided that n is sufficiently large.

2 The Limiting Distribution

In this section, we use the moment generating function technique to obtain the limiting distribution of the coefficients of the q-Catalan numbers. We introduce the random variable ξ_{n} corresponding to the probability generating function

ϕ_{n}(q) = C_{n}(q)/C_{n}.

As far as the computations are concerned, we will not need the following combinatorial interpretation of C_{n}(q). However, for completeness and for the sake of presentation, we would mention that ξ_{n} reflects the distribution of the major indices of Catalan words of length 2n, see, for example, [3]. We write

C_{n}(q) = ∑ m_{n}(k)q^{k}.

The following lemma is concerned with the expectation and variance of ξ_{n}.

Lemma 2.1 We have

E(ξ_{n}) = \frac{n(n − 1)}{2} and Var(ξ_{n}) = \frac{n(n − 1)(n + 1)}{6}.  (2.1)

Proof. By the definition of C_{n}(q), it is easy to check the following symmetry property of m_{n}(k):

m_{n}(k) = m_{n}(n(n − 1) − k).

Hence

E(ξ_{n}) = \frac{n(n − 1)}{2}.

Let

F = F (q) = ∏_{i=1}^{n−1}(1 + q + ⋯ + q^{n+i}) and G = G(q) = ∏_{i=1}^{n−1}(1 + q + ⋯ + q^{i}).

It is easily verified that C_{n}(q) = F/G. Since

C_{n}(q)′′|_{q=1} = (\frac{F′′}{G} − \frac{F G′′}{G^{2}} − \frac{2G′F′}{G^{2}} + \frac{2G^{′2}F}{G^{3}} )|_{q=1}

= \frac{1}{12}n(n − 1)(3n^{2} − n − 4) · C_{n},

we obtain

Var(ξ_{n}) = \frac{C_{n}(q)′′|_{q=1}}{C_{n}} + E(ξ_{n}) − E(ξ_{n})^{2} = \frac{1}{6}n(n − 1)(n + 1).

This completes the proof.

Lemma 2.2 When n → ∞, we have

∑_{k=2}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} ∑_{i=2}^{n} ((n + i)^{2k} − i^{2k}) → 0

uniformly for t from any bounded set, where B_{j}’s are the Bernoulli numbers and σ^{2} is the variance of ξ_{n} as given in (2.1).

Proof. The second summation can be expanded as follows:

∑_{i=2}^{n} ((n + i)^{2k} − i^{2k}) = ∑_{i=2}^{n} ∑_{j=1}^{2k} \binom{2k}{j}n^{j}i^{2k−j} = ∑_{j=1}^{2k} \binom{2k}{j} (∑_{i=2}^{n} n^{j}i^{2k−j}) .

For k > 1, the second factor in the preceding summation is bounded by the following integral:

∑_{i=2}^{n} n^{j}i^{2k−j} < n^{j} ∫_{1}^{n+1} t^{2k−j}dt = n^{j} · \frac{(n + 1)^{2k−j+1} − 1}{2k − j + 1}.

Consequently,

∑_{i=2}^{n} ((n + i)^{2k} − i^{2k}) < 2^{2k}(n + 1)^{2k+1} < 8^{2k}n^{2k+1}.

Since σ^{2} = \frac{n^{3}−n}{6} > \frac{n^{3}}{8} when n is sufficiently large, we have

σ^{−2k} ∑_{i=2}^{n} ((n + i)^{2k} − i^{2k}) < 64^{2k}n^{1−k} ≤ n^{−1/3}64^{2k}n^{−k/3},

for large n and k > 1. Thus

| ∑_{2∤k,k≥3}B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} ∑_{i=2}^{n} ((n + i)^{2k} − i^{2k})|

< n^{−1/3} ∑_{2∤k,k≥3}|B_{2k}|\frac{t^{2k}}{2k(2k)!}64^{2k}n^{−k/3}

= n^{−1/3} ∑_{2∤k,k≥3}|B_{2k}|\frac{(64tn^{− \frac{1}{6}} )^{2k}}{2k(2k)!} .

In view of the following asymptotic expansion of the Bernoulli numbers

|B_{2n}| ∼ \frac{2(2n)!}{(2π)^{2n}} ,

the convergent radius R of the series ∑_{2∤k,k≥3}|B_{2k}|\frac{t^{2k}}{2k(2k)!} equals 2π. Since t is

from a bounded set, when n is large enough, the series

∑_{2∤k,k≥3}|B_{2k}|\frac{(64tn^{− \frac{1}{6}} )^{2k}}{2k(2k)!}

converges. Moreover, it is evident that 64tn^{− \frac{1}{6}} < 1, we can bound the above summation by the constant

M_{1} = ∑_{2∤k,k≥3}|B_{2k}|\frac{1}{2k(2k)!}.

Similarly, it can be deduced that

∑_{2|k,k≥2} B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} ∑_{i=2}^{n} ((n + i)^{2k} − i^{2k}) < \frac{M_{2}}{n^{\frac{1}{3}}} ,

where M_{2} = ∑_{2|k,k≥2} B_{2k} \frac{1}{2k(2k)!} is a constant. Hence

∑_{k=2}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} ∑_{i=2}^{n} ((n + i)^{2k} − i^{2k}) < \frac{M_{1} + M_{2}}{n^{1/3}} ,

which tends to zero as n → ∞. This completes the proof.

Theorem 2.3 When n → ∞, the random variable

η_{n} = \frac{ξ_{n} − E(ξ_{n})}{Var(ξ_{n})^{\frac{1}{2}}}

has the standard normal distribution.

Proof. Let M_{n}(q) denote the moment generating function of ξ_{n}. Then we have M_{n}(q) = ϕ_{n}(e^{q}), see Sachkov [7]. Hence

M_{n}(q) = \frac{n + 1}{\binom{2n}{n}} \frac{1 − e^{q}}{1 − e^{(n+1)q}} · ∏_{i=1}^{n} \frac{1 − e^{(n+i)q}}{1 − e^{iq}}

= ∏_{i=2}^{n} \frac{i}{n + i} · ∏_{i=2}^{n} \frac{1 − e^{(n+i)q}}{1 − e^{iq}}

= ∏_{i=2}^{n} \frac{(1 − e^{(n+i)q})/(n + i)}{(1 − e^{iq})/i}

= exp \{\frac{1}{2} ∑_{i=2}^{n} ((n + i)q − iq)\} ∏_{i=2}^{n} \frac{(e^{(n+i)q/2} − e^{−(n+i)q/2})/\frac{n+i}{2}}{(e^{iq/2} − e^{−iq/2})/\frac{i}{2}}

= exp \{\frac{n(n − 1)q}{2} \} ∏_{i=2}^{n} \frac{sinh ((n + i)q/2) /\frac{n+i}{2}}{sinh (iq/2) /\frac{i}{2}} .

Recalling the following relation on the Bernoulli numbers [6]

ln (\frac{sinh(x/2)}{x/2}) = ∑_{k=1}^{∞} B_{2k} \frac{x^{2k}}{2k(2k)!},  (2.2)

we find that

ln M_{n}(q) = \frac{n(n − 1)}{2}q + ∑_{i=2}^{n} (ln (\frac{sinh((n + i)q/2)}{(n + i)/2}) − ln (\frac{sinh(iq/2)}{i/2}))

= \frac{n(n − 1)}{2}q + ∑_{k=1}^{∞} B_{2k} \frac{q^{2k}}{2k(2k)!} ∑_{i=2}^{n} ((n + i)^{2k} − i^{2k}) .

Setting q = t/σ, where σ is the standard deviation of ξ_{n} as given in Theorem 2.1, we are led to the expansion

ln M_{n}(t/σ) = \frac{n(n − 1)t}{2σ} + ∑_{k=1}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} ∑_{i=2}^{n} ((n + i)^{2k} − i^{2k}) .

Applying Lemma 2.2, we have, when n → ∞,

∑_{k=2}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} ∑_{i=2}^{n}((n + i)^{2k} − i^{2k}) → 0

uniformly for t from any bounded set. Finally,

lim_{n→∞} M_{n}(t/σ) exp \{−\frac{n(n − 1)t}{2σ}\}

= lim_{n→∞} exp \{∑_{k=1}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} ∑_{i=2}^{n} ((n + i)^{2k} − i^{2k})\}

= lim_{n→∞} exp \{B_{2} \frac{t^{2}}{2(2)!σ^{2}} ∑_{i=2}^{n} ((n + i)^{2} − i^{2})\}
= e^{t^{2}/2},

which coincides with the moment generating function of the standard normal distribution. Employing Curtiss’ theorem [7], we reach the conclusion that η_{n} has the standard normal distribution when n approaches infinity.

3 A General Setting

In this section, we will determine the limiting distribution of the coefficients of a quotient of products of q-numbers and will give two special cases.

Theorem 3.1 Let a_{1}, a_{2}, a_{3}, … and b_{1}, b_{2}, b_{3}, … be two sequences of positive numbers, and let

ϕ_{n}(x) = ∑_{k} p_{n}(k)x^{k} = \frac{(1 − q^{a_{1}})(1 − q^{a_{2}}) ⋯ (1 − q^{a_{n}})}{(1 − q^{b_{1}})(1 − q^{b_{2}}) ⋯ (1 − q^{b_{n}})}.

Suppose that ξ_{n} is the random variable corresponding to the generating function ϕ_{n}(x), that is,

P (ξ_{n} = k) = \frac{p_{n}(k)}{∑_{k} p_{n}(k)}.

Then ξ_{n} is normally distributed as n → ∞, if and only if for k > 1

∑_{k=1}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!} (∑_{i=1}^{n}(a_{i}^{2k} − b_{i}^{2k})) \frac{1}{(∑_{i=1}^{n}(a_{i}^{2} − b_{i}^{2}))^{k}} → 0 as n → ∞.

Proof. The expectation of ξ_{n} is easy to compute, as given below:

E(ξ_{n}) = ϕ_{n}(x)′_{q=1} = \frac{1}{2} ∑_{i=1}^{n} (a_{i} − b_{i}) .

Proceeding analogously as in the proof of Theorem 2.1, we find

σ^{2} = Var(ξ_{n}) = \frac{1}{12} ∑_{i=1}^{n} (a_{i}^{2} − b_{i}^{2}) .  (3.1)

Hence,

B_{2} \frac{t^{2}}{2(2)!σ^{2}} (∑_{i=1}^{n}(a_{i}^{2} − b_{i}^{2})) = \frac{1}{6} · \frac{t^{2}}{4 · \frac{1}{12} (∑_{i=1}^{n}(a_{i}^{2} − b_{i}^{2}))} · (∑_{i=1}^{n}(a_{i}^{2} − b_{i}^{2})) = \frac{t^{2}}{2} .

By the same procedure as in the proof of Theorem 2.3, we obtain

lim_{n→∞} M_{n}(t/σ) exp \{\frac{1}{2} ∑_{i=1}^{n} (a_{i}^{2k} − b_{i}^{2k})\}

= e^{t^{2}/2} lim_{n→∞} exp \{∑_{k=2}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} (∑_{i=1}^{n} (a_{i}^{2k} − b_{i}^{2k}))\} .

It follows that the limiting distribution of p_{n}(k) is normal if and only if

∑_{k=2}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!σ^{2k}} (∑_{i=1}^{n} (a_{i}^{2k} − b_{i}^{2k})) → 0 as n → ∞,  (3.2)

for t from any bounded set. By virtue of the variance formula (3.1), the condition (3.2) is equivalent to

∑_{k=1}^{∞} B_{2k} \frac{t^{2k}}{2k(2k)!} \begin{matrix}∑_{i=1}^{n} & (a_{i}^{2k} − b_{i}^{2k}) \\ (∑_{i=1}^{n} (a_{i}^{2} − b_{i}^{2})) & k \end{matrix} → 0 as n → ∞  (3.3)

for t from any bounded set. Thus (3.2) is verified. This completes the proof.

Corollary 3.2 Let p_{n}(k) be given as in the above theorem. Suppose that for k ≥ 2, there exist constants α > 0, β < 0 and γ < 0 such that

\begin{matrix}∑_{i=1}^{n} & (a_{i}^{2k} − b_{i}^{2k}) \\ (∑_{i=1}^{n}(a_{i}^{2} − b_{i}^{2})) & k \end{matrix} < n^{γ}(αn^{β})^{2k},  (3.4)

for t from any bounded set. Then the limiting distribution of p_{n}(k) is normal.

Proof. Note that the convergent radius R of the series

∑_{2∤k,k≥3}|B_{2k}|\frac{x^{2k}}{2k(2k)!}

is 2π. If (3.4) holds for k > 1, then for t from any bounded set, and for sufficiently large n, we have

|t^{2k} ∑_{i=1}^{n} (a_{i}^{2k} − b_{i}^{2k}) /σ^{2k}| ≤ n^{γ}(tαn^{β})^{2k},

where tαn^{β} < 2π. It is clear that n^{γ} → 0 since γ < 0.

If we choose α = 32\sqrt{3}/3, 2β = γ = −\frac{1}{3}, Theorem 3.2 contains Theorem 2.3 as a special case. We now give two more examples. One is the following q-analog of the Catalan numbers

c_{n}(q) = \frac{[2]}{[2n]}\left[{2n \atop n − 1}\right],

which are symmetric and unimodal, see Stanley [].

Using Theorem 3.1, we reach the following assertion.

Corollary 3.3 The distribution of the coefficients in c_{n}(q) is asymptotically normal.

Proof. First, we write c_{n}(q) in the following form:

\frac{∏_{i=3}^{n}(1 − q^{n+i−1})}{(1 − q) ∏_{i=3}^{n−1}(1 − q^{i})},

Set a_{1} = a_{2} = 1, a_{i} = n + i − 1, 3 ≤ i ≤ n, and b_{1} = b_{2} = 1, b_{3} = 1, b_{i} = i − 1, 4 ≤ i ≤ n. Then we have

∑_{i=1}^{n} (a_{i}^{2k} − b_{i}^{2k}) = (a_{3}^{2k} − b_{3}^{2k}) + ∑_{i=4}^{n} (a_{i}^{2k} − b_{i}^{2k})

= (n + 2)^{2k} − 1 + ∑_{i=3}^{n−1} ((n + i)^{2k} − i^{2k})

and

(∑_{i=1}^{n}(a_{i}^{2} − b_{i}^{2}))^{k} = ((n + 2)^{2} − 1 + ∑_{i=3}^{n−1} ((n + i)^{2} − i^{2}))^{k}
= (n − 1)^{k}(n + 1)^{k}(2n − 3)^{k}.

By the same arguments as in the proof of Lemma 2.2, we may set α = 32\sqrt{3}/3 and 2β = γ = −\frac{1}{3} such that the condition (3.4) is satisfied. Therefore, Theorem 3.1 implies the limiting distribution of the coefficients of c_{n}(q).

The m-Catalan numbers are defined by

C_{n,m} = \frac{1}{(m − 1)n + 1}\binom{mn}{n},

for n ≥ 1. Accordingly, the generalized q-Catalan numbers are given by

C_{n,m}(q) = \frac{1}{[(m − 1)n + 1]}\left[{mn \atop n}\right].

Theorem 3.1 has the following consequence.

Corollary 3.4 The coefficients of the generalized q-Catalan numbers C_{n,m}(q) are normally distributed when n → ∞.

Proof. First, express C_{n,m}(q) as follows

∏_{i=2}^{n} \frac{1 − q^{(m−1)n+i}}{1 − q^{i}} .

Set a_{1} = 1, a_{i} = (m − 1)n + i, 2 ≤ i ≤ n, and b_{1} = 1, b_{i} = i, 2 ≤ i ≤ n. Then we have

∑_{i=1}^{n} (a_{i}^{2k} − b_{i}^{2k}) = ∑_{i=2}^{n} (a_{i}^{2k} − b_{i}^{2k}) = ∑_{i=2}^{n} ∑_{j=1}^{2k} \binom{2k}{j} ((m − 1)n)^{2k−j} i^{j}.

The same argument as in the proof of Lemma 2.2 yields the following bound

∑_{i=1}^{n} (a_{i}^{2k} − b_{i}^{2k}) < 8^{2k} ((m − 1) n)^{2k+1} .

Now,

(∑_{i=1}^{n}(a_{i}^{2} − b_{i}^{2}))^{k} = (∑_{i=2}^{n} (((m − 1)n + i)^{2} − i^{2}))^{k}
> (m − 1)^{2k}n^{2k}(n − 1)^{k}
> (m − 1)^{2k+1}n^{3k}/(2m)^{k}.

It follows that

\begin{matrix}∑ & {n \atop i=1} & (a_{i}^{2k} − b_{i}^{2k}) \\ (∑_{i=1}^{n}(a_{i}^{2} − b_{i}^{2})) & k \end{matrix} < (8\sqrt{2m})^{2k}n^{1−k}.

Again, by the same arguments as in the proof of Lemma 2.2, we may set α = 8\sqrt{2m} and 2β = γ = −\frac{1}{3} such that the condition (3.4) holds. Finally, we may use Theorem 3.1 to get the desired distribution.

4 Open Problems

While the q-Catalan numbers are not unimodal for small n, see Stanley [8], the limiting distribution suggests that the coefficients are almost unimodal in certain sense for sufficiently large n. Obviously, the first and the last term should not be taken into account otherwise one can never expect to have unimodality. In fact, an easy computation indicates that C_{n}(q) are unimodal for n ≥ 16.

Conjecture 4.1 The sequence {m_{n}(1), …, m_{n}(n(n − 1) − 1)} is unimodal when n is sufficiently large.

When n > 70, numerical evidence suggestive of a stronger conjecture:

Conjecture 4.2 There exists an integer t such that when n is sufficiently large, the sequence {m_{n}(t), …, m_{n}(n(n − 1) − t)} is log-concave, namely,

(m_{n}(k))^{2} ≥ m_{n}(k + 1)m_{n}(k − 1)

for t + 1 ≤ k ≤ n(n − 2) − t − 1. Moreover, the minimum value of t seems to be 75.

We also conjecture that similar properties hold for the generalized q-Catalan numbers.

Acknowledgments. We would like to thank B.H. Margolius for helpful comments. This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education, the Ministry of Science and Technology, and the National Science Foundation of China.

References

[1] H. Alzer, Sharp bounds for the Bernoulli numbers, Arch. Math. 74 (2000), 207–211.

[2] G.E. Andrews, Catalan numbers, q-Catalan numbers and hypergeometric series, J. Combin. Theory, Ser. A 44 (1987), 267–273.

[3] J. Fürlinger and J. Hofbauer, q-Catalan Numbers, J. Combin. Theory, Ser. A 40 (1985), 248–264.

[4] I. Gessel and D. Stanton, Applications of q-Lagrange inversion to basic hypergeometric series, Trans. Amer. Math. Soc. 177 (1983), 173–201.

[5] C. Krattenthaler, A new q-Lagrange formula and some applications, Proc. Amer. Math. Soc. 90 (1984), 338–344.

[6] B.H. Margolius, Permutations with inversions, J. Integer Seq. 4 (2001), A01.2.4.

[7] V.N. Sachkov, Probabilisitic Methods in Combinatorial Analysis, Cambridge University Press, New York, 1997.

[8] R.P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph Theory and Its Applications: East and West, Ann. New York Acad. Sci., Vol. 576, 1989, pp. 500–535.

[9] R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.