Séminaire Lotharingien de Combinatoire 55 (2006), Article B55b

ON DERANGEMENT POLYNOMIALS OF TYPE B

CHAK-ON CHOW

Abstract. Wachs [Proc. Amer. Math. Soc. 106 (1989), 273–278] studied the q-enumeration of derangements in the symmetric group 𝔖_{n} by the major index and obtained a q-analogue of the classical derangement number. We consider in this work the q-enumeration of derangements in the hyperoctahedral group B_{n} by the flag major index and obtain a q-analogue of the type B derangement number.

Let n ⩾ 1. Let B_{n} be the nth hyperoctahedral group, which is a Coxeter group of rank n, consisting of signed permutations of [n] := {1, 2, …, n}. We shall represent a signed permutation σ ∈ B_{n} by the word σ_{1}σ_{2} ⋯ σ_{n}, where σ_{i} = σ(i), i = 1, 2, …, n. The (type A) descent set of σ is D(σ) := {i ∈ [n − 1]: σ_{i} > σ_{i+1}}. A statistic derivable from D(σ) is the usual (type A) major index: maj(σ) := ∑_{i∈D(σ)} i. Let N(σ) := #{i ∈ [n]: σ_{i} < 0} be the number of negative letters of σ.

Two candidates for the type B major index, namely, the negative major index (nmaj) and the flag major index (fmaj), have recently been proposed and proven to be Mahonian, i.e.,

∑_{σ∈B_{n}} q^{fmaj(σ)} = ∑_{σ∈B_{n}} q^{nmaj(σ)} = ∑_{σ∈B_{n}} q^{l_{B}(σ)} = [2]_{q}[4]_{q} ⋯ [2n]_{q},

where [k]_{q} := 1 + q + q^{2} + ⋯ + q^{k−1} is a q-integer, fmaj(σ) := 2 maj(σ) + N(σ), and l_{B} the length function on B_{n}. By pairing with the negative descent number (ndes) and the flag descent number (fdes), respectively, these major indices are shown to satisfy a q-rational generating function generalizing the classical Carlitz identity. See [1, 2] for the definitions of undefined terms and the above mentioned results.

In a recent work, Chow and Gessel [5] studied the Euler-Mahonian pair (des_{B}, fmaj), where des_{B} is the type B descent number, on B_{n} and computed its q-rational generating function. This q-rational generating function reduces to the rational generating function for the type B Eulerian polynomial when q → 1, thus providing a natural type B generalization of the classical Carlitz identity. It is from this point of view that the flag major index (fmaj) plays the same role on the hyperoctahedral group B_{n} as the usual major index (maj) does on the symmetric group 𝔖_{n}.

A number of statistical studies on B_{n} sequel to [1, 2, 5] have been pursued by various authors. See, e.g., [6, 7, 9] which considered the flag and negative major indices as well as other permutation statistics in the more general setting of signed words and wreath products.

For n ⩾ 1, let 𝒟_{n} := {σ ∈ 𝔖_{n}: σ(i) ≠ i for all i ∈ [n]} be the set of all derangements in 𝔖_{n}. Wachs [11] considered derangement polynomials defined by d_{n}(q) := ∑_{σ∈𝒟_{n}} q^{maj(σ)} and showed combinatorially that

(1)  d_{n}(q) = [n]_{q}! ∑_{k=0}^{n} \frac{(−1)^{k}q^{\binom{k}{2}}}{[k]_{q}!} ,

where [n]_{q}! := [1]_{q}[2]_{q} ⋯ [n]_{q} is a q-factorial. Letting q → 1, the above formula reduces to the formula of the nth classical derangement number: d_{n} = n! ∑_{k=0}^{n}(−1)^{k}/k!. It is from this point of view that Wachs’ derangement polynomials are q-analogues of the derangement numbers.

We show in this work (Theorem 5) that d_{n}^{B}(q) := ∑_{σ∈𝒟_{n}^{B}} q^{fmaj(σ)} can be written as

d_{n}^{B}(q) = [2]_{q}[4]_{q} ⋯ [2n]_{q} ∑_{k=0}^{n} \frac{(−1)^{k}q^{2\binom{k}{2}}}{[2]_{q}[4]_{q} ⋯ [2k]_{q}} ,

where 𝒟_{n}^{B} := {σ ∈ B_{n}: σ(i) ≠ i for all i ∈ [n]} is the set of derangements in B_{n}. The first four d_{n}^{B}(q) are given as follows:

d_{1}^{B}(q) = q,
d_{2}^{B}(q) = q + 2q^{2} + q^{3} + q^{4},
d_{3}^{B}(q) = q + 3q^{2} + 4q^{3} + 5q^{4} + 5q^{5} + 4q^{6} + 4q^{7} + 2q^{8} + q^{9},
d_{4}^{B}(q) = q + 4q^{2} + 8q^{3} + 13q^{4} + 18q^{5} + 22q^{6} + 26q^{7} + 28q^{8} + 28q^{9} + 25q^{10}
+ 21q^{11} + 17q^{12} + 11q^{13} + 7q^{14} + 3q^{15} + q^{16}.

Following Wachs, for any signed permutation α ∈ B_{A}, where A = {a_{1} < a_{2} < ⋯ < a_{k}}, define the reduction of α to be the signed permutation in B_{k} obtained from α by replacing each letter α_{j} by (sgn α_{j})i if |α_{j}| = a_{i}, i = 1, 2, …, k. The derangement part of a signed permutation σ ∈ B_{n}, denoted dp(σ), is the reduction of the subword of non-fixed points of σ. For example, dp(5¯3¯1476¯2) = 4¯3¯15¯2. Note that the derangement part of a signed permutation is a signed derangement, and that conversely, any derangement in 𝒟_{k}^{B} and k-element subset of [n] determine a signed permutation in B_{n} with n − k fixed points. Hence, the number of signed permutations in B_{n} with a given derangement part in 𝒟_{k}^{B} is \binom{n}{k}.

Now let σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ B_{n}. A letter σ_{i} of σ is an excedant (respectively subcedant) of σ if σ_{i} > i (respectively σ_{i} < i). Let s(σ) and e(σ) be the number of subcedants and excedants of σ, respectively. It is clear that excedants of σ are necessarily positive. We now fix n and let k ⩽ n. For σ ∈ B_{k}, let σ̃ be the signed permutation of k letters obtained from σ by replacing its ith smallest (in absolute value) subcedant σ_{j} by (sgn σ_{j})i, i = 1, 2, …, s(σ), its ith smallest fixed point by s(σ) + i, i = 1, 2, …, k − s(σ) − e(σ), and its ith largest excedant by n − i + 1, i = 1, 2, …, e(σ). The map σ → σ̃ restricted to the symmetric group 𝔖_{k} is precisely the descent set preserving map used in [11]. If k = n then σ̃ ∈ B_{n}. If σ is a signed derangement, then σ̃ ∈ 𝒟_{A}^{B}, where A = {1, 2, …, s(σ)} ∪ {n − e(σ) + 1, n − e(σ) + 2, …, n}.

Lemma 1. Let σ ∈ B_{k}, k ⩽ n. Then D(σ) = D(σ̃) and N(σ) = N(σ̃).

ON DERANGEMENT POLYNOMIALS OF TYPE B 3

Proof. It is clear from the construction of σ̃ that N(σ) = N(σ̃). Let σ = σ_{1}σ_{2} ⋯ σ_{k} and σ̃ = σ̃_{1}σ̃_{2} ⋯ σ̃_{k}. For each i ∈ [k − 1], we shall show that i ∈ D(σ) if and only if i ∈ D(σ̃), by considering the nine possible designations of subcedant (s), excedant (e), and fixed point (f) to σ_{i} and σ_{i+1}. Since the letters σ̃_{i} are determined according to whether σ_{i} is a subcedant (e), a fixed point (f), or an excedant (e), and in this order, σ̃_{i} < σ̃_{i+1} if the designation of σ_{i} precedes that of σ_{i+1}.

Suppose that (σ_{i}, σ_{i+1}) is an (f, e) or (f, f) pair. Then σ_{i} = i < i + 1 ⩽ σ_{i+1} so that σ̃_{i} < σ̃_{i+1}. If (σ_{i}, σ_{i+1}) is an (f, s), then σ_{i} = i > i − 1 ⩾ σ_{i+1} so that σ̃_{i} > s(σ) ⩾ |σ̃_{i+1}| ⩾ σ̃_{i+1}.

Suppose now that (σ_{i}, σ_{i+1}) is an (s, f) or (s, e) pair. Then σ_{i} < i < i + 1 ⩽ σ_{i+1} so that σ̃_{i} < σ̃_{i+1}. If (σ_{i}, σ_{i+1}) is an (s, s), then since sgn σ_{i} = sgn σ̃_{i}, σ_{i} ≷ σ_{i+1} ≷ 0 if and only if σ̃_{i} ≷ σ̃_{i+1} ≷ 0, and σ_{i} ≷ 0 ≷ σ_{i+1} if and only if σ̃_{i} ≷ 0 ≷ σ̃_{i+1}.

Suppose finally that (σ_{i}, σ_{i+1}) is an (e, f) pair. Then σ_{i} ⩾ i + 2 > i + 1 = σ_{i+1} so that σ̃_{i} > σ̃_{i+1}; if (σ_{i}, σ_{i+1}) is an (e, s) pair, then σ_{i} > i ⩾ σ_{i+1} so that σ̃_{i} > σ̃_{i+1}; consider now (σ_{i}, σ_{i+1}) being an (e, e) pair. If σ_{i} (respectively σ_{i+1}) is the jth (respectively kth) largest excedant of σ, then σ_{i} ≶ σ_{i+1} if and only if j ≷ k if and only if σ̃_{i} = n − j + 1 ≶ n − k + 1 = σ̃_{i+1}. □

Let n_{1}, …, n_{r} be non-negative integers such that ∑_{i=1}^{r} n_{i} = n. Recall the q-multinomial coefficient

[\begin{matrix}n \\ n_{1}, …, n_{r} \end{matrix}]_{q} := \frac{[n]_{q}!}{[n_{1}]_{q}! ⋯ [n_{r}]_{q}!}.

Now let (N_{1}, …, N_{r}) be a partition of the set [n]. For each 1 ⩽ i ⩽ r let π_{i} be a permutation of the elements of N_{i}. Recall that a permutation σ ∈ 𝔖_{n} is a shuffle of π_{1}, π_{2}, …, π_{r} if, for every i, the letters of N_{i} appears in σ in the same order as the corresponding letters in π_{i}. The generating function of shuffles of permutations by their major index has been computed by Garsia and Gessel [8, Theorem 3.1].

Theorem 2 (Garsia-Gessel). Let sh(π_{1}, …, π_{r}) be the collection of all shuffles of given permutations π_{1}, π_{2}, …, π_{r}. Then

∑_{σ∈sh(π_{1},...,π_{r})} q^{maj(σ)} = [\begin{matrix}n \\ n_{1}, …, n_{r} \end{matrix}]_{q} q^{maj(π_{1})+···+maj(π_{r})},

where n_{i} is the length of π_{i} (1 ⩽ i ⩽ r).

Theorem 2 remains true if π_{1}, …, π_{r} are signed words of distinct letters from the totally ordered alphabet {−n < −n + 1 < ⋯ < −1 < 1 < 2 < ⋯ < n}. It is clear in this case that N(σ) = N(π_{1}) + ⋯ + N(π_{r}). Replacing q by q^{2}, followed by multiplication by q^{N(σ)} and noting that fmaj(σ) = 2 maj(σ) + N(σ), we have the following identity:

(2)  ∑_{σ∈sh(π_{1},...,π_{r})} q^{fmaj(σ)} = [\begin{matrix}n \\ n_{1}, …, n_{r} \end{matrix}]_{q^{2}} q^{fmaj(π_{1})+···+fmaj(π_{r})},

where n_{i} is the length of π_{i} (1 ⩽ i ⩽ r).

Theorem 3. Let α ∈ 𝒟_{k}^{B}, k ⩽ n, and γ = (s(α) + 1)(s(α) + 2) … (n − e(α)). Then the map φ: {σ ∈ B_{n}: dp(σ) = α} → sh(α̃, γ) defined by φ(σ) = σ̃ is a flag major index preserving bijection, i.e., fmaj(σ) = fmaj(φ(σ)).

Proof. The flag major index preserving property of φ is clear from Lemma 1. Since #{σ ∈ B_{n}: dp(σ) = α\} = # sh(α̃, γ) = \binom{n}{k}, to prove that φ is a bijection, it suffices to prove that φ({σ ∈ B_{n}: dp(σ) = α}) = sh(α̃, γ).

First, we claim that if σ ∈ B_{n} is such that dp(σ) = α, then σ̃ is obtained from σ by replacing the subword of non-fixed points of σ by α̃ and the subword of fixed points of σ by γ. Indeed, the subword of fixed points of σ is replaced by the word (s(σ) + 1)(s(σ) + 2) ⋯ (n − e(σ)), which is precisely γ since s(σ) = s(α) and e(σ) = e(α). Also since α is the reduction of the subword of non-fixed points of σ, the position of the ith smallest subcedant of α is the same as the position of the i smallest subcedant of σ in its subword of non-fixed points. The same is true for the ith largest excedant. Hence each subcedant and excedant of σ is replaced by the same letter that replaces the corresponding subcedant and excedant of α, which means that the subword of subcedants and excedants of σ is replaced by α̃. Thus φ(σ) = σ̃ ∈ sh(α̃, γ).

To finish the proof, we show that φ is surjective. Let τ ∈ sh(α̃, γ). Replace the α̃ subword by the signed permutation, of the subword positions, whose reduction is α, and the letters of the γ subword by their positions, we obtain a unique signed permutation σ ∈ B_{n} such that dp(σ) = α and φ(σ) = τ. □

Proposition 4. Let α ∈ 𝒟_{k}^{B} and 0 ⩽ k ⩽ n. Then

∑_{dp(σ)=α, σ∈B_{n}} q^{fmaj(σ)} = q^{fmaj(α)} [\begin{matrix}n \\ k \end{matrix}]_{q^{2}} .

Proof. This follows from

∑_{dp(σ)=α, σ∈B_{n}} q^{fmaj(σ)} = ∑_{σ∈sh(α̃,γ)} q^{fmaj(σ)} = q^{fmaj(α̃)} [\begin{matrix}n \\ k \end{matrix}]_{q^{2}} = q^{fmaj(α)} [\begin{matrix}n \\ k \end{matrix}]_{q^{2}} ,

where the first equality follows from Theorem 3, the second from (2), and the third from Lemma 1. □

Recall that the two q-exponential functions defined by

e(u; q) := ∑_{n⩾0} \frac{u^{n}}{(q; q)_{n}} , E(u; q) := ∑_{n⩾0} \frac{q^{\binom{n}{2}}u^{n}}{(q; q)_{n}} ,

satisfy E(−u; q)e(u; q) = 1 (which is what the so-called Gauß inversion [3, p. 96] amounts to), where

(u; q)_{n} := \begin{cases}1 & if n = 0, \\ (1 − u)(1 − uq) ⋯ (1 − uq^{n−1}) & if n ⩾ 1. \end{cases}

Theorem 5. For n ⩾ 1, we have

(i) d_{n}^{B}(q) = [2]_{q}[4]_{q} ⋯ [2n]_{q} ∑_{k=0}^{n} \frac{(−1)^{k}q^{2\binom{k}{2}}}{[2]_{q}[4]_{q} ⋯ [2k]_{q}} ,

(ii) ∑_{n⩾0}d_{n}^{B}(q)\frac{u^{n}}{[2]_{q}[4]_{q} ⋯ [2n]_{q}} = \frac{E(−u(1 − q); q^{2})}{1 − u},

(iii) d_{n+1}^{B}(q) = [2n + 2]_{q}d_{n}^{B}(q) + (−1)^{n+1}q^{2\binom{n+1}{2}}.

Proof. By virtue of the preceding proposition, we have

[2]_{q}[4]_{q} ⋯ [2n]_{q} = ∑_{σ∈B_{n}} q^{fmaj(σ)}

= ∑_{k=0}^{n} ∑_{α∈𝒟_{k}^{B}} ∑_{dp(σ)=α} q^{fmaj(σ)}

= ∑_{k=0}^{n} ∑_{α∈𝒟_{k}^{B}} q^{fmaj(α)} [\begin{matrix}n \\ k \end{matrix}]_{q^{2}}

= ∑_{k=0}^{n} [\begin{matrix}n \\ k \end{matrix}]_{q^{2}} d_{k}^{B}(q).

(3)

Since [2]_{q}[4]_{q} ⋯ [2n]_{q} = (1 + q)^{n}[n]_{q^{2}}!, (3) can be simplified as

(1 + q)^{n} = ∑_{k=0}^{n} \frac{d_{k}^{B}(q)}{[k]_{q^{2}}![n − k]_{q^{2}}!}.

Multiplying through by u^{n}/(1 − q^{2})^{n}, followed by summing over n ⩾ 0, we get

e(u; q^{2}) ∑_{n⩾0}d_{n}^{B}(q)\frac{u^{n}}{(q^{2}; q^{2})_{n}} = ∑_{n⩾0} \frac{u^{n}}{(1 − q)^{n}} ,

since (q^{2}; q^{2})_{n} = (1 − q^{2})^{n}[n]_{q^{2}}!. Multiplying the preceding equation by E(−u; q^{2}), followed by extracting the coefficients of u^{n}, we have

d_{n}^{B}(q) = ∑_{k=0}^{n} \frac{(−1)^{k}q^{2\binom{k}{2}}(q^{2}; q^{2})_{n}}{(q^{2}; q^{2})_{k}(1 − q)^{n−k}} = ∑_{k=0}^{n} \frac{(−1)^{k}q^{2\binom{k}{2}}[2]_{q}[4]_{q} ⋯ [2n]_{q}}{[2]_{q}[4]_{q} ⋯ [2k]_{q}} ,

which is (i). Since (q^{2}; q^{2})_{n} = (1 − q)^{n}[2]_{q}[4]_{q} ⋯ [2n]_{q}, we have

∑_{n⩾0}d_{n}^{B}(q)\frac{u^{n}}{(1 − q)^{n}[2]_{q}[4]_{q} ⋯ [2n]_{q}} = \frac{E(−u; q^{2})}{1 − u/(1 − q)}.

Replacing u by u(1 − q), we get (ii). (iii) is immediate from (i). □

Theorem 5(i) is the type B analogue of (1), in the sense that [2]_{q}[4]_{q} ⋯ [2n]_{q} (respextively [n]_{q}!) is the Poincaré series of B_{n} (respectively 𝔖_{n}). (See [4, Chapter 7].) By letting q → 1, E(−u(1 − q); q^{2}) → e^{−u/2} and Theorem 5 specializes to

\begin{aligned}∑_{n⩾0}d_{n}^{B} \frac{u^{n}}{2^{n}n!} & = \frac{e^{−u/2}}{1 − u}, \\ d_{n+1}^{B} & = 2(n + 1)d_{n}^{B} + (−1)^{n+1}, \\ d_{n}^{B} & = n! ∑_{k=0}^{n} \frac{(−1)^{k}2^{n−k}}{k!} , \end{aligned}

where d_{n}^{B} = d_{n}^{B}(1) is the derangement number of B_{n}; the last formula can also be obtained by a routine application of the principle of inclusion-exclusion [10, Chapter 2].

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] R. M. Adin and Y. Roichman, The flag major index and group actions on polynomial rings, European J. Combin. 22 (2001), 431–446.

[3] M. Aigner, Combinatorial Theory, Springer-Verlag, New York, 1979.

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

[5] C.-O. Chow and I. M. Gessel, On the descent numbers and major indices for the hyperoctahedral group, submitted, 2003.

[6] D. Foata and G.-N. Han, Signed words and permutations, II: the Euler-Mahonian polynomials, Electron. J. Combin. 11(2), Article #R22, 2005, 18 pages (The Stanley Festschrift).

[7] D. Foata and G.-N. Han, Signed words and permutations, III: the MacMahon Verfahren, Sém. Lothar. Combin., B54a, 2006, 20 pages (The Viennot Festschrift).

[8] A. Garsia and I. Gessel, Permutation statistics and partitions, Adv. Math. 31 (1979), 288–305.

[9] J. Haglund, N. Loehr and J. B. Remmel, Statistics on wreath products, perfect matchings and signed words, European J. Combin. 26 (2005), 835–868.

[10] R. P. Stanley, Enumerative Combinatorics, vol. 1, Cambridge University Press, Cambridge, 1997.

[11] M. Wachs, On q-derangement numbers, Proc. Amer. Math. Soc. 106 (1989), 273–278.

P.O. Box 91100, Tsimshatsui Post Office, Hong Kong

 E-mail address: cchow@alum.mit.edu