Séminaire Lotharingien de Combinatoire 63 (2010), Article B63d

HANKEL DETERMINANTS OF SOME SEQUENCES OF POLYNOMIALS

Sivaramakrishnan Sivasubramanian

Department of Mathematics Indian Institute of Technology, Bombay

                      email: krishnan@math.iitb.ac.in

Abstract. Ehrenborg gave a combinatorial proof of Radoux’s theorem which states that the determinant of the (n + 1) × (n + 1) dimensional Hankel matrix of exponential polynomials is x^{n(n+1)/2} ∏_{i=0}^{n} i!. This proof also shows the result that the (n + 1) × (n + 1) Hankel matrix of factorial numbers is ∏_{k=1}^{n}(k!)^{2}. We observe that two polynomial generalizations of factorial numbers also have interesting determinant values for Hankel matrices.

A polynomial generalization of the determinant of the Hankel matrix with entries being fixed-point free involutions on the set [2n] is given next. We also give a bivariate non-crossing analogue of a theorem of Cigler about the determinant of a similar Hankel matrix.

1. Introduction

For a sequence A = (a_{0}, a_{1}, a_{2}, …), consider the matrix

H = ( \begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ \\ a_{1} & a_{2} & a_{3} & ⋯ \\ a_{2} & a_{3} & a_{4} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

The nth Hankel matrix H_{n} of A is the top left (n + 1) × (n + 1) sized matrix. In this work, the a_{i}’s will be sequences of polynomials.

Let [n] = {1, 2, …, n}, and let SP_{n} be the set of set-partitions of [n]. For a set-partition π ∈ SP_{n}, let |π| be the number of parts in π. Consider the n-th exponential polynomial e_{n}(x) = ∑_{π} x^{|π|} = ∑_{k=0}^{n} S(n, k)x^{k}, where the S(n, k)’s are Stirling numbers of the second kind. The following is known (see Krattenthaler [7, Eqn. (3.54)] or Radoux [9]).

Theorem 1. The determinant of the nth Hankel matrix of exponential polynomials is

x^{n(n+1)/2} ∏_{k=1}^{n} k!.

Ehrenborg [4] gave a combinatorial proof of Theorem 1 which also proves the following classical result.

Theorem 2. The determinant of the nth Hankel matrix of the factorial numbers (i.e., det((i + j)!)_{0≤i,j≤n} ) is ∏_{k=1}^{n}(k!)^{2}.

We give generalizations of this result where we replace n! by polynomials p_{n}(.) in variables q, x and t . Consider the Eulerian polynomial Eu_{n}(x) = ∑_{k=0}^{n} A(n, k)x^{k} where A(n, k) is the number of permutations in S_{n} with k excedances (or k descents; see Section 2 for precise definitions), with Eu_{0}(x) = 1. In Section 2, we prove the following determinant evaluation.

Theorem 3. The determinant of the nth Hankel matrix with (i, j)-th entry (for 0 ≤ i, j ≤ n) being Eu_{i+j}(x) is x^{n(n+1)/2} ∏_{k=1}^{n} k!^{2}.

We also give a bivariate generalisation. Consider the Eulerian-Mahonian polynomial EI_{n}(q, t) = ∑_{π∈S_{n}} t^{exc(π)}q^{inv(π)} where again EI_{0}(q, t) = 1. Then, in Subsection 2.1, we prove the following result.

Theorem 4. The determinant of the nth Hankel matrix with (i, j)-th entry (for 0 ≤ i, j ≤ n) being EI_{i+j}(q, t) is

t^{n(n+1)/2}q^{n(n+1)(2n+1)/6} ∏_{k=1}^{n}([k]_{q}!)^{2}.

Krattenthaler [7] gives a survey of several techniques for evaluating Hankel determinants, one of which uses connections between Hankel determinants and continued fractions. Clarke, Steingrímsson and Zeng (see [2, Corollary 11]) give a continued fraction expansion for the polynomial EI_{n}(q, t) = ∑_{π∈S_{n}} t^{exc(π)}q^{inv(π)}. Thus, Theorem 4, and hence Theorem 3, is already established. In the present paper, we provide an alternative proof. As all other proofs in this paper, it is combinatorial in nature (i.e., it is based on an explicit sign reversing involutions). The virtue of such combinatorial proofs is that they make the result completely transparent, and this is the main purpose of our paper.

The proofs of all our results are modifications of Ehrenborg’s proof (see [4]), with the labelling of certain sets being the difference. One of our objectives is to give more examples where Ehrenborg’s proof method is applicable.

1.1. Fixed point free involutions. Let I_{2n} be the set of fixed-point free involutions on the set [2n]. We denote a_{n} = |I_{2n}|. Clearly, a_{n} = 1 · 3 · 5 ⋯ (2n − 1) (with a_{0} = 1). It is clear that any M ∈ I_{2n} can also be thought of as a perfect matching in K_{2n}, the complete graph on 2n vertices. Thus, we use the terms “fixed-point free involutions” and “perfect matchings” interchangeably.

A well studied statistic on perfect matchings is its crossing number, defined as follows. Let M = {(i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{n}, j_{n})} ∈ I_{2n} be a perfect matching. Define cross(M), its crossing number, to be cardinality of the set {i < j < k < l : (i, k), (j, l) ∈ M}. The crossing number occurs for example in an expansion for the pfaffian of a skew-symmetric matrix of order 2n (see Krattenthaler’s survey [7, p. 23]). Let Cr_{n}(q) = ∑_{M∈I_{2n}} q^{cross(M)} be the q-crossing polynomial, where Cr_{0}(q) = 1. Given these definitions, in Section 3, we prove the following theorem.

Theorem 5. The determinant of the nth Hankel matrix with (i, j)-th entry (for 0 ≤ i, j ≤ n) being Cr_{i+j}(q) is ∏_{k=1}^{n}[2k]_{q}!.

1.2. Non crossing partitions. Cigler [1] generalised Theorem 1 as follows. Wachs and White [16] defined four statistics on set-partitions, one of which they called rs(·). This, when added over set-partitions of [n] with k parts, gives a q-analogue of S(n, k), the Stirling numbers of the second kind. Let S_{q}(n, k) = ∑_{π∈SP_{n},|π|=k} q^{rs(π)}, where q is an indeterminate. Consider the polynomial E_{n}(q, x) = ∑_{k=0}^{n} x^{k}S_{q}(n, k) with E_{0}(q, x) = 1. Given these notations, the generalisation of Cigler [1] reads as follows.

Theorem 6. The determinant of the nth Hankel matrix with the (i, j)-th entry (for 0 ≤ i, j ≤ n) being E_{i+j}(x, q) is

x^{\binom{n+1}{2}}q^{\binom{n+1}{3}} ∏_{k=1}^{n}[k]_{q}!.

Ehrenborg [5] gave a combinatorial proof of Theorem 6 using juggling cards. It is known (see Simion [12]) that the number of non-crossing partitions of [n] is equal to the n-th Catalan number C_{n}. Recall that non-crossing partitions of [n] are those set-partitions π = B_{1}|B_{2}| ⋯ |B_{k} ∈ SP_{n} which have the property that for all 1 ≤ a < b < c < d ≤ n, whenever a, c ∈ B_{i} and b, d ∈ B_{j} for 1 ≤ i, j ≤ k, then i = j; i.e., the blocks do not “cross”. Let NC_{n} be the set of non-crossing partitions of [n]. The following is known (see Krattenthaler’s second survey [8, Theorem 33]) or Radoux [10]).

Theorem 7. The determinant of the nth Hankel matrix with the (i, j)-th entry (for 0 ≤ i, j ≤ n) being C_{i+j} is 1.

We prove the following analogue of Theorem 6 for non-crossing partitions, thereby generalising Theorem 7. Simion [12] considered Wachs and White’s rs(.) statistic when restricted to non-crossing partitions and gave an alternate definition for the statistic rs(π) when π ∈ NC_{n}. Let π = B_{1}|B_{2}| … |B_{k} ∈ NC_{n} be the standard representation of π, i.e., a representation where π has k blocks, B_{1}, …, B_{k} and, if the least elements of B_{i} are f_{i} for 1 ≤ i ≤ k, then f_{1} < f_{2} < ⋯ < f_{k}. Similarly, let ℓ_{i} be the largest element in B_{i} for 1 ≤ i ≤ k. Simion ([12, Lemma 2.1]) showed that

(1)  rs(π) = ( ∑_{i=1}^{k}(ℓ_{i} − f_{i})) − n + k.

Let NC(n, k) be the set of non-crossing set-partitions of [n] into k parts. It is known that the cardinality of NC(n, k) is given by the Narayana numbers \frac{1}{n} \binom{n}{k}\binom{n}{k−1} (see Edelman [3]). Consider the q-analogue of the Narayana numbers defined as NC_{q}(n, k) = ∑_{π∈NC(n,k)} q^{rs(π)} and the bivariate polynomial N_{n}(x, q) = ∑_{k=0}^{n} x^{k}NC_{q}(n, k). In Section 4, we prove the following theorem.

Theorem 8. The determinant of the nth Hankel matrix with the (i, j)-th entry (for 0 ≤ i, j ≤ n) being N_{i+j}(x, q) is x^{\binom{n+1}{2}}q^{2\binom{n+1}{3}}.

2. The Eulerian analogue

We recall that, given a permutation π = (π_{1}, π_{2}, …, π_{n}), an excedance is an index i such that π_{i} > i. The number of excedances of π is denoted as exc(π). It is well known (see [15]) that the excedance number of a permutation is an Eulerian statistic. Consider the n-th Hankel matrix E_{n} = (e_{i,j}) where e_{i,j} = Eu_{i+j}(x).

Proof of Theorem 3. Let R_{0}, R_{1}, …, R_{n} and C_{0}, C_{1}, …, C_{n} be pairwise disjoint sets with |R_{i}| = |C_{i}| = i. Let P be the set of tuples (σ, π_{0}, π_{1}, …, π_{n}), where σ is a permutation on the set [n_{0}] = {0, 1, …, n} and π_{i} is a permutation of R_{i} ∪ C_{σ(i)}. It is clear that only such tuples index terms in the determinant evaluation of PP_{n} and that such a tuple contributes (−1)^{inv(σ)}x^{∑_{i=0}^{n} exc(π_{i})} to the determinant value. We assume that the elements of R_{i} and C_{i} for 1 ≤ i ≤ n are totally ordered. We also assume that all elements of R_{i} (respectively C_{i}) are less than all elements of R_{j} (respectively C_{j}) for j > i and that any element of C_{i} is greater than any element of R_{j} for all pairs i, j.

We represent all permutations π_{i} in two-line notation. Since we have permutations which are themselves indexed as π_{i}, we denote the r-th letter of π_{i} as (π_{i})_{r}. Let T be the set of terms indexed by tuples (id, π_{0}, π_{1}, …, π_{n}) where id is the identity permutation on [n_{0}] and π_{i} is such that π_{i}(R_{i}) = C_{i} and π_{i}(C_{i}) = R_{i} for each 1 ≤ i ≤ n. Clearly there are ∏_{k=1}^{n}(k!)^{2} such tuples in T. Since sgn(id) = 1, and since each element of C_{k} is larger than each element of R_{k} for all k, all the π_{k}’s in T will have exc(π_{k}) = k. Since this happens for all k, the contribution of T to the determinant of E_{n} is ∏_{k=0}^{n} k!^{2}x^{∑_{k=0}^{n} k} = x^{n(n+1)/2} ∏_{k=0}^{n}(k!)^{2}.

Given a tuple (σ, π_{0}, π_{1}, …, π_{n}), for each 1 ≤ i ≤ n let a_{i} be the sum of the number of elements of R_{i} which under π_{i} go to C_{σ(i)} and the number of elements of C_{σ(i)} which under π_{i} go to R_{i}. We note that all the a_{i}’s are even and if a_{i} = 2p, then p elements of R_{i} are written under C_{σ(i)} and p elements of C_{σ(i)} are written under R_{i} in the two line notation of π_{i}. Furthermore, it is clear that the a_{i}’s are distinct for a term indexed by (σ, π_{0}, π_{1}, …, π_{n}) if and only if (σ, π_{0}, π_{1}, …, π_{n}) ∈ T. For each (σ, π_{0}, π_{1}, …, π_{n}) ∈ P − T, a partner tuple (σ′, π′_{0}, π′_{1}, …, π′_{n}) with an opposite sign will be constructed so that this map is a sign reversing involution on the set of tuples in P − T. This will show that the tuples in P − T contribute nothing to the determinant value.

If (σ, π_{0}, π_{1}, …, π_{n}) ∈ P − T, then at least two of the a_{i}’s must be identical. Choose the lexicographically minimum pair s, t such that a_{s} = a_{t}. Let σ′ be a permutation on the set [n_{0}] such that σ′(s) = σ(t), σ′(t) = σ(s) and σ′(i) = σ(i) for i ≠ s, t.

Let 2a = a_{s} = a_{t}. Let π′_{i} be identical to π_{i} on R_{i} ∪ C_{σ(i)} for i ≠ s, t. For the two line representation of π′_{s} (a permutation on R_{s} ∪C_{σ(t)}), since C_{σ(t)} and C_{σ(s)} are ordered, list the a elements of C_{σ(t)} below R_{s} in the order of the a elements of C_{σ(s)} in π_{s} and list the a elements of R_{s} below C_{σ(t)} in the same order as in π_{s}. (See the example below.)

π_{s} = ( \begin{matrix}& R_{s} & & & & C_{σ(s)} \\ 1 & 2 & 3 & 51 & 52 & 53 & 54 \\ 53 & 3 & 52 & 1 & 54 & 51 & 2 \end{matrix} ) π_{t} = ( \begin{matrix}& R_{t} & & & & C_{σ(t)} \\ 10 & 11 & 12 & 13 & 56 & 57 & 58 \\ 56 & 57 & 13 & 10 & 12 & 11 & 58 \end{matrix} )
inv(π_{s}) = 13, exc(π_{s}) = 4  inv(π_{t}) = 12, exc(π_{t}) = 3

π′_{s} = ( \begin{matrix}& R_{s} & & & C_{σ(t)} \\ 1 & 2 & 3 & 56 & 57 & 58 \\ 57 & 3 & 56 & 1 & 2 & 58 \end{matrix} ) π′_{t} = ( \begin{matrix}& R_{t} & & & & C_{σ(s)} \\ 10 & 11 & 12 & 13 & 51 & 52 & 53 & 54 \\ 52 & 53 & 13 & 10 & 12 & 54 & 51 & 11 \end{matrix} )
inv(π′_{s}) = 8, exc(π′_{s}) = 3  inv(π′_{t}) = 17, exc(π′_{t}) = 4

Similarly, to get the two line representation of π′_{t} (a permutation on the set R_{t} ∪ C_{σ(s)}), list the a elements of C_{σ(s)} below R_{t} in the order of the a elements of R_{t} in π_{t} and list the a elements of R_{t} below C_{σ(s)} as they appeared in π_{t}. From the above, it is easy to see that the term (σ′, π′_{0}, π′_{1}, …, π′_{n}) has the same a_{i}’s as the term (σ, π_{0}, π_{1}, …, π_{n}) and thus these terms map to each other, showing that we have an involution. We show now that

(2)  exc(π_{s}) + exc(π_{t}) = exc(π′_{s}) + exc(π′_{t})

Since a elements of C_{σ(t)} and C_{σ(s)} (which are larger than all elements of R_{s} and R_{t}) get swapped in π_{s} and π_{t} to give π′_{s} and π′_{t}, the two quantities on each side of Equation (2) are equal. Furthermore, as sgn(σ) = −sgn(σ′), all terms in P − T cancel out in the determinant expansion. Thus the only terms that contribute to the determinant are those in T, completing the proof. □

2.1. Bivariate analogue of Theorem 2.

Proof of Theorem 4. Consider the same bijection and the same set T fixed under the involution. We show that

(1) terms in P − T have the same (exc, inv) joint distribution under the sign reversing involution

(2) and t^{n(n+1)/2}q^{n(n+1)(2n+1)/6} ∏_{k=1}^{n}([k]_{q}!)^{2} is the sum of the joint distribution of (exc, inv) over terms of T.

Proof of item 1. Straightforward and thus omitted, just that this time terms π and π′ that are mapped to each other under the bijection satisfy t^{exc(π)}q^{inv(π)} = t^{exc(π′)}q^{inv(π′)} and have opposite signs.

Proof of item 2. We show that the sum of the joint distribution of (exc, inv) over the π_{i}’s is t^{i}q^{i^{2}}[i]_{q}!. To see this, we note that each π_{i} maps R_{i} to C_{i} and vice-versa (so there are i!^{2} such π_{i}’s) and, due to our labelling, all π_{i}’s have i excedances. Hence we can pull out a t^{i} factor and sum q^{inv(π_{i})} over these (i!)^{2} permutations. It is clear from the two-line representation of these permutations and ∑_{π∈S_{i}} q^{inv(π)} = [i]_{q}! (see [6, Section 2, p. 15]) that permutations π_{i} contribute t^{i}q^{i^{2}}([i]_{q}!)^{2} to the determinant’s value. Taking the product over 1 ≤ i ≤ n completes the proof. □

Remark 1. From Theorem 4, it is clear that if p_{n}(q) = [n]_{q}! with p_{0}(q) = 1, then the n-th Hankel matrix whose (i, j)-th term for 0 ≤ i, j ≤ n is p_{i+j}(q) has determinant

q^{n(n+1)(2n+1)/6} ∏_{k=1}^{n}([k]_{q}!)^{2}.

This can also be seen from [7, Proposition 1]. By replacing q by q^{2} or more generally by q^{d} for a positive integer d, we get analogues for the hyperoctahedral group and the wreath-product group S_{n} ≀ ℤ_{d}.

Remark 2. The same proposition can be used to show that, if s_{n}(x) = x(x + 1) ⋯ (x + n − 1), then the determinant of the n-th Hankel matrix with (i, j)-th entry being s_{i+j}(x) is ∏_{k=1}^{n}(k!s_{k}(x)). More generally, for positive integers a, r, consider the arithmetic progression A = (a, a + r, a + 2r, …,) (i.e., a_{1} = a and a_{i} = a + (i − 1)r) and define a sequence of polynomials p_{n}(x, y) = ∏_{k=1}^{n}(a_{1}x + (k − 1)ry) with p_{0}(x, y) = 1. The determinant of the n-th Hankel matrix with (i, j)-th entry being p_{i+j}(x, y) is

∏_{k=1}^{n} (ax + (k − 1)ry) ∏_{k=1}^{n}(ry)^{k}k!.

3. Fixed point free involutions

Let M be a perfect matching (or fixed-point free involution) on the set [2n]. We call each pair (i, j) ∈ M an edge of M. We assume without loss of generality that the edges of M are (i_{1}, j_{i}), (i_{2}, j_{2}), …, (i_{n}, j_{n}) where i_{r} < j_{r} for 1 ≤ r ≤ n and i_{r} < i_{r+1} for 1 ≤ r < n.

Proof of Theorem 5. For each positive integer 1 ≤ i ≤ n, let R_{i} and C_{i} be disjoint sets of size 2i. As before we label them such that any element of any C_{j} is larger than any element of any R_{i}. It is easy to see that terms in the determinant are indexed by the set P, with elements being tuples of the form p = (π, m_{0}, m_{1}, …, m_{n}), where π ∈ S_{n_{0}} and m_{i} is a perfect matching on the set R_{i} ∪ C_{π(i)}. Such a tuple p contributes (−1)^{sgn(π)}q^{∑_{i=0}^{n} cross(m_{i})} to the determinant value.

As done before, let T ⊆ P be those terms indexed by (id, m_{0}, m_{1}, …, m_{n}) where in m_{i}, each element of R_{i} is paired with an element of C_{i}. We omit the routine sign reversing involution on the terms in P − T and show that ∑_{(id,m_{0},...,m_{n})∈T} q^{∑_{i=0}^{n} cross(m_{i})} = ∏_{k=1}^{n}[2k]_{q}!. Let PM_{2i} denote the set of perfect matchings on the set R_{i} ∪ C_{i} (where |R_{i}| = |C_{i}| = 2i) with the property that every edge of PM_{2i} is of the type (r, c) where r ∈ R_{i} and c ∈ C_{j}. Clearly, |PM_{2i}| = (2i)!. It suffices to show that ∑_{M∈PM_{2i}} q^{cross(M)} = [2i]_{q}!. To see this, write M as a 2i sized permutation π_{M} in two line notation with the elements of R_{i} above and those of C_{i} below (π_{M} contains complete information about M). Then it is simple to see that inv(π_{M}) = \binom{2i}{2} − cross(M). Since each of the (2i)! permutation π_{M} occur this way, ∑_{M∈PM_{2i}} q^{cross(M)} = ∑_{π∈S_{2i}} q^{\binom{2i}{2}−inv(π)}. This is clearly [2i]_{q}! (see [15, page 21]). The proof is complete after taking the product over the n different PM_{2i}’s. □

4. Non crossing partitions

We begin with a slightly modified definition of the statistic rs(·). If a set of size n is not labelled by [n], but by some set T_{n} ⊆ ℤ of n positive integers, then from Equation (1), we see that the statistic rs(π) for a non-crossing partition π depends on the set T_{n}, which is not desirable. Thus, whenever we have a non-crossing partition π on a set T_{n}, we map its elements to the set {1, 2, …, n} in an order-preserving (with respect to the natural order on ℤ) way, and then compute its rs(·) value.

Proof of Theorem 8. We have disjoint sets R_{i} for 0 ≤ i ≤ n with |R_{i}| = i and another completely disjoint family of sets C_{i} for 0 ≤ i ≤ n, again with |C_{i}| = i. We label the elements of R_{i} in increasing order of i and then, starting from a larger number L, number the elements of C_{i} in decreasing order of i. (This is done so that, for any 0 ≤ i, j ≤ n, if the elements of R_{i} are written in increasing order from left-right and those of C_{j} are written below in increasing order from right-left, the elements of R_{i} ∪ C_{j} appear in increasing order when viewed clockwise.)

It is clear that the terms involved in the determinant expansion of the nth Hankel matrices with (i, j)-th entry being N_{i+j}(x, q) are indexed by tuples (σ, π_{0}, π_{1}, …, π_{n}), where σ is a permutation of [n_{0}] and π_{i} is a non-crossing partition on the set R_{i} ∪ C_{σ(i)}, and such a term contributes (−1)^{sgn(σ)}x^{∑_{i=0}^{n} |π_{i}|}q^{∑_{i=0}^{n} rs(π_{i})}. Let P be the set of such tuples. For a tuple (σ, π_{0}, π_{1}, …, π_{n}) ∈ P, let a_{i} be the number of blocks of the non-crossing partition π_{i} which intersect both R_{i} and C_{σ(i)}. Let T consist of the tuples indexed by (id, π_{0}, π_{1}, …, π_{n}) where π_{i} is a non-crossing partition on R_{i} ∪ C_{i} with i blocks intersecting both R_{i} and C_{i}. Thus, there is exactly one tuple in T.

It is simple to note that the a_{i}’s are all distinct for a tuple if and only if it is in T. We thus need to exhibit a fixed point free sign-reversing involution on the tuples in P − T. As before, for a tuple (σ, π_{0}, π_{1}, …, π_{n}) ∈ P − T, let (s, t) be the lexicographically smallest pair with a_{s} = a_{t}. Define (σ′, π′_{0}, π′_{1}, …, π′_{n}) such that σ(i) = σ′(i) for i ∈ [n_{0}], i ≠ s, t. Let σ′(s) = σ(t) and σ′(t) = σ(s).

Let π′_{i} = π_{i} for i ≠ s, t. Since a = a_{s} = a_{t}, there are a blocks of π_{s}, π_{t} which intersect both R_{s} ∪ C_{σ(s)} and R_{t} ∪ C_{σ(t)} (see Figure 1 below). Each of the a blocks of π_{s} (respectively π_{t}) contains some element of R_{s} (respectively R_{t}) and since the elements of R_{s} and R_{t} are totally ordered, each of the a blocks contains a minimum element (of R_{s} or R_{t}). Order the a non-crossing blocks of π_{s} as P_{1}, P_{2}, …, P_{a} in increasing order of the minimum element of R_{s} contained in P_{i} and likewise, order the blocks of π_{t} as Q_{1}, Q_{2}, …, Q_{a} in increasing order of the minimum element of R_{t} contained in Q_{i}. Let P′_{i} = (P_{i} ∩ R_{s}) ∪ (Q_{i} ∩ C_{σ(t)}) and Q′_{i} = (Q_{i} ∩ R_{t}) ∪ (P_{i} ∩ C_{σ(s)}) for 1 ≤ i ≤ a. Let the blocks of π′_{s} (a non-crossing partition on the set R_{s} ∪ C_{σ(t)}), be obtained by replacing P_{i} by P′_{i} and similarly let the blocks of π′_{t} be obtained by replacing Q_{i} by Q′_{i} for all 1 ≤ i ≤ a. It is simple to see that both π′_{s} and π′_{t} are non-crossing partitions and that sgn(σ) = −sgn(σ′). Furthermore, it is easy to see that |π_{s}| = |π′_{s}| and |π_{t}| = |π′_{t}|.

Figure 1. An illustration of the bijection (shaded regions are the blocks of the partition).

In π_{s} and π_{t}, since any element of any C_{j} is greater than any element of any R_{i}, it is straightforward to note that if α = |R_{s}| and β = |R_{t}|, then we can write, for some c_{i}, ℓ(P_{i}) = α + c_{i} for all 1 ≤ i ≤ a (i.e., the largest element of P_{i} is the c_{i}-th largest element above α). Similarly, for some d_{i}, we can write ℓ(Q_{i}) = β + d_{i}.

In π′_{s}, we note that ℓ(P′_{i}) = α + d_{i} for 1 ≤ i ≤ a, while in π′_{t}, ℓ(Q′_{i}) = β + c_{i} for all i. It is straightforward to note that f(P_{i}) = f(P′_{i}) for all i and f(Q_{i}) = f(Q′_{i}) for all i. We have also observed that |π_{s}| = |π′_{s}| and |π_{t}| = |π′_{t}|. Hence, rs(π_{s}) + rs(π_{t}) = rs(π′_{s}) + rs(π′_{t}) and thus q^{∑_{i=0}^{n} rs(π_{i})} = q^{∑_{i=0}^{n} rs(π′_{i})}. i.e., the involution preserves both x^{∑_{i=0}^{n} |π_{i}|} and q^{∑_{i=1}^{n} rs(π_{i})} simultaneously.

Since the involution is fixed-point free on P − T, the set P − T contributes nothing to the determinant. As (id, π_{0}, π_{1}, …, π_{n}) is the only tuple in T, it is simple to see that the exponent of x contributed is n(n+1)/2 (as each π_{i} contributes i parts for 0 ≤ i ≤ n). For the exponent of q, we note that π_{i} has i-blocks and for the k-th block (where 1 ≤ k ≤ i) f_{k} = k, ℓ_{k} = 2i − k + 1. Thus, rs(π_{i}) = ∑_{k=1}^{i}(2k − 1) − 2i + i = i^{2} − i and ∑_{i=0}^{n} i^{2} − i = 2\binom{n+1}{3}. Thus, the determinant has value x^{\binom{n+1}{2}}q^{2\binom{n+1}{3}}, completing the proof. □

We end with a few remarks about Theorem 8. Simion [12] has shown that NC_{n} is a graded lattice and that the Narayana numbers are its Whitney numbers. Theorem 8 is thus about the Hankel determinant of a q-analogue of the Whitney polynomial of NC_{n}.

Reiner [11] has defined non-crossing partitions for all classical reflection groups and hence type-B analogues of NC_{n}, denoted NC_{n}^{B} exist. NC_{n}^{B} is also a graded lattice with k-th Whitney number being \binom{n}{k}^{2} (see [11]). Simion [13] has given analogues rs^{B}(σ) for type-B non-crossing partitions σ of the statistic rs(.). Consider the type-B Whitney polynomial p_{n}^{B}(x) = ∑_{k=0}^{n} \binom{n}{k}^{2}x^{k}. The determinant of the n-th Hankel matrix with (i, j)-th entry being the polynomial p_{i+j}^{B}(x) is 2^{n}x^{n(n+1)/2} (see Paul Barry’s contribution in [14, id: A000984]). However, a q-analogue similar to Theorem 8 does not hold with respect to the statistic rs^{B}(.).

It would be very interesting to have a statistic st^{B}(σ) on a type-B non-crossing partition σ such that a type-B analogue of Theorem 8 holds.

Acknowledgement

Some theorems in this work were found first in conjectured form, tested using the computer package “Sage”. We thank the authors for generously releasing their software as an opensource package.

We are grateful to Professor Christian Krattenthaler for pointing out several inaccuracies, whose correction has substantially improved the manuscript and for pointing out the short proofs mentioned in Remarks 1 and 2. The initial proofs of these were similar sign reversing involutions.

References

[1] Cigler, J. Eine Charakterisierung der q-Exponentialpolynome. Österreich Akad. Wiss. Math.-Naturwiss. Kl. Sitzungsber. II, 208 (1999), 143–157. [2]

[2] Clarke, R. J., Steingrímsson, E., and Zeng, J. New Euler-Mahonian statistics on permutations and words. Advances in Applied Math. 18 (1997), 237–270. [2]

[3] Edelman, P. Chain enumeration and non-crossing partitions. Discrete Math. 31 (1980), 171–180. [3]

[4] Ehrenborg, R. The Hankel determinant of exponential polynomials. American Math. Monthly 107 (2000), 557–560. [1, 2]

[5] Ehrenborg, R. Determinants involving q-Stirling numbers. Advances in Applied Math. 31 (2003), 630– 642. [3]

[6] Foata, D., and Han, G. q-series in Combinatorics; Permutation Statistics. available at

http://www-irma.u-strasbg.fr/∼foata/qseries.html, 2004. [5]

[7] Krattenthaler, C. Advanced determinant calculus. Seminaire Lotharingien Combin. 42 (1999), Art. B42q. [1, 2, 5]

[8] Krattenthaler, C. Advanced determinant calculus: A complement. Linear Algebra and Appl. 411 (2005), 68–166. [3]

[9] Radoux, C. Calcul effectif de certains déterminants de Hankel. Bull Soc. Math. Belg. Sér. B 31 (1979), 49–55. [1]

[10] Radoux, C. Addition formulas for polynomials built on classical sequences. Journal of Computational and Applied Math. 115 (2000), 471–477. [3]

[11] Reiner, V. Non-crossing partitions for classical reflection groups. Discrete Math. 177 (1997), 195–222. [7]

[12] Simion, R. Combinatorial statistics on non-crossing partitions. Journal of Combinatorial Theory Ser. A 66, 2 (1994), 270–301. [3, 7]

[13] Simion, R. Combinatorial statistics on type-B analogues of non-crossing partitions and restricted permutations. Electronic Journal of Combinatorics 7 (2000), R9. [7]

[14] Sloane, N. J. A. OEIS: Online Encyclopaedia of Integer Sequences. Available at

www.research.att.com/∼njas/OEIS/. [7]

[15] Stanley, R. P. Enumerative Combinatorics, vol. 1. Cambridge University Press, 1997. [3, 6]

[16] Wachs, M., and White, D. p, q-Stirling numbers and set partition statistics. Journal of Combinatorial Theory Ser. A 56 (1990), 27–46. [2]