A q-CATALAN-NUMBERS-DETERMINANT

Ö. EĞECIOĞLU^{∗} AND C. KRATTENTHALER^{†}

Abstract. We compute a determinant involving Carlitz’s q-Catalan numbers.

Let C_{n}(q) be defined by C_{0}(q) = 1 and

C_{n}(q) = ∑_{k=0}^{n−1} q^{k}C_{k}(q)C_{n−k−1}(q),  n ≥ 1.  (1)

From [2, Eq. (2.1)],^{1} one can derive the expansion

1 = ∑_{n=0}^{∞}(−1)^{n}q^{−\binom{n}{2}}C_{n}(q)z^{n}(−z; q^{−1})_{n+1}.  (2)

The purpose of this note is to prove the following theorem. It has recently been reproved by Cigler [1] using completely different means. In fact, Cigler is able to embed the result below into a wider framework and is thereby able to establish several similar theorems — some already known, some new.

Theorem 1. For all non-negative integers n, we have

det_{0≤i,j≤n} (∑_{m=0}^{i+j} C_{i+j−m}(q)x^{m}) = q^{n(n−1)(4n+1)/6} ∑_{k=0}^{n}(−1)^{k}q^{(n−k)^{2}} [\begin{matrix}n + k \\ n − k \end{matrix}] x^{k}. (3)

Proof. We start by subtracting x times row i − 1 from row i, i = n, n − 1, …, 1 (in this order!), in the matrix of which we want to compute the determinant. As a result, we obtain that the determinant on the left-hand side of (3) is equal to

det_{0≤i,j≤n} (\begin{matrix}∑_{m=0}^{j} C_{j−m}(q)x^{m} & i = 0 \\ C_{i+j}(q) & i ≥ 1 \end{matrix}) .  (4)

Next we replace column j by

(column j) − ∑_{s=0}^{j−1} q^{j−s−1}C_{j−s−1}(q) · (column s),

2010 Mathematics Subject Classification. Primary 15A15; Secondary 05A15 05A19 05A30.

Key words and phrases. Carlitz q-Catalan numbers, non-intersecting lattice paths.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

1Our C_{n}(q) is denoted by C̃_{n}(q) in [2]. The relation between these q-Catalan numbers and the ones in [2, Eq. (2.1)] is described in [2, Eq. (2.3)].

j = 0, 1, …, n. Clearly, this can be achieved by elementary column operations, which do not change the value of the determinant. Thereby, the determinant in (4) is transformed into

det_{0≤i,j≤n} (\begin{matrix}∑_{m=0}^{j} C_{j−m}(q)x^{m} − ∑_{s=0}^{j−1} q^{j−s−1}C_{j−s−1}(q) ∑_{m=0}^{s} C_{s−m}(q)x^{m} & i = 0 \\ C_{i+j}(q) − ∑_{s=0}^{j−1} q^{j−s−1}C_{j−s−1}(q)C_{i+s}(q) & i ≥ 1 \end{matrix})

= det_{0≤i,j≤n} (\begin{matrix}∑_{m=0}^{j} C_{j−m}(q)x^{m} − ∑_{m=0}^{j−1} x^{m} ∑_{s=m}^{j−1} q^{j−s−1}C_{j−s−1}(q)C_{s−m}(q) & i = 0 \\ C_{i+j}(q) − ∑_{s=0}^{j−1} q^{j−s−1}C_{j−s−1}(q)C_{i+s}(q) & i ≥ 1 \end{matrix})

= det_{0≤i,j≤n} (\begin{matrix}x^{j} & i = 0 \\ C_{i+j}(q) − ∑_{s=0}^{j−1} q^{j−s−1}C_{j−s−1}(q)C_{i+s}(q) & i ≥ 1 \end{matrix}) ,

where we used (1) to obtain the last line. We may expand this determinant along the first row to arrive at

∑_{k=0}^{n}(−1)^{k}x^{k} det_{1≤i≤n, 0≤j≤n−1} (C_{i+j+χ(j≥k)}(q)

− ∑_{s=0}^{j+χ(j≥k)−1} q^{j+χ(j≥k)−s−1}C_{j+χ(j≥k)−s−1}(q)C_{i+s}(q)), (5)

where χ(S) = 1 if S is true and χ(S) = 0 otherwise.

We now focus our attention on the coefficient of (−x)^{k} in this expansion, that is, on the determinant

det_{0≤i,j≤n−1} (C_{i+j+χ(j≥k)+1}(q) − ∑_{s=0}^{j+χ(j≥k)−1} q^{j+χ(j≥k)−s−1}C_{j+χ(j≥k)−s−1}(q)C_{i+s+1}(q)).

(6)

(The reader should note that we did the replacement i → i + 1 compared to (5).) By using column operations, working from the left to the right, this determinant can be reduced to

det_{0≤i,j≤n−1} (\begin{matrix}C_{i+j+1}(q) & j < k \\ C_{i+j+2}(q) − ∑_{s=k}^{j} q^{j−s}C_{j−s}(q)C_{i+s+1}(q) & j ≥ k \end{matrix}) .

Now, for j = k, k + 1, n − 1, we replace column j by

∑_{ℓ=k}^{j} C_{j−ℓ}(q)(column ℓ).

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; A_{0}; A_{1}; A_{2}; A_{3}; A_{4}; E_{0}; E_{1}; E_{2}; E_{3}; E_{4}] Figure 1

Again, this can be achieved by elementary column operations. In this manner, we see that the determinant in (6) is equal to

det_{0≤i,j≤n−1} (\begin{matrix}C_{i+j+1}(q) & j < k \\ \begin{matrix}∑_{ℓ=k}^{j} C_{j−ℓ}(q)C_{i+ℓ+2}(q) \\ − ∑_{ℓ=k}^{j} C_{j−ℓ}(q) ∑_{s=k}^{ℓ} q^{ℓ−s}C_{ℓ−s}(q)C_{i+s+1}(q) \end{matrix} & j ≥ k \end{matrix})

= det_{0≤i,j≤n−1} (\begin{matrix}C_{i+j+1}(q) & j < k \\ \begin{matrix}∑_{ℓ=k}^{j} C_{j−ℓ}(q)C_{i+ℓ+2}(q) \\ − ∑_{s=k}^{j} C_{i+s+1}(q) ∑_{ℓ=s}^{j} C_{j−ℓ}(q)q^{ℓ−s}C_{ℓ−s}(q) \end{matrix} & j ≥ k \end{matrix})

= det_{0≤i,j≤n−1} (\begin{matrix}C_{i+j+1}(q) & j < k \\ ∑_{ℓ=k}^{j} C_{j−ℓ}(q)C_{i+ℓ+2}(q) − ∑_{s=k}^{j} C_{i+s+1}(q)C_{j−s+1} & j ≥ k \end{matrix})

= det_{0≤i,j≤n−1} (\begin{matrix}C_{i+j+1}(q) & j < k \\ C_{i+j+2}(q) − C_{i+k+1}(q)C_{j−k+1} & j ≥ k \end{matrix}) ,

where we used (1) to arrive at the next-to-last line.

The next step is to expand the last determinant by linearity in columns k, k + 1, …, n − 1. In theory, this produces 2^{n−k} terms. However, since choosing the term C_{i+k+1}(q)C_{j−k+1} for two different j’s will result in a vanishing determinant, only very few terms survive. To be precise, these are

det_{0≤i,j≤n−1} (C_{i+j+χ(j≥k)+1}(q)) − ∑_{ℓ=k}^{n−1} C_{ℓ−k+1}(q) det_{0≤i,j≤n−1} (\begin{matrix}C_{i+j+χ(j≥k)+1}(q) & j ≠ ℓ \\ C_{i+k+1}(q) & j = ℓ \end{matrix})

= ∑_{ℓ=k−1}^{n−1}(−1)^{ℓ−k+1}C_{ℓ−k+1}(q) det_{0≤i,j≤n−1} (C_{i+j+χ(j≥ℓ+1)+1}(q))

= ∑_{ℓ=k}^{n}(−1)^{ℓ−k}C_{ℓ−k}(q) det_{0≤i,j≤n−1} (C_{i+j+χ(j≥ℓ)+1}(q)) .  (7)

By the Lindström–Gessel–Viennot theorem ([4, Lemma 1], [3, Theorem 1]), the determinant in (7) can be given a combinatorial interpretation: it is equal to the generating function ∑_{P} w(P), where the sum is over all families P = (P_{0}, P_{1}, …, P_{n−1}) of nonintersecting paths consisting of up-steps and down steps, where P_{i} is a path from (−2i−2, 0) to (2i+2χ(j ≥ ℓ)) never running below the x-axis, i = 0, 1, …, n−1, and where the weight w(P) is q^{A(P_{0})+···+A(P_{n−1})}, with A(P) denoting the area under the path P. An example with n = 5 and ℓ = 2 is given in Figure 1.

By looking at the last up-step of paths ℓ, ℓ + 1, …, n − 1, it is not difficult to see that this generating function equals

q^{∑_{t=1}^{n−1} ∑_{s=1}^{t}(4s−1)}q^{2 ∑_{s=ℓ}^{n−1}(s−ℓ)} ∑_{0≤k_{ℓ}≤···≤k_{n−1}} q^{k_{ℓ}+···+k_{n−1}}

= q^{n(n−1)(4n+1)/6}q^{(n−ℓ)(n−ℓ−1)} [\begin{matrix}n + ℓ + 1 \\ n − ℓ \end{matrix}] .

Therefore, if we substitute this in (7), and if we subsequently replace ℓ by ℓ + k, then we obtain the expression

∑_{ℓ=0}^{n−k}(−1)^{ℓ}q^{n(n−1)(4n+1)/6}q^{(n−k−ℓ)(n−k−ℓ−1)}C_{ℓ}(q) [\begin{matrix}n + k + ℓ + 1 \\ n − k − ℓ \end{matrix}] .  (8)

Using the q-binomial theorem, we have

⟨z^{m}⟩ (−z; q)_{M} = q^{\binom{m}{2}} [\begin{matrix}M \\ m \end{matrix}] ,

where (α; q)_{M} := (1 − α)(1 − αq) ⋯ (1 − αq^{M−1}) for M ≥ 1 and (α; q)_{0} := 1, and where ⟨z^{m}⟩ h(z) denotes the coefficient of z^{m} in the formal Laurent series h(z). Hence, we can rewrite (8) as

∑_{ℓ=0}^{n−k}(−1)^{ℓ}q^{n(n−1)(4n+1)/6}q^{\binom{n−k−ℓ}{2}}C_{ℓ}(q) ⟨z^{n−k−ℓ}⟩ (−z; q)_{n+k+ℓ+1}

= ∑_{ℓ=0}^{n−k}(−1)^{ℓ}q^{n(n−1)(4n+1)/6}q^{\binom{n−k−ℓ}{2}}C_{ℓ}(q)

· q^{(n−k−ℓ)(n+k+ℓ)} ⟨z^{n−k−ℓ}⟩ (−zq^{−n−k−ℓ}; q)_{n+k+ℓ+1}

= ⟨z^{n−k}⟩ (−z; q^{−1})_{n+k}q^{n(n−1)(4n+1)/6}q^{\binom{n}{2}+n(n−k)−\binom{k}{2}}

× ∑_{ℓ=0}^{n−k}(−1)^{ℓ}q^{−\binom{ℓ}{2}−ℓ(n+k)}C_{ℓ}(q)z^{ℓ}(−zq^{−n−k}; q^{−1})_{ℓ}

= ⟨z^{n−k}⟩ (−z; q^{−1})_{n+k}q^{n(n−1)(4n+1)/6}q^{\binom{n}{2}+n(n−k)−\binom{k}{2}}

= q^{n(n−1)(4n+1)/6}q^{(n−k)^{2}} [\begin{matrix}n + k \\ n − k \end{matrix}] ,

where we used (2) to obtain the next-to-last line. To summarize: we have proved that the coefficient of (−x)^{k} in (5) is equal to this last expression. In its turn, expression (5) is equal to our determinant on the left-hand side of (3). This completes the proof of the theorem. □

References

[1] J. Cigler, Hankel determinants of some polynomial sequences, preprint, arχiv:1211.0816.

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

[3] I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint, 1989, available

   at http://www.cs.brandeis.edu/~ira.

[4] B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90.

∗Department of Computer Science, University of California at Santa Barbara, CA 93106-5110

WWW: http://www.cs.ucsb.edu/~omer/.

†Fakultät für Mathematik, Universität Wien, Nordbergstrasze 15, A-1090 Vi-

enna, Austria. WWW: http://www.mat.univie.ac.at/~kratt.