Séminaire Lotharingien de Combinatoire 49 (2003), Article B49e

TWO INVOLUTIONS FOR SIGNED EXCEDANCE NUMBERS

Gérald Ksavrelof and Jiang Zeng

Institut Girard Desargues Université Claude Bernard (Lyon 1) 69622 Villeurbanne Cedex, France

                  E-mail:{ksavrelo, zeng}@igd.univ-lyon1.fr

Abstract Two involutions on permutations and derangements are constructed. They lead to a direct evaluation of some signed Eulerian polynomials on permutations and derangements. The latter formulas, combined with the exponential formula, give a new derivation of the corresponding generating functions.

1 Introduction

Let n be a positive integer. A permutation σ of the set [n] := {1, …, n} has an excedance at i if σ(i) > i, for 1 ≤ i ≤ n. As usual, we denote the numbers of excedances, cycles and fixed points of σ by exc σ, cyc σ and fix σ, respectively. A fixed-point-free permutation is called a derangement. Let S_{n} (resp. D_{n}) be the set of permutations (resp. derangements) of [n]. For example, the permutation σ = σ(1) … σ(5)σ(6) = 3 2 6 5 4 1 ∈ S_{6} has the cycle decomposition (1, 3, 6)(2)(4, 5), so 2 is the only fixed point and σ has an excedance at 1, 3 and 4; finally cyc σ = 3, exc σ = 3 and fix σ = 1. Consider the following enumerative polynomial of S_{n} :

P_{n}(x, y, β) = ∑_{σ∈S_{n}} x^{exc σ}y^{fix σ}β^{cyc σ}.

Then P_{n}(x, 1, 1) is the classical Eulerian polynomial (cf. [8, Chap. 1]), and P_{n}(x, 0, 1) the counterpart for the derangements. For a combinatorial treatment of Eulerian polynomials the reader is referred to the seminal book of Foata and Schützenberger [5].

It is remarkable that when β = −1, these two polynomials have simple closed formulas :

P_{n}(x, 1, −1) = −(x − 1)^{n−1},  (1)
P_{n}(x, 0, −1) = −x − x^{2} − ⋯ − x^{n−1}.  (2)

Although P_{n}(x, 0, −1) is a special case of P_{n}(x, y, β), its evaluation does imply the exponential generating function of P_{n}(x, y, β). Actually, weighting each permutation σ by the monomial x^{exc σ}y^{fix σ}(−1)^{cyc σ}, the counting polynomial for permutations in S_{n} with k chosen fixed points for 0 ≤ k ≤ n is (−y)^{k}P_{n−k}(x, 0, −1), hence we deduce from (2) that

P_{n}(x, y, −1) = ∑_{k=0}^{n} \binom{n}{k}(−y)^{k}P_{n−k}(x, 0, −1) = \frac{(x − y)^{n} − x(1 − y)^{n}}{1 − x} .  (3)

Now, according to the exponential formula (cf. [5], [8, Chap. 5]) and the evident identity e^{x} = (e^{−x})^{−1}, we have

1 + ∑_{n≥1} P_{n}(x, y, β)\frac{t^{n}}{n!} = [exp (− ∑_{n≥1} ∑_{σ∈C_{n}} x^{exc σ}y^{fix σ} \frac{t^{n}}{n!})]^{−β} ,  (4)

where C_{n} denotes the set of cyclic permutations in S_{n}. Setting β = −1 in (4) we see that the expression under brackets in (4) is equal to 1 + ∑_{n≥1} P_{n}(x, y, −1)t^{n}/n!, hence

1 + ∑_{n≥1} P_{n}(x, y, β)\frac{t^{n}}{n!} = (∑_{n≥0} \frac{(x − y)^{n} − x(1 − y)^{n}}{1 − x} \frac{t^{n}}{n!})^{−β} .  (5)

Conversely, it is a simple matter to derive (2) from (5) with β = 1 and y = 0, so (2) is actually equivalent to (5), of which the β = 1 case was already given by Foata and Schützenberger [5].

Note that the polynomial P_{n}(x, y, β) can also be interpreted through some linear statistics on permutations. Identify each permutation σ ∈ S_{n} with the word σ(1)σ(2) … σ(n). An integer i, 1 ≤ i ≤ n − 1, is a descent (resp. succession) of σ if σ(i) > σ(i + 1) (resp. σ(i + 1) = σ(i) + 1), and an integer j = σ(i) for some i ∈ [n] is a left-to-right maximum of σ if σ(k) < j for all k < i. Let des σ, suc σ and lrm σ be the numbers of descents, successions and left-to-right maxima of σ, respectively. Then, thanks to the fundamental transformation of Foata and Schützenberger [5], we have also

P_{n}(x, y, β) = ∑_{σ∈S_{n}} x^{des σ}y^{suc σ}β^{lrm σ}.

For some latest developments of the above fundamental transformation on words we refer the reader to a recent paper by Foata and Han [4].

Our purpose is to provide bijective proofs to the identities (1) and (2). In particular, this bijective approach leads to the following refinement of (2), which seems to be new.

Theorem 1 Let D_{n,j} = {σ ∈ D_{n} | σ(n) = j} for j ∈ [n − 1]. Then

∑_{σ∈D_{n,j}}(−1)^{cyc σ}x^{exc σ} = −x^{n−j}.  (6)

This paper was motivated by several recent papers: after deriving (1) from its generating function, which is equivalent to formula (5) with y = 1, Brenti [1, p.163] asked for a bijective proof, Chapman [2] gave a bijective proof of (2) when x = 1, Gessel [6] gave a combinatorial proof of (5) when β = x = 1 and y = 0, and Kim and Zeng [7] have given a direct combinatorial proof of (5) when β = 1 and y = 1 or 0, see also [3, 9] for some related problems.

In Section 2 we first give a bijective proof of the following recurrences:

P_{n}(x, 1, −1) = (x − 1)P_{n−1}(x, 1, −1),  n ≥ 3,  (7)
P_{n}(x, 0, −1) = P_{n−1}(x, 0, −1) − x^{n−1},  n ≥ 3.  (8)

Since P_{2}(x, 1, −1) = 1 − x and P_{2}(x, 0, −1) = −x, (7) implies (1) and (8) implies (2). The reason for including such recursive proofs of (1) and (2) is that they use simpler involutions than the bijective ones. In Section 3 we then give a second proof of (1) and (2) (in fact (6)) based on a direct interpretation of their right-sides.

All our four involutions are constructed by composing (from right to left) a permutation σ with a transposition (i, j). It is easy to see that the number of the cycles of the resulting permutation will be increased by one if i and j are in the same cycle of σ, and decreased by one otherwise.

The weight of a permutation σ ∈ S_{n} is w(σ) = (−1)^{cyc σ}x^{exc σ}, and that of a subset E ⊆ S_{n} is the sum of the weights of its elements, i.e., w(E) = ∑_{σ∈E} w(σ). Therefore, the basic idea of proving an identity is then to construct a subset E of S_{n} whose weight is the right-side of the identity; and a killing involution on S_{n} \ E, i.e. an involution which preserves the number of excedances but changes the sign of the weight of each element.

2 Involutions for recursive proofs

2.1 Permutations

Define the involution ϕ_{1} on S_{n} by

σ ↦ σ′ = (σ(n − 1), σ(n)) ∘ σ.

Clearly σ′(j) = σ(j) if j ≠ n − 1, n, σ′(n − 1) = σ(n), and σ′(n) = σ(n − 1). Let’s partition S_{n} into three subsets:

S_{n}^{1} = {σ ∈ S_{n} | σ(n − 1) ≠ n, σ(n) ≠ n},
S_{n}^{2} = {σ ∈ S_{n} | σ(n) = n},
S_{n}^{3} = {σ ∈ S_{n} | σ(n − 1) = n}.

It is easy to check that the restriction of ϕ_{1} to S_{n}^{1} is a killing involution, and the mapping σ ↦ σ′′ = σ(1)σ(2) ⋯ σ(n−1) is a bijection from S_{n}^{2} to S_{n−1} such that w(σ) = −w(σ′′), so the weight of S_{n}^{2} is −P_{n−1}(x, 1, −1). Finally the restriction of ϕ_{1} to S_{n}^{3} is a bijection from S_{n}^{3} to S_{n}^{2} such that w(σ) = −x w(σ′). So the weight of S_{n}^{3} is xP_{n−1}(x, 1, −1). Summarizing the above three cases yields (7).

2.2 Derangements

Let U_{n} = {σ ∈ D_{n} | σ(2) = 1 and σ(1) ≠ 2}. Clearly the mapping σ ↦ σ′′ = σ̄(1)σ̄(3) ⋯ σ̄(n), where σ̄(i) = σ(i) − 1, is a weight preserving bijection from U_{n} to D_{n−1}, so w(U_{n}) = P_{n−1}(x, 0, −1). Note also that the weight of the cyclic permutation σ_{0} = (1, 2, …, n) is −x^{n−1}. Hence, to prove (8) it remains to construct a killing involution on \overline{D}_{n} = D_{n} \ (U_{n} ∪ \{σ_{0}\}). We claim that φ_{1} : σ ↦ (σ(i_{σ}), σ(i_{σ} + 1)) ∘ σ is such an involution on \overline{D}_{n}, where i_{σ} is the smallest integer i ∈ [n − 1] such that σ(i) ≠ i + 1.

We first show that φ_{1} is an involution on \overline{D}_{n}. Let σ ∈ \overline{D}_{n}.

• φ_{1}(σ) ∈ D_{n} : if i_{σ} = 1, then σ(1) ≠ 2 and by definition of σ, σ(2) ≠ 1; if i_{σ} ≠ 1, then σ(i_{σ}) ≠ i_{σ} + 1 and σ(i_{σ} + 1) ≠ i_{σ} since i_{σ} is the image of i_{σ} − 1 by definition of i_{σ}.

• φ_{1}(σ) ∉ U_{n} ∪ {σ_{0}} : If i_{σ} = 1, φ_{1}(σ)(2) = σ(1) ≠ 1 since σ ∈ D_{n}; otherwise φ_{1}(σ)(1) = σ(1) = 2. So φ_{1}(σ) ∉ U_{n}, moreover φ_{1}(σ) ≠ σ_{0} because

φ_{1}(σ)(i_{σ}) = σ(i_{σ} + 1) ≠ i_{σ} + 1,  (9)

• φ_{1} is an involution : for all j < i_{σ}, φ_{1}(σ)(j) = σ(j) = j + 1, so φ_{1}(σ) = i_{σ} in view of (9).

Next, we check that exc φ_{1}(σ) = exc σ: if σ(i_{σ}) > i_{σ} (resp. < i_{σ}), then φ_{1}(σ)(i_{σ} + 1) = σ(i_{σ}) > i_{σ} + 1 (resp. < i_{σ} + 1); if σ(i_{σ} + 1) < i_{σ} + 1 (resp. > i_{σ} + 1), then φ_{1}(σ)(i_{σ}) = σ(i_{σ} + 1) < i_{σ} (resp. > i_{σ}) since i_{σ} is the image of i_{σ} − 1. Note that the number of cycles changes by one, and so our involution reverses sign, and hence is a killing involution on \overline{D}_{n}.

3 Involutions for bijective proofs

3.1 Permutations

Let Ω_{n} denote the set of permutations σ in S_{n}, whose cycle decomposition consists of a k-cycle, k ≥ 1, such that

σ(1) < σ^{2}(1) < ⋯ < σ^{k−1}(1),  (10)

and n − k singletons. Set C_{σ}(1) = {1, σ(1), …, σ^{k−1}(1)}, the orbit of σ containing 1. It is not hard to see that the weight of Ω_{n} is −(x − 1)^{n−1}. Therefore, to prove (2), it remains to construct a killing involution on \overline{Ω}_{n} = S_{n} \ Ω_{n}. Each permutation σ in \overline{Ω}_{n} can be characterized by the condition that either the k-cycle containing 1 does not satisfy the condition (10) or there exists an m-cycle (m > 1) disjoint with C_{σ}(1); in other words, there exists i ∈ [n] such that

i ∈ C_{σ}(1) and σ^{−1}(i) > i > 1, or i ∉ C_{σ}(1) and σ(i) ≠ i.  (11)

\begin{matrix}σ with i_{σ} ∈ C_{σ}(1) & i_{σ} & j_{σ} & (σ(j_{σ}), σ(i_{σ})) & ϕ_{2}(σ) \\ 3 4 2 1=(1,3,2,4) & 2 & 1 & (3,4) & 4 3 2 1=(1,4)(2,3) \\ 3 1 4 2=(1,3,4,2) & 2 & 1 & (3,1) & 1 3 4 2=(1)(2,3,4) \\ 4 3 1 2=(1,4,2,3) & 2 & 1 & (4,3) & 3 4 1 2=(1,3)(2,4) \\ 4 1 2 3=(1,4,3,2) & 2 & 1 & (4,1) & 1 4 2 3=(1)(2,4,3) \\ 2 4 1 3=(1,2,4,3) & 3 & 2 & (4,1) & 2 1 4 3=(1,2)(3,4) \\ 3 1 2 4=(1,3,2)(4) & 2 & 1 & (3,1) & 1 3 2 4=(1)(2,3)(4) \\ 4 1 3 2=(1,4,2)(3) & 2 & 1 & (4,1) & 1 4 3 2=(1)(2,4)(3) \\ 4 2 1 3=(1,4,3)(2) & 3 & 1 & (4,1) & 1 2 4 3=(1)(2)(3,4) \end{matrix}

Table 1: Involution ϕ_{2} for n = 4

Let i_{σ} denote the smallest integer satisfying (11) and j_{σ} the largest integer < i_{σ} in C_{σ}(1). Then we claim that the mapping ϕ_{2} : σ ↦ σ ∘ (i_{σ}, j_{σ}) is a killing involution on \overline{Ω}_{n}.

• Assume that i_{σ} ∈ C_{σ}(1), then there exist integers p, q ≥ 0 such that q < p, i_{σ} = σ^{p}(1), j_{σ} = σ^{q}(1) and the only elements < i_{σ} in C_{σ}(1) are 1, σ(1), …, σ^{q}(1) = j_{σ}. It follows that i_{ϕ_{2}(σ)} = i_{σ} and ϕ_{2} is an involution. It remains to check the corresponding values of σ and ϕ_{2}(σ) at i_{σ} and j_{σ}. Clearly σ(j_{σ}) > i_{σ} and σ(i_{σ}) < i_{σ} (resp. > i_{σ}) if σ(i_{σ}) = 1 (resp. otherwise). On the other hand, ϕ_{2}(σ)(i_{σ}) = σ(j_{σ}) > i_{σ} and

ϕ_{2}(σ)(j_{σ}) = \{ \begin{matrix}σ(i_{σ}) = 1 ≤ j_{σ} & if σ(i_{σ}) = 1; \\ σ(i_{σ}) > i_{σ} > j_{σ} & otherwise. \end{matrix}

So exc ϕ_{2}(σ) = exc σ.

• The case where i_{σ} ∉ C_{σ}(1) can be proved similarly. Note that if i_{σ} ∉ C_{σ}(1), then i_{σ} is the smallest element in C_{σ}(i_{σ}), and the only elements < i_{σ} in C_{σ}(1) are 1, σ(1), …, j_{σ}, arranged in increasing order. The rest of the verification is left to the reader.

Remark. 1. Since n ∉ \{i_{σ}, j_{σ}\} for σ ∈ \overline{Ω}_{n}, we see that ϕ_{2} is actually a killing involution on \overline{Ω}_{n,j} := \{σ ∈ \overline{Ω}_{n} | σ(n) = j\} for j ∈ [n].

2. It is also easy to see that ϕ_{2} is a bijection between permutations σ ∈ \overline{Ω}_{n} such that i_{σ} ∈ C_{σ}(1) and those σ ∈ \overline{Ω}_{n} such that i_{σ} ∉ C_{σ}(1).

We end with an example of ϕ_{2} for n = 4 in Table 1. As observed above, we need only to apply ϕ_{2} to permutations σ ∈ \overline{Ω}_{n} with i_{σ} ∈ C_{σ}(1).

3.2 Derangements

Fix j ∈ [n − 1] and set D_{n,j} = {σ ∈ D_{n} | σ(n) = j}. By definition, the weight of each σ ∈ D_{n,j} is (−1)^{cyc σ}x^{exc σ}, hence the weight of the cyclic permutation

σ_{j} = (n, j, j + 1, …, n − 1, j − 1, j − 2, …, 2, 1) ∈ D_{n,j}

is −x^{n−j}, to prove (6) it remains to construct a killing involution on \overline{D}_{n,j} = D_{n,j} \ \{σ_{j}\}.

For a, b ∈ [n], we say that a is smaller than b, denoted a ≺ b, if a is to the left of b in the word:

w_{j} = n 1 2 … (j − 2) (j − 1) (n − 1) … (j + 1) j.

For σ ∈ \overline{D}_{n,j} = D_{n,j} \ \{σ_{j}\} denote by i_{σ} the smallest integer i in the above word such that σ(i) ≠ σ_{j}(i). We notice that i_{σ} ≠ n because σ and σ_{j} have the same value j at n, and also i_{σ} ≠ j because, otherwise, σ and σ_{j} differ only at j and coincide at all the other k ≠ j.

We claim that φ_{2} : σ ⟶ (i_{σ}, σ_{j}(i_{σ})) ∘ σ is a killing involution on \overline{D}_{n,j}. It suffices to check the following points :

• φ_{2}(σ) ∈ D_{n}: First, by definition of i_{σ}, σ(i_{σ}) ≠ σ_{j}(i_{σ}). Secondly, if i_{σ} = 1 then σ(σ_{j}(i_{σ})) = j ≠ i_{σ}; otherwise σ(σ_{j}(i_{σ})) = σ_{j}^{2}(i_{σ}) ≺ i_{σ} since σ_{j} maps each k ≠ n to his left in w_{j}. Thus σ(σ_{j}(i_{σ})) ≠ i_{σ}.

• φ_{2}(σ) ∈ D_{n,j} : Since i_{σ} ≠ j and i_{σ} ≠ n then j ∉ {i_{σ}, σ_{j}(i_{σ})}. It follows that φ_{2}(σ)(n) = j.

• φ_{2}(σ) ≠ σ_{j} and i_{φ_{2}(σ)} = i_{σ} : For k ≺ i_{σ} and k ≠ n, since σ(k) = σ_{j}(k) ≠ σ_{j}(i_{σ}) and σ(k) = σ_{j}(k) ≺ k ≺ i_{σ}, then σ(k) ∉ {i_{σ}, σ_{j}(i_{σ})}, which implies that φ_{2}(σ)(k) = σ_{j}(k). Since φ_{2}(σ)(i_{σ}) = σ(i_{σ}) ≠ σ_{j}(i_{σ}), then φ_{2}(σ) ≠ σ_{j} and i_{φ_{2}(σ)} = i_{σ}.

• exc φ_{2}(σ) = exc σ : It suffices to check the values of φ_{2}(σ) and σ at k ∈ [n − 1] such that σ(k) = i_{σ} or σ(k) = σ_{j}(i_{σ}). If i_{σ} ≤ j − 1 then σ maps 1, 2, …, i_{σ} − 1 respectively to n, 1, …, i_{σ} − 2, so σ^{−1}(i_{σ}) > i_{σ} and σ^{−1}(i_{σ} − 1) > i_{σ}; if i_{σ} = n − 1 then σ maps 1, 2, …, j − 1 respectively to n, 1, …, j − 2, moreover σ^{−1}(j) = n, so j − 1 < σ^{−1}(n − 1) < n − 1 and j − 1 < σ^{−1}(j − 1) < n − 1; if i_{σ} ∈ {n−2, …, j +1} then σ maps 1, 2, …, j − 2, j −1, n−1, …, i_{σ} +1 respectively to n, 1, …, j −1, n−1, …, i_{σ} +2, so σ^{−1}(i_{σ}) < i_{σ} and σ^{−1}(i_{σ} +1) < i_{σ}. Summarizing ϕ_{2}(σ) and σ have the same number of excedances at σ^{−1}(i_{σ}) and σ^{−1}(σ_{j}(i_{σ})).

As an example, we illustrate φ_{2} for n = 5. There are four subsets \overline{D}_{5,j} (1 ≤ j ≤ 4) :

• subset \overline{D}_{5,4} : σ_{4} = 5 1 2 3 4, w_{4} = 5 1 2 3 4,

\begin{matrix}σ & i_{σ} & σ_{4}(i_{σ}) & (i_{σ}, σ_{4}(i_{σ})) ∘ σ \\ 2 1 5 3 4=(1,2)(3,5,4) & 1 & 5 & 2 5 1 3 4=(1,2,5,4,3) \\ 2 3 1 5 4=(1,2,3)(4,5) & 1 & 5 & 2 3 5 1 4=(1,2,3,5,4) \\ 3 1 2 5 4=(1,3,2)(4,5) & 1 & 5 & 3 5 2 1 4=(1,3,2,5,4) \\ 3 5 1 2 4=(1,3)(2,5,4) & 1 & 5 & 3 1 5 2 4=(1,3,5,4,2) \\ 5 3 2 1 4=(1,5,4)(2,3) & 2 & 1 & 5 3 1 2 4=(1,5,4,2,3) \end{matrix}

• subset \overline{D}_{5,3} : σ_{3} = 5 1 4 2 3, w_{3} = 5 1 2 4 3,

\begin{matrix}σ & i_{σ} & σ_{3}(i_{σ}) & (i_{σ}, σ_{3}(i_{σ})) ∘ σ \\ 2 1 4 5 3=(1,2)(3,4,5) & 1 & 5 & 2 5 4 1 3=(1,2,5,3,4) \\ 2 4 5 1 3=(1,2,4)(3,5) & 1 & 5 & 2 4 1 5 3=(1,2,4,5,3) \\ 4 1 5 2 3=(1,4,2)(3,5) & 1 & 5 & 4 5 1 2 3=(1,4,2,5,3) \\ 4 5 2 1 3=(1,4)(2,5,3) & 1 & 5 & 4 1 2 5 3=(1,4,5,3,2) \\ 5 4 1 2 3=(1,5,3)(2,4) & 2 & 1 & 5 4 2 1 3=(1,5,3,2,4) \end{matrix}

• subset \overline{D}_{5,2} : σ_{2} = 5 3 4 1 2, w_{2} = 5 1 4 3 2,

\begin{matrix}σ & i_{σ} & σ_{2}(i_{σ}) & (i_{σ}, σ_{2}(i_{σ})) ∘ σ \\ 3 4 1 5 2=(1,3)(2,4,5) & 1 & 5 & 3 4 5 1 2=(1,3,5,2,4) \\ 3 5 4 1 2=(1,3,4)(2,5) & 1 & 5 & 3 1 4 5 2=(1,3,4,5,2) \\ 4 3 5 1 2=(1,4)(2,3,5) & 1 & 5 & 4 3 1 5 2=(1,4,5,2,3) \\ 4 5 1 3 2=(1,4,3)(2,5) & 1 & 5 & 4 1 5 3 2=(1,4,3,5,2) \\ 5 1 4 3 2=(1,5,2)(3,4) & 4 & 1 & 5 4 1 3 2=(1,5,2,4,3) \end{matrix}

• subset \overline{D}_{5,1} : σ_{1} = 2 3 4 5 1, w_{1} = 5 4 3 2 1,

\begin{matrix}σ & i_{σ} & σ_{1}(i_{σ}) & (i_{σ}, σ_{1}(i_{σ})) ∘ σ \\ 2 5 4 3 1=(1,2,5)(3,4) & 4 & 5 & 2 4 5 3 1=(1,2,4,3,5) \\ 3 4 5 2 1=(1,3,5)(2,4) & 4 & 5 & 3 5 4 2 1=(1,3,4,2,5) \\ 5 3 4 2 1=(1,5)(2,3,4) & 4 & 5 & 4 3 5 2 1=(1,4,2,3,5) \\ 5 4 2 3 1=(1,5)(2,4,3) & 4 & 5 & 4 5 2 3 1=(1,4,3,2,5) \\ 4 3 2 5 1=(1,4,5)(2,3) & 3 & 4 & 3 4 2 5 1=(1,3,2,4,5) \end{matrix}

Remark. Chapman [2] has given a bijective proof of (6) with x = 1, but his involution does not work for our purpose.

References

[1] F. Brenti: A Class of q-Symmetric Function Arising from Plethysm, J. Combin. Theory Ser. A, 91 (2000), 137-170.

[2] R. Chapman: An involution on derangements, Discrete Math., 231 (2001), 121–122.

[3] J. Désarménien: Une autre interprétation du nombre des dérangements, Actes 8^{e} Séminaire Lotharingien, B08b, ed. D. Foata, publ. IRMA Strasbourg (1984), 11–16.

 (Available electronically at http://igd.univ-lyon1.fr/~slc.)

[4] D. Foata and G. N. Han: Further properties of the second fundamental transformation on words, preprint, october 2003.

[5] D. Foata and M. P. Schützenberger: Théorie géométrique des polynômes eulériens, Lecture Notes in Mathematics, Springer-Verlag, vol. 138, 1970.

[6] I. M. Gessel: A coloring problem, Amer. Math. Monthly, 98 (1991), 530–533.

[7] D. Kim and J. Zeng: A new decomposition of derangements, J. Combin. Theory Ser. A, 96 (2001), no. 1, 192–198.

[8] R. P. Stanley: Enumerative Combinatorics, vol. 1 and 2, Cambridge University Press, 1997.

[9] M. L. Wachs: An involution for signed Eulerian numbers, Discrete Math., 99, (1992), 59–62.