Some Determinantal Representations of Eulerian Polynomials and Their q-Analogues

Chak-On Chow 28A, Block 2, Banyan Garden Cheung Sha Wan Hong Kong

                      cchow@alum.mit.edu

Abstract The author recently q-extended the approach of Qi, Wang, and Guo to derangement numbers, and successfully applied this extended approach to obtain expressions for certain types B and D of derangement polynomials as determinants of order n + 1. In this paper, we demonstrate that the q-extended approach is applicable to other generating functions, including the Eulerian polynomials A_{n}(t), B_{n}(t), and D_{n}(t) for types A, B, and D, as well as the types A and B “inv” analogues of q-Eulerian polynomials A_{n}^{inv}(t, q) and B_{n}^{inv}(t, q). We also present a new recurrence relation for B_{n}^{inv}(t, q).

1 Introduction

Certain mathematical quantities are expressible as determinants. See [12] for useful tools for evaluating determinants, examples of evaluated determinants in context, and further references. As far as the present work is concerned, a notable example is the nth classical derangement number d_{n}. Qi, Wang, and Guo [13], by exploiting Lemma 1 below, were able to express d_{n} as a tridiagonal determinant of order n + 1. The involved generating function of d_{n} is of the exponential type. See Section 2 for undefined terms.

An inspection of the approach of Qi et al. reveals that it is q-generalizable. The author [10], by coming up with a q-version of Lemma 1, obtained expressions for types B and D of derangement polynomials d_{n}^{B}(q) := ∑_{σ∈D_{n}^{B}} q^{fmaj(σ)} and d_{n}^{D}(q) := ∑_{σ∈D_{n}^{D}} q^{maj(σ)}, studied previously in [6, 8], as determinants of order n + 1, whose generating functions are of the factorial type.

The above mentioned derangement polynomials enumerate signed and even-signed derangements according to a certain statistic. By extrapolating this idea, we can, in general, consider generating functions that enumerate other combinatorial objects according to tuples of statistics. For instance, one can consider the classical Eulerian polynomial A_{n}(x), which is a univariate generating function of n-permutations by their descent numbers, or q-Eulerian polynomials that are bivariate generating function of permutations by their descent numbers and some other statistics. Examples of the latter include the types A and B “inv” analogues of q-Eulerian polynomials, namely, A_{n}^{inv}(t, q) := ∑_{σ∈𝔖_{n}} t^{des(σ)+1}q^{inv(σ)} and B_{n}^{inv}(t, q) := ∑_{σ∈B_{n}} t^{des_{B}(σ)}q^{inv_{B}(σ)}.

The successes in [13, 9, 10] suggest that the original and extended approach of Qi et al. readily apply to generating functions of the exponential or of factorial type and whose closed form expressions are quotients, yielding determinantal expressions of them.

The purpose of this work is to show that the q-extended approach of Qi et al. applies to finding determinantal expressions of k-variate generating functions, with k = 1, 2.

The organization of this work is as follows. In Section 2, we gather notation and undefined terms that are needed in the rest of this paper. In Section 3, we compute determinantal expressions of Eulerian polynomials of types A, B, and D. In Section 4, we compute determinantal expressions of the q-Eulerian polynomials A_{n}^{inv}(t, q) and B_{n}^{inv}(t, q). In Section 5, we explore the relationship between A_{n}^{inv}(t, q) and B_{n}^{inv}(t, q) and obtain a recurrence relation for B_{n}^{inv}(t, q). In Section 6, we end this work by raising two questions.

2 Notation and preliminaries

Let ℕ, ℚ, and ℝ denote the sets of non-negative integers, rational numbers, and real numbers, respectively. Let a, b ∈ ℕ. Define the interval of integers [a, b] by {a, a + 1, …, b}. In case b < a, we have [a, b] = ∅, the empty set. Let #S denote the cardinality of a finite set S.

Let n ≥ 1. A square matrix A = (a_{ij})_{1≤i,j≤n} of order n is lower Hessenberg if all entries above the superdiagonal are zeros.

Let 𝔖_{n} denote the symmetric group of degree n, consisting of all permutations of 1, 2, …, n. An element σ of 𝔖_{n} is represented by the associated word σ_{1}σ_{2} ⋯ σ_{n}, where σ_{i} = σ(i) for i = 1, 2, …, n. An n-permutation σ = σ_{1}σ_{2} ⋯ σ_{n} is said to be a derangement if σ_{i} ≠ i for all i = 1, 2, …, n. Let D_{n} denote the set of n-derangements. Define the major index, the descent number, and the inversion number of σ ∈ 𝔖_{n} by

maj(σ) := ∑_{i=1}^{n−1} iχ(σ_{i} > σ_{i+1}),

des(σ) := ∑_{i=1}^{n−1} χ(σ_{i} > σ_{i+1}),

inv(σ) := ∑_{i=1}^{n−1} ∑_{j=i+1}^{n} χ(σ_{i} > σ_{j}),

respectively, where χ(P) = 1 or 0 depending on whether the statement P is true or not. This notion of major index applies to any permutations, signed or not. The nth classical Eulerian polynomial is defined by A_{n}(x) := ∑_{σ∈𝔖_{n}} x^{des(σ)+1}. It is well known that the exponential generating function of (A_{n}(x))_{n⩾0} has the following expression:

A(x, z) := ∑_{n≥0} A_{n}(x)\frac{z^{n}}{n!} = \frac{1 − x}{1 − xe^{z(1−x)}} ,  (1)

where A_{0}(x) := 1 by convention.

Let B_{n} denote the nth hyperoctahedral group, consisting of all signed permutations of 1, 2, …, n, represented by the associated words. The above definition of derangements also applies to signed permutations. Let D_{n}^{B} denote the set of signed n-derangements. Three needed statistics on B_{n} are the flag major index, the type B descent number, and the type B inversion number, defined respectively by

fmaj(σ) := 2 maj(σ) + N(σ),
des_{B}(σ) := ∑_{i=0}^{n−1} χ(σ_{i} > σ_{i+1}),

inv_{B}(σ) := inv(σ) + ∑_{i=1}^{n} |σ_{i}|χ(σ_{i} < 0),

where N(σ) := #{i: σ_{i} < 0} is the number of negative letters of σ, and σ_{0} := 0. The above definition of flag major index is due to Adin-Brenti-Roichman [1], and those of des_{B} and inv_{B} are due to Brenti [5], who had also shown that inv_{B} ≡ l_{B}, where l_{B} is the type B length function.

The nth type B Eulerian polynomial is defined by B_{n}(x) := ∑_{σ∈B_{n}} x^{des_{B}(σ)}. It is known that the exponential generating function of (B_{n}(x))_{n⩾0} has the following expression:

B(x, z) := ∑_{n≥0} B_{n}(x)\frac{z^{n}}{n!} = \frac{(1 − x)e^{z(1−x)}}{1 − xe^{2z(1−x)}} ,  (2)

where B_{0}(x) := 1 by convention.

Let D_{n} denote the nth even-signed permutation group, consisting even-signed permutations of 1, 2, …, n of length n. An element σ of D_{n} is a signed n-permutation σ_{1}σ_{2} ⋯ σ_{n} with N(σ) even. Being a subgroup of B_{n}, the definition of derangements applies to D_{n}. Let D_{n}^{D} denote the set of even-signed n-derangements. The type D descent number of σ ∈ D_{n} is defined by

des_{D}(σ) := ∑_{i=0}^{n−1} χ(σ_{i} > σ_{i+1}),

where σ_{0} := −σ_{2}. The nth type D Eulerian polynomial is defined by D_{n}(x) := ∑_{σ∈D_{n}} x^{des_{D}(σ)}. It is known that the exponential generating function of (D_{n}(x))_{n⩾0} has the following expression:

D(x, z) := ∑_{n≥0} D_{n}(x)\frac{z^{n}}{n!} = \frac{(1 − x)(e^{z(1−x)} − xze^{2z(1−x)})}{1 − xe^{2z(1−x)}},  (3)

where D_{0}(x) := 1 by convention.

Those two classes of derangement polynomials mentioned in the Introduction are

d_{n}^{B}(q) := ∑_{σ∈D_{n}^{B}} q^{fmaj(σ)}, and d_{n}^{D}(q) := ∑_{σ∈D_{n}^{D}} q^{maj(σ)},

studied previously by the author [6, 8].

Let x and q be commuting indeterminates. Define

(x; q)_{n} := \begin{cases}(1 − x)(1 − xq) ⋯ (1 − xq^{n−1}) & if n ≥ 1; \\ 1 & otherwise. \end{cases}

Q-integers, q-factorials and q-binomial coefficients are defined by

\begin{aligned}[n]_{q} & := 1 + q + ⋯ + q^{n−1}, \\ [n]_{q}! & := [1]_{q}[2]_{q} ⋯ [n]_{q}, and \\ [\begin{matrix}n \\ k \end{matrix}]_{q} & := \frac{[n]_{q}!}{[k]_{q}![n − k]_{q}!}, 0 ≤ k ≤ n, \end{aligned}

respectively.

The original approach of Qi et al. is based on Lemma 1, which is stated in [4, p. 40] as an exercise. A solution of this Bourbaki exercise can be found in [9].

Lemma 1. Let u = u(x) and v = v(x) be two real functions that are n times differentiable on an interval I ⊂ ℝ. Then at every point where v(x) ≠ 0, we have

\frac{d^{n}}{dx^{n}} (\frac{u}{v}) = \frac{(−1)^{n}}{v^{n+1}} |\begin{matrix}u & v & 0 & ⋯ & 0 & 0 \\ u′ & v′ & v & ⋯ & 0 & 0 \\ u′′ & v′′ & 2v′ & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ u^{(n−1)} & v^{(n−1)} & \binom{n−1}{1}v^{(n−2)} & ⋯ & \binom{n−1}{n−2}v′ & v \\ u^{(n)} & v^{(n)} & \binom{n}{1}v^{(n−1)} & ⋯ & \binom{n}{n−2}v′′ & \binom{n}{n−1}v′ \end{matrix}| .

Let {f_{n}} be a sequence of numbers or k-variate formal power series independent of x, where k ≥ 1. If the exponential generating function of {f_{n}},

f(x) = ∑_{n≥0} f_{n} \frac{x^{n}}{n!} ,

can be written as a quotient u(x)/v(x), then with Lemma 1, the approach of Qi et al. allows us to express

f_{n} = \frac{∂^{n}}{∂x^{n}} f(x)|_{x=0}

as a determinant of order n + 1.

The author [10] q-extended Lemma 1 to become Lemma 2, where for formal power series f(t; q) ∈ ℚ[[t, q]] in t and q with rational coefficients, its q-derivative with respect to t is defined as

D_{q}f(t; q) := \frac{f(tq; q) − f(t; q)}{(q − 1)t}.  (4)

It is easy to see that D_{q}t^{n} = [n]_{q}t^{n−1}. See [2, §2.2] for details of q-calculus.

Lemma 2. Let n ≥ 1 and let u = u(t; q), v = v(t; q) ∈ ℚ[[t, q]] be such that their nth q-derivatives D_{q}^{n}u(t; q) and D_{q}^{n}v(t; q) exist. Then at every point where v(t; q) ≠ 0, we have

D_{q}^{n}(\frac{u}{v})(t; q) = \frac{(−1)^{n}}{v^{n+1}} |\begin{matrix}u & v & 0 & ⋯ & 0 & 0 \\ D_{q}u & D_{q}v & v & ⋯ & 0 & 0 \\ D_{q}^{2}u & D_{q}^{2}v & [\begin{matrix}2 \\ 1 \end{matrix}]_{q}D_{q}v & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ D_{q}^{n−1}u & D_{q}^{n−1}v & [\begin{matrix}n−1 \\ 1 \end{matrix}]_{q}D_{q}^{n−2}v & ⋯ & [\begin{matrix}n−1 \\ n−2 \end{matrix}]_{q}D_{q}v & v \\ D_{q}^{n}u & D_{q}^{n}v & [\begin{matrix}n \\ 1 \end{matrix}]_{q}D_{q}^{n−1}v & ⋯ & [\begin{matrix}n \\ n−2 \end{matrix}]_{q}D_{q}^{2}v & [\begin{matrix}n \\ n−1 \end{matrix}]_{q}D_{q}v \end{matrix}| ,

where all the formal power series on the right side are evaluated at (tq^{−n}; q).

To simplify the expressions, we write in the sequel D_{q}^{n}u(tq^{−n}; q) to mean the result of substituting the arguments of the nth q-derivative of u(t; q) by (tq^{−n}; q), etc.

Let (f_{n})_{n⩾0} be a sequence of formal power series dependent on q and on some other indeterminates but independent of x. If the factorial generating function of (f_{n})_{n⩾0},

f(x) = ∑_{n≥0} f_{n} \frac{x^{n}}{[n]_{q}!},

can be written as a quotient u(x)/v(x), then with Lemma 2, the q-extended approach of Qi et al. allows us to express

f_{n} = D_{q}^{n}f(x)|_{x=0}

as a determinant of order n + 1, where D_{q}^{n}f(x) on the right denotes the nth q-derivative of f(x) with respect to x.

3 Determinantal expressions of Eulerian polynomials

The goal of this section is to present determinantal expressions of the Eulerian polynomials A_{n}(x), B_{n}(x), and D_{n}(x).

Theorem 3. Let n ≥ 1. The Eulerian polynomial A_{n}(x) is expressible as the following lower Hessenberg determinant of order n + 1:

A_{n}(x) = (−1)^{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & −x & 1 & ⋯ & 0 & 0 \\ 0 & −x(1 − x) & −2x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & −x(1 − x)^{n−2} & −\binom{n−1}{1}x(1 − x)^{n−3} & ⋯ & −\binom{n−1}{n−2}x & 1 \\ 0 & −x(1 − x)^{n−1} & −\binom{n}{1}x(1 − x)^{n−2} & ⋯ & −\binom{n}{n−2}x(1 − x) & −\binom{n}{n−1}x \end{matrix}| .

Proof. By virtue of the exponential generating function (1) of (A_{n}(x))_{n⩾0}, regarding x as a parameter, we let u(z; x) = 1 − x and v(z; x) = 1 − xe^{z(1−x)}. Then for k ≥ 1, ∂_{z}^{k}u(z; x) = 0 and ∂_{z}^{k}v(z; x) = −x(1 − x)^{k}e^{z(1−x)}. Applying Lemma 1, and letting z → 0, we have

A_{n}(x) = \frac{∂^{n}}{∂z^{n}} A(x, z)|_{z=0}

= \frac{(−1)^{n}}{(1 − x)^{n+1}} |\begin{matrix}1 − x & 1 − x & 0 & ⋯ & 0 & 0 \\ 0 & −x(1 − x) & 1 − x & ⋯ & 0 & 0 \\ 0 & −x(1 − x)^{2} & −2x(1 − x) & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & −x(1 − x)^{n−1} & −\binom{n−1}{1}x(1 − x)^{n−2} & ⋯ & −\binom{n−1}{n−2}x(1 − x) & 1 − x \\ 0 & −x(1 − x)^{n} & −\binom{n}{1}x(1 − x)^{n−1} & ⋯ & −\binom{n}{n−2}x(1 − x)^{2} & −\binom{n}{n−1}x(1 − x) \end{matrix}|

= (−1)^{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & −x & 1 & ⋯ & 0 & 0 \\ 0 & −x(1 − x) & −2x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & −x(1 − x)^{n−2} & −\binom{n−1}{1}x(1 − x)^{n−3} & ⋯ & −\binom{n−1}{n−2}x & 1 \\ 0 & −x(1 − x)^{n−1} & −\binom{n}{1}x(1 − x)^{n−2} & ⋯ & −\binom{n}{n−2}x(1 − x) & −\binom{n}{n−1}x \end{matrix}| ,

where the last equality follows from dividing each column by 1 − x.

Theorem 4. Let n ≥ 1. The type B Eulerian polynomial B_{n}(x) is expressible as the following lower Hessenberg determinant of order n + 1:

B_{n}(x) = (−1)^{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ 1 − x & −2x & 1 & ⋯ & 0 & 0 \\ (1 − x)^{2} & −2^{2}x(1 − x) & −2^{2}x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ (1 − x)^{n−1} & −2^{n−2}x(1 − x)^{n−2} & −\binom{n−1}{1}2^{n−3}x(1 − x)^{n−3} & ⋯ & −\binom{n−1}{n−2}2x & 1 \\ (1 − x)^{n} & −2^{n}x(1 − x)^{n−1} & −\binom{n}{1}2^{n−2}x(1 − x)^{n−2} & ⋯ & −\binom{n}{n−2}2^{2}x(1 − x) & −\binom{n}{n−1}2x \end{matrix}| .

Proof. By virtue of (2), let u(z; x) = (1 − x)e^{z(1−x)} and v(z; x) = 1 − xe^{2z(1−x)}. Then for k ≥ 1, ∂_{z}^{k}u(z; x) = (1−x)^{k+1}e^{z(1−x)} and ∂_{z}^{k}v(z; x) = −2^{k}x(1−x)^{k}e^{z(1−x)}. Applying Lemma 1, letting z → 0, and followed by dividing each column by 1 − x, we obtain

\begin{aligned}B_{n}(x) & = \frac{∂^{n}}{∂z^{n}} B(x, z)|_{z=0} \\ & = (−1)^{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ 1 − x & −2x & 1 & ⋯ & 0 & 0 \\ (1 − x)^{2} & −2^{2}x(1 − x) & −2^{2}x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ (1 − x)^{n−1} & −2^{n−2}x(1 − x)^{n−2} & −\binom{n−1}{1}2^{n−3}x(1 − x)^{n−3} & ⋯ & −\binom{n−1}{n−2}2x & 1 \\ (1 − x)^{n} & −2^{n}x(1 − x)^{n−1} & −\binom{n}{1}2^{n−2}x(1 − x)^{n−2} & ⋯ & −\binom{n}{n−2}2^{2}x(1 − x) & −\binom{n}{n−1}2x \end{matrix}| . \end{aligned}

Theorem 5. Let n ≥ 1. The type D Eulerian polynomial D_{n}(x) is expressible as the following lower Hessenberg determinant of order n + 1:

\begin{matrix}D_{n}(x) \\ = (−1)^{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ (1 − 2x) & −2x & 1 & ⋯ & 0 & 0 \\ (1 − x)(1 − 5x) & −2^{2}x(1 − x) & −2^{2}x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ^{…} & ⋮ & ⋮ \\ (1 − x)^{n−2}(1 − ((n − 1)2^{n−2} + 1)x) & −2^{n−1}x(1 − x)^{n−2} & −\binom{n−1}{1}2^{n−2}x(1 − x)^{n−3} & ⋯ & −\binom{n−1}{n−2}2x & 1 \\ (1 − x)^{n−1}(1 − (n2^{n−1} + 1)x) & −2^{n}x(1 − x)^{n−1} & −\binom{n}{1}2^{n−1}x(1 − x)^{n−2} & ⋯ & −\binom{n}{n−2}2^{2}x(1 − x) & −\binom{n}{n−1}2x \end{matrix}| . \end{matrix}

Proof. By virtue of (3), let u(z; x) = (1 − x)(e^{z(1−x)} − xze^{2z(1−x)}) and v(z; x) = 1 − xe^{2z(1−x)}. For k ≥ 1,

\begin{aligned}∂_{z}^{k}u(z; x) & = (1 − x)((1 − x)^{k}e^{z(1−x)} − x(2^{k}(1 − x)^{k}z + (\begin{matrix}k \\ 1 \end{matrix})2^{k−1}(1 − x)^{k−1})e^{2z(1−x)}), \\ ∂_{z}^{k}v(z; x) & = −2^{k}x(1 − x)^{k}e^{z(1−x)} \end{aligned}

so that

∂_{z}^{k}u(z; x)|_{z=0} = (1 − x)^{k}(1 − (k2^{k−1} + 1)x)), and ∂_{z}^{k}v(z; x)|_{z=0} = −2^{k}x(1 − x)^{k}.

Applying Lemma 1 with z → 0, we have

\begin{matrix}D_{n}(x) = \frac{∂^{n}}{∂z^{n}} D(x, z)|_{z=0} \\ = (−1)^{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ (1 − 2x) & −2x & 1 & ⋯ & 0 & 0 \\ (1 − x)(1 − 5x) & −2^{2}x(1 − x) & −2^{2}x & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ^{…} & ⋮ & ⋮ \\ (1 − x)^{n−2}(1 − ((n − 1)2^{n−2} + 1)x) & −2^{n−1}x(1 − x)^{n−2} & −\binom{n−1}{1}2^{n−2}x(1 − x)^{n−3} & ⋯ & −\binom{n−1}{n−2}2x & 1 \\ (1 − x)^{n−1}(1 − (n2^{n−1} + 1)x) & −2^{n}x(1 − x)^{n−1} & −\binom{n}{1}2^{n−1}x(1 − x)^{n−2} & ⋯ & −\binom{n}{n−2}2^{2}x(1 − x) & −\binom{n}{n−1}2x \end{matrix}| . \end{matrix}

4 Determinantal expressions of q-Eulerian polynomials

Bivariate extensions of A_{n}(x) and B_{n}(x) are available in the literature, namely, A_{n}^{inv}(t, q) := ∑_{σ∈𝔖_{n}} t^{des(σ)+1}q^{inv(σ)}, whose factorial generating function was computed by Stanley [15]:

A^{inv}(x; t, q) := ∑_{n≥0} A_{n}^{inv}(t, q)\frac{x^{n}}{[n]_{q}!} = \frac{1 − t}{1 − te(x(1 − t); q)},  (5)

where e(x; q) := ∑_{n≥0} \frac{x^{n}}{[n]_{q}!} is a q-exponential, and B_{n}^{inv}(t, q) := ∑_{σ∈B_{n}} t^{des_{B}(σ)}q^{inv_{B}(σ)}. Désarménien and Foata [11] showed that the following “semi” q-recurrence relation holds:

A_{n}^{inv}(t, q) = ∑_{k=0}^{n−1} [\begin{matrix}n \\ k \end{matrix}]_{q} A_{k}^{inv}(t, q)t(1 − t)^{n−1−k},  (6)

“semi” in the sense that the summands on the right involve two factors one of which depends on q and the other does not. The author [7] showed that A_{n}^{inv}(t, q) satisfies the following “fully” q-recurrence relation:

A_{n+1}^{inv}(t, q) = (1 + tq^{n})A_{n}^{inv}(t, q) + ∑_{k=1}^{n−1} [\begin{matrix}n \\ k \end{matrix}]_{q} q^{k}A_{n−k}^{inv}(t, q)A_{k}^{inv}(t, q).

As far as coefficient extraction is concerned, A^{inv}(x; t, q) enjoys the following property:

D_{q}^{n}A^{inv}(x; t, q)|_{x=0} = A_{n}^{inv}(t, q),

where the q-derivative is taken with respect to x. The key to the applicability of the approach of Qi et al., the original or the q-extended one, is that the exponential or factorial generating function be expressible as a quotient. That of (A_{n}^{inv}(t, q))_{n⩾0}, i.e., (5), is definitely a quotient. Applying the q-extended approach of Qi et al. readily yields Theorem 6.

Theorem 6. Let n ≥ 1. The q-Eulerian polynomial A_{n}^{inv}(t, q) is expressible as the following lower Hessenberg determinant of order n + 1:

A^{inv}(t, q) = (−1)^{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & −t & 1 & ⋯ & 0 & 0 \\ 0 & −t(1 − t) & −[\begin{matrix}2 \\ 1 \end{matrix}]_{q}t & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & −t(1 − t)^{n−2} & −[\begin{matrix}n−1 \\ 1 \end{matrix}]_{q}t(1 − t)^{n−3} & ⋯ & −[\begin{matrix}n−1 \\ n−2 \end{matrix}]_{q}t & 1 \\ 0 & −t(1 − t)^{n−1} & [\begin{matrix}n \\ 1 \end{matrix}]_{q}t(1 − t)^{n−2} & ⋯ & −[\begin{matrix}n \\ n−2 \end{matrix}]_{q}t(1 − t) & −[\begin{matrix}n \\ n−1 \end{matrix}]_{q}t \end{matrix}| .

Proof. Let u(x; t, q) := 1 − t and v(x; t, q) := 1 − te(x(1 − t); q). It is clear that u(0; t, q) = v(0; t, q) = 1 − t. For k ≥ 1, the kth q-derivatives of u(x; t, q) and v(x; t, q) with respect to x are, respectively, D_{q}^{k}u(x; t, q) = 0 and

D_{q}^{k}v(x; t, q) = −t ∑_{n≥k} \frac{(1 − t)^{n}x^{n−k}}{[n − k]_{q}!} = −t(1 − t)^{k} ∑_{n≥0} \frac{[x(1 − t)]^{n}}{[n]_{q}!} .

Evaluating them at (xq^{−n}; t, q) followed by letting x → 0, we have D_{q}^{k}u(xq^{−n}; t, q)|_{x=0} = 0 and D_{q}^{k}v(xq^{−n}; t, q)|_{x=0} = −t(1 − t)^{k}. Applying Lemma 2 with x → 0, we obtain

A^{inv}(t, q)

= \frac{(−1)^{n}}{(1 − t)^{n+1}} |\begin{matrix}1 − t & 1 − t & 0 & ⋯ & 0 & 0 \\ 0 & −t(1 − t) & 1 − t & ⋯ & 0 & 0 \\ 0 & −t(1 − t)^{2} & −[\begin{matrix}2 \\ 1 \end{matrix}]_{q}t(1 − t) & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & −t(1 − t)^{n−1} & −[\begin{matrix}n−1 \\ 1 \end{matrix}]_{q}t(1 − t)^{n−2} & ⋯ & −[\begin{matrix}n−1 \\ n−2 \end{matrix}]_{q}t(1 − t) & 1 − t \\ 0 & −t(1 − t)^{n} & [\begin{matrix}n \\ 1 \end{matrix}]_{q}t(1 − t)^{n−1} & ⋯ & −[\begin{matrix}n \\ n−2 \end{matrix}]_{q}t(1 − t)^{2} & −[\begin{matrix}n \\ n−1 \end{matrix}]_{q}t(1 − t) \end{matrix}|

= (−1)^{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ 0 & −t & 1 & ⋯ & 0 & 0 \\ 0 & −t(1 − t) & −[\begin{matrix}2 \\ 1 \end{matrix}]_{q}t & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & −t(1 − t)^{n−2} & −[\begin{matrix}n−1 \\ 1 \end{matrix}]_{q}t(1 − t)^{n−3} & ⋯ & −[\begin{matrix}n−1 \\ n−2 \end{matrix}]_{q}t & 1 \\ 0 & −t(1 − t)^{n−1} & [\begin{matrix}n \\ 1 \end{matrix}]_{q}t(1 − t)^{n−2} & ⋯ & −[\begin{matrix}n \\ n−2 \end{matrix}]_{q}t(1 − t) & −[\begin{matrix}n \\ n−1 \end{matrix}]_{q}t \end{matrix}| ,

where the second equality follows from dividing each column by 1 − t.

Let us now look at B_{n}^{inv}(t, q), whose first three members are as follows:

B_{1}^{inv}(t, q) = 1 + qt,
B_{2}^{inv}(t, q) = 1 + (2q + 2q^{2} + 2q^{3})t + q^{4}t^{2},
B_{3}^{inv}(t, q) = 1 + (3q + 4q^{2} + 5q^{3} + 4q^{4} + 4q^{5} + 2q^{6} + q^{7})t
+ (q^{2} + 2q^{3} + 4q^{4} + 4q^{5} + 5q^{6} + 4q^{7} + 3q^{8})t^{2} + q^{9}t^{3},

Reiner [14, Corollary 4.7] showed, in our terminology, that

∑_{n≥0} \frac{x^{n} ∑_{π∈B_{n}} q^{inv_{B}(π)}t^{n−des_{B}(π)}}{[2]_{q}[4]_{q} ⋯ [2n]_{q}} = (1 − ∑_{n≥1} \frac{(t − 1)^{n−1}x^{n}}{[n]_{q}!} )^{−1} ∑_{n≥0} \frac{(t − 1)^{n}x^{n}}{[2]_{q}[4]_{q} ⋯ [2n]_{q}} .

Note that [2k]_{q} = (1 + q^{k})[k]_{q} = (1 + q)[k]_{q^{2}} and that (1 + q)(1 + q^{2}) ⋯ (1 + q^{n}) = (−q; q)_{n}. The replacements x ↦ xt and t ↦ t^{−1} in the preceding factorial generating function identity then yield

B^{inv}(x; t, q) := ∑_{n≥0} B_{n}^{inv}(t, q)\frac{x^{n}}{(−q; q)_{n}[n]_{q}!}

= (1 − \frac{t}{1 − t} ∑_{n≥1} \frac{(1 − t)^{n}x^{n}}{[n]_{q}!} )^{−1} ∑_{n≥0} \frac{(1 − t)^{n}x^{n}}{(−q; q)_{n}[n]_{q}!},  (7)

which enjoys the following property:

D_{q}^{n}B^{inv}(x; t, q)|_{x=0} = \frac{B_{n}^{inv}(t, q)}{(−q; q)_{n}}.

The q-extended approach of Qi et al. readily applies to B^{inv}(x; t, q), yielding Theorem 7. Theorem 7. Let n ≥ 1. The type B q-Eulerian polynomial B_{n}^{inv}(t, q) can be expressed as the following lower Hessenberg determinant of order n + 1:

\begin{matrix}B_{n}^{inv}(t, q) \\ = (−1)^{n}(−q; q)_{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ \frac{(1−t)}{(−q;q)_{1}} & −t & 1 & ⋯ & 0 & 0 \\ \frac{(1−t)^{2}}{(−q;q)_{2}} & −t(1 − t) & −[\begin{matrix}2 \\ 1 \end{matrix}]_{q}t & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ \frac{(1−t)^{n−1}}{(−q;q)_{n−1}} & −t(1 − t)^{n−2} & −\binom{n−1}{1}t(1 − t)^{n−3} & ⋯ & −[\begin{matrix}n−1 \\ n−2 \end{matrix}]_{q}t & 1 \\ \frac{(1−t)^{n}}{(−q;q)_{n}} & −t(1 − t)^{n−1} & −[\begin{matrix}n \\ 1 \end{matrix}]_{q}t(1 − t)^{n−2} & ⋯ & −[\begin{matrix}n \\ n−2 \end{matrix}]_{q}t(1 − t) & −[\begin{matrix}n \\ n−1 \end{matrix}]_{q}t \end{matrix}| . \end{matrix}

Proof. Let

u(x; t, q) := ∑_{n≥0} \frac{(1 − t)^{n}x^{n}}{(−q; q)_{n}[n]_{q}!} and v(x; t, q) := 1 − \frac{t}{1 − t} ∑_{n≥1} \frac{(1 − t)^{n}x^{n}}{[n]_{q}!} .

It is easy to see that u(0; t, q) = 1 and v(0; t, q) = 1. For 1 ≤ k ≤ n, the kth q-derivatives of u(x; t, q) and v(x; t, q) with respect to x are, respectively,

\begin{aligned}D_{q}^{k}u(x; t, q) & = ∑_{n≥k} \frac{(1 − t)^{n}x^{n−k}}{(−q; q)_{n}[n − k]_{q}!} = (1 − t)^{k} ∑_{n≥0} \frac{(1 − t)^{n}x^{n}}{(−q; q)_{n+k}[n]_{q}!}, \\ D_{q}^{k}v(x; t, q) & = −\frac{t}{1 − t} ∑_{n≥k} \frac{(1 − t)^{n}x^{n−k}}{[n − k]_{q}!} = −t(1 − t)^{k−1} ∑_{n≥0} \frac{(1 − t)^{n}x^{n}}{[n]_{q}!} . \end{aligned}

It follows that

\begin{aligned}D_{q}^{k}u(xq^{−n}; t, q)|_{x=0} & = lim_{x→0}(1 − t)^{k} ∑_{n≥0} \frac{(1 − t)^{n}(xq^{−n})^{n}}{(−q; q)_{n+k}[n]_{q}!} = \frac{(1 − t)^{k}}{(−q; q)_{k}} , \\ D_{q}^{k}v(xq^{−n}; t, q)|_{x=0} & = − lim_{x→0} t(1 − t)^{k−1} ∑_{n≥0} \frac{(1 − t)^{n}(xq^{−n})^{n}}{[n]_{q}!} = −t(1 − t)^{k−1}. \end{aligned}

Since letting x → 0 after evaluating at (xq^{−n}; t, q) makes no difference to letting x → 0 directly, it now follows from Lemma 2 that

\begin{matrix}B_{n}^{inv}(t, q) = (−q; q)_{n}D_{q}^{n}B^{inv}(xq^{−n}; t, q)|_{x=0} \\ = (−1)^{n}(−q; q)_{n} |\begin{matrix}1 & 1 & 0 & ⋯ & 0 & 0 \\ \frac{(1−t)}{(−q;q)_{1}} & −t & 1 & ⋯ & 0 & 0 \\ \frac{(1−t)^{2}}{(−q;q)_{2}} & −t(1 − t) & −[\begin{matrix}2 \\ 1 \end{matrix}]_{q}t & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ \frac{(1−t)^{n−1}}{(−q;q)_{n−1}} & −t(1 − t)^{n−2} & −\binom{n−1}{1}t(1 − t)^{n−3} & ⋯ & −[\begin{matrix}n−1 \\ n−2 \end{matrix}]_{q}t & 1 \\ \frac{(1−t)^{n}}{(−q;q)_{n}} & −t(1 − t)^{n−1} & −[\begin{matrix}n \\ 1 \end{matrix}]_{q}t(1 − t)^{n−2} & ⋯ & −[\begin{matrix}n \\ n−2 \end{matrix}]_{q}t(1 − t) & −[\begin{matrix}n \\ n−1 \end{matrix}]_{q}t \end{matrix}| . \end{matrix}

It is clear that B_{n}^{inv}(t, 1) = B_{n}(t). On the other hand, one can move the multiplicative factor (−q; q)_{n} of the determinantal expression in Theorem 7 into the determinant by multiplying each entry of the first column by (−q; q)_{n}, the resulting quantities (−q; q)_{n}/(−q; q)_{k} are q-analogues of powers of 2. In Theorem 4, powers of 2 are are distributed over the last n columns of the determinant. When q → 1, the determinantal expression in Theorem 7 does not reduce to become that in Theorem 4.

5 A recurrence relation for B_{n}^{inv}(t, q)

Unlike its type A counterpart, a recurrence relation for B_{n}^{inv}(t, q) was, up to now, apparently not in the literature. The goal of this final section is to fill in this gap. Before doing so, it is important to note that A_{n}^{inv}(t, q) and B_{n}^{inv}(t, q) are closely related with each other.

Proposition 8. For n ≥ 1, we have

B_{n}^{inv}(t, q) = ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q} \frac{(−q; q)_{n}(1 − t)^{n−k}A_{k}^{inv}(t, q)}{(−q; q)_{n−k}},  (8)

= ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q^{2}} (−q; q)_{k}(1 − t)^{n−k}A_{k}^{inv}(t, q).  (9)

Proof. An inspection of the denominator of B^{inv}(x; t, q) reveals that

1 − \frac{t}{1 − t} ∑_{n≥1} \frac{(1 − t)^{n}x^{n}}{[n]_{q}!} = \frac{1 − te(x(1 − t); q)}{1 − t}

so that

B^{inv}(x; t, q) = A^{inv}(x; t, q) ∑_{n≥0} \frac{(1 − t)^{n}x^{n}}{(−q; q)_{n}[n]_{q}!}.  (10)

Extracting the coefficients of x^{n} on both sides, we have

\frac{B_{n}^{inv}(t, q)}{(−q; q)_{n}[n]_{q}!} = ∑_{k=0}^{n} \frac{A_{k}^{inv}(t, q)(1 − t)^{n−k}}{[k]_{q}!(−q; q)_{n−k}[n − k]_{q}!},

whence (8). Since [2k]_{q}! = (1 + q)^{k}[k]_{q^{2}}! = (−q; q)_{k}[k]_{q}!, we have

[\begin{matrix}n \\ k \end{matrix}]_{q} = \frac{(−q; q)_{k}(−q; q)_{n−k}}{(−q; q)_{n}} [\begin{matrix}n \\ k \end{matrix}]_{q^{2}} .  (11)

Substituting (11) into (8), equality (9) follows.

Based on Stanley’s factorial generating function (5), Björner and Brenti [3, §7.2] generalized the factorial generating functions by descent numbers and lengths to other Coxeter families of which (10) in the preceding proof is a concrete type B realization. Compare (10) with [3, Exercise 7.2.5(b)].

Theorem 9. For n ≥ 1, B_{n}^{inv}(t, q) satisfies the following recurrence relation:

B_{n+1}^{inv}(t, q) = ∑_{k=0}^{n} [\begin{matrix}n + 1 \\ k \end{matrix}]_{q^{2}} (−q; q)_{k}[(−q; q)_{n+1−k}t + (1 − t)](1 − t)^{n−k}A_{k}^{inv}(t, q).

Proof. Starting from (9) with n + 1 in place of n, followed by using (6), we obtain

B_{n+1}^{inv}(t, q) = (−q; q)_{n+1}A_{n+1}^{inv}(t, q) + ∑_{k=0}^{n} [\begin{matrix}n + 1 \\ k \end{matrix}]_{q^{2}} (−q; q)_{k}(1 − t)^{n+1−k}A_{k}^{inv}(t, q)

= (−q; q)_{n+1} ∑_{k=0}^{n} [\begin{matrix}n + 1 \\ k \end{matrix}]_{q} t(1 − t)^{n−k}A_{k}^{inv}(t, q)

+ ∑_{k=0}^{n} [\begin{matrix}n + 1 \\ k \end{matrix}]_{q^{2}} (−q; q)_{k}(1 − t)^{n+1−k}A_{k}^{inv}(t, q)

= (−q; q)_{n+1} ∑_{k=0}^{n} [\begin{matrix}n + 1 \\ k \end{matrix}]_{q^{2}} \frac{(−q; q)_{k}(−q; q)_{n+1−k}}{(−q; q)_{n+1}} t(1 − t)^{n−k}A_{k}^{inv}(t, q)

+ ∑_{k=0}^{n} [\begin{matrix}n + 1 \\ k \end{matrix}]_{q^{2}} (−q; q)_{k}(1 − t)^{n+1−k}A_{k}^{inv}(t, q)

= ∑_{k=0}^{n} [\begin{matrix}n + 1 \\ k \end{matrix}]_{q^{2}} (−q; q)_{k}[(−q; q)_{n+1−k}t + (1 − t)](1 − t)^{n−k}A_{k}^{inv}(t, q).

It is not apparent that the sum on the right can be written as a combination of B_{k}^{inv}(t, q).

6 Two questions

In the preceding sections, we obtained expressions of Eulerian polynomials of types A, B, and D, as well as the “inv” analogues of types A and B q-Eulerian polynomials, as lower Hessenberg determinants.

Besides representing Eulerian polynomials, determinants also play important roles in the theory of symmetric functions. For instance, the Jacobi-Trudi identity is a determinantal representation of skew Schur functions in terms of homogeneous symmetric functions [16, §7.16]. In view of the present work, it is natural to ask

Question 10. Can a given determinant be interpreted in terms of symmetric functions?

Another occurrence of determinants is in the classical definition of Schur functions [16]:

a_{λ+δ}/a_{δ} = s_{λ}(x_{1}, …, x_{n}),

where λ is a partition of n with at most n parts, δ = (n − 1, n − 2, …, 0) and a_{λ+δ} = det(x_{i}^{λ_{i}+n−j})_{i,j=1}^{n}. Note that neither a_{λ+δ} nor a_{δ} is symmetric in x_{1}, …, x_{n}, but a_{λ+δ}/a_{δ} is. Extending Question 10, more generally, one can ask

Question 11. Can a given quotient of two determinants be interpreted in terms of symmetric functions?

7 Acknowledgments

The author thanks the anonymous referee for his invaluable comments/suggestions that have led to much improved presentation of this work.

References

[1] R. M. Adin, F. Brenti, and Y. Roichman, Descent numbers and major indices for the hyperoctahedral group, Adv. in Appl. Math. 27 (2001) 210–224.

[2] M. Aigner, A Course in Enumeration, Springer, 2007.

[3] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Springer, 2005.

[4] N. Bourbaki, Functions of a Real Variable, Springer-Verlag, 2004.

[5] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, European J. Combin. 15 (1994) 417–441.

[6] C.-O. Chow, On derangement polynomials of type B, Sém. Lothar. Combin. 55 (2006), Art. B55b.

[7] C.-O. Chow, A recurrence relation for the “inv” analogue of q-Eulerian polynomials, Electron. J. Combin. 17 (2010) #N22.

[8] C.-O. Chow, On derangement polynomials of type D, Taiwanese J. Math. 27 (2023) 629–646.

[9] C.-O. Chow, Some determinantal representations of derangement numbers and polynomials, submitted, 2023.

[10] C.-O. Chow, Some determinantal representations of derangement polynomials, submitted, 2023.

[11] J. Désarménien and D. Foata, The signed Eulerian numbers, Discrete Math. 99 (1992) 49–58.

[12] C. Krattenthaler, Advanced determinant calculus, Sém. Lothar. Combin. 42 (1999), Art. B42q.

[13] F. Qi, J.-L. Wang, and B.-N. Guo, A recovery of two determinantal representations for derangement numbers, Cogent Math. 3 (2016) 1232878.

[14] V. Reiner, Upper binomial posets and permutation statistics, European J. Combin. 14 (1993) 581–588.

[15] R. P. Stanley, Binomial posets, Möbius inversion and permutation enumeration, J. Combin. Theory Ser. A 20 (1976) 336–356.

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

2020 Mathematics Subject Classification: Primary 05A15. Secondary 05A05. Keywords: derangement polynomial, determinant, lower Hessenberg determinant.

Received February 7 2023; revised versions received June 24 2023; June 26 2023. Published in Journal of Integer Sequences, July 24 2023.

Return to Journal of Integer Sequences home page.