THE SIGNED EULERIAN NUMBERS

BY

Jacques DÉSARMÉNIEN (^{∗}) AND Dominique FOATA (^{∗∗})

To John Riordan, in memoriam.

ABSTRACT. — The basic relation between the signed Eulerian Numbers and the classical Eulerian Numbers is derived by using two different methods.

1. Introduction

LODAY [Lo] in his study of the cyclic homology of commutative algebras came across a sequence of numbers (B_{n,k}) related to the classical Eulerian numbers A_{n,k} as follows. The latter numbers are defined by the recurrence relation (see, e.g. [Ri, chap. 2])

(1.1)  A_{1,1} = 1 ;  A_{1,k} = 0 for k ≠ 1 ;

(1.2) A_{n,k} = kA_{n−1,k} + (n − k + 1)A_{n−1,k−1} ;

for n ≥ 2 and 1 ≤ k ≤ n, so that the first values are easily calculated, as shown in the next table.

k = 1  2  3  4  5  6 7
n = 1 1
2 1  1
3 1  4  1
4 1 11  11  1
5 1 26  66  26  1
6 1 57 302 302  57  1
7 1 120 1191 2416 1191 120 1

J. DÉSARMÉNIEN AND D. FOATA

The polynomial A_{n}(t) = ∑_{k=1}^{n} A_{n,k}t^{k} is called the n-th Eulerian polynomial. As it is well-known (see, e.g., [Ri, chap. 7]), A_{n}(t) is the generating polynomial for the permutation group 𝔖_{n} by the number of descents. More precisely, say that i is a descent of a permutation σ = σ(1) … σ(n) of order n, if 1 ≤ i ≤ n − 1 and σ(i) > σ(i + 1) and let des σ denote the number of descents of σ. It is straightforward to verify directly from the foregoing recurrence relation that the following identity

(^{∗}) Supported by the French Coordinated Research Program in Mathematics and Computer Science (^{∗∗}) Supported in part by NSF grant DMS 8901610 while the author was on leave (1989) at Drexel University, department of Mathematics, Philadelphia, PA 19104,USA.

(1.3)  A_{n}(t) = ∑_{σ∈S_{n}} t^{1+des σ},

holds, or, equivalently, if S_{n,k} denotes the set of all permutations of order n having (k − 1) descents, that

(1.4)  A_{n,k} = card S_{n,k}.

LODAY [Lo] introduced the numbers

(1.5)  B_{n,k} = ∑_{σ∈S_{n,k}} sgn σ,

where sgn σ designates the signature of σ, computed the first values and conjectured the following formulas

(1.6a)  B_{2n,k} = B_{2n−1,k} − B_{2n−1,k−1} ;
(1.6b)  B_{2n+1,k} = kB_{2n,k} + (2n − k + 2)B_{2n,k−1} ;

together with the analogs of the Worpitzky formulas

(1.7a)  ∑_{i} \binom{2n + i}{i}B_{2n,k−i} = k^{n} ;

(1.7b)  ∑_{i} \binom{2n − 1 + i}{i}B_{2n−1,k−i} = k^{n}.

The first values of the numbers B_{n,k} are shown in the next table.

k = 1 2  3 4 5 6 7
n = 1 1
2 1 −1
3 1 0 −1
4 1 −1 −1 1
5 1 2 −6 2 1
6 1 1 −8 8 −1 −1
7 1 8 −19 0 19 −8 −1

The purpose of this paper is to show what LODAY [Lo] had conjectured, namely that if (1.5) is the definition for the numbers (B_{n,k}), then those numbers satisfy the recurrence relations (1.6a) and (1.6b). The Worpitzky formulas (1.7a) and (1.7b) are easily derived from (1.6a) and (1.6b). Let

(1.8)  B_{n}(t) = ∑_{σ∈S_{n}} sgn σ t^{1+des σ}.

Then (1.6a) and (1.6b) can be rewritten as

(1.9a)  B_{2n}(t) = (1 − t)B_{2n−1}(t) ;
(1.9b)  B_{2n+1}(t) = (2n + 1) t B_{2n}(t) + t(1 − t)B′_{2n}(t) ;

where B′_{2n}(t) denotes the derivative of B_{2n}(t). As the recurrence relation (1.1) can also be expressed as

A_{n}(t) = ntA_{n−1}(t) + t(1 − t)A′_{n−1}(t),

it is straightforward to verify that proving the implication [(1.5) ⇒ (1.6a) & (1.6b)] is equivalent to proving the following theorem.

Theorem 1. — Let B_{n}(t) be the signed Eulerian polynomial defined in (1.8). Then

(1.10a)  B_{2n}(t) = (1 − t)^{n}A_{n}(t) ;
(1.10b)  B_{2n+1}(t) = (1 − t)^{n}A_{n+1}(t).

The polynomial B_{n}(t) can also be regarded as a specialization of one of the q-Eulerian polynomial A_{n}(t, q). If inv σ denotes the usual number of inversions of a permutation σ = σ(1) … σ(n), that is, the number of pairs (i, j) such that 1 ≤ i < j ≤ n and σ(i) > σ(j), then A_{n}(t, q) is defined to be (see, e.g., [St])

(1.11)  A_{n}(t, q) = ∑_{σ∈S_{n}} t^{1+des σ}q^{inv σ}.

As (−1)^{inv σ} is precisely equal to the signature sgn σ of the permutation σ, we have

B_{n}(t) = A_{n}(t, −1).

To prove THEOREM 1 it then suffices to work out with the various recurrence formulas dealing with the polynomials A_{n}(t, q), replace q by −1 and try to obtain the two formulas (1.10a) and (1.10b). As it will be seen in the next section, this program is achieved without any major difficulties.

Identities (1.10a) and (1.10b) suggest that there is a signed involution of 𝔖_{2n} that maps each element on another element with opposite weight, except those permutations which are in bijection with the set 2^{[n]} × 𝔖_{n}. Such an involution has just been found by Michelle WACHS [Wa].

More interesting is the fact that THEOREM 1 relates to a set of results on congruence properties of the q-Eulerian polynomials modulo a cyclotomic polynomial, a theory that was developed by the first author in [De2] in the context of the q-Kummer congruences. In fact, the forementioned theorem can even be regarded as a consequence of [De2, theorem 10.4]. However to make the present paper self-contained we have preferred to restate and reprove the basic results in a slightly different way.

The q-Eulerian polynomials A_{m,n}(t, q) (m ≥ 0, n ≥ 0) with two indices were introduced in [De2, § 10]. They may be defined by their generating function

(1.12) ∑_{m≥0, n≥0} A_{m,n}(t, q)\frac{u^{n}}{(q; q)_{n}} \frac{v^{m}}{m!} = \frac{1 − t}{1 − te((1 − t)u; q) exp((1 − t)v)},

where (q; q)_{n} and e(u; q) are, respectively, the q-ascending factorial and the first q-exponential whose definitions are recalled in the beginning of section 2. We shall not reprove that formula (1.12) does define a class of generating polynomials for the symmetric groups 𝔖_{m+n} by a pair of statistics. This result was derived by the first author from a calculation on Schur functions associated with ribbons [De2, § 10]. The two polynomials A_{n}(t, q) and A_{n}(t) are the following specializations of A_{m,n}(t, q)

(1.13)  A_{0,n}(t, q) = A_{n}(t, q) ;  A_{m,0}(t, q) = A_{m}(t),

as it can be directly seen from their generating functions shown in (2.3) and (2.4).

For each k let Φ_{k}(q) denote the k-th cyclotomic polynomial (Φ_{1}(q) = 1 − q; Φ_{2}(q) = 1 + q, etc…). Our purpose is also to prove the following theorem.

Theorem 2. — Let n and k be two positive integers and let n = ka+b, 0 ≤ b ≤ k − 1 be the Euclidean division of n by k. Then the following congruence holds :

A_{m,ka+b}(t, q) ≡ (1 − t)^{(k−1)a}A_{m+a,b}(t, q) mod Φ_{k}(q).

For k = 1 we then have

A_{a,1}(t, q) = A_{a+1,0}(t, q) = A_{a+1}(t),

for k = 2, b = 0, 1

A_{2a+b}(t, q) = A_{0,2a+b} ≡ (1 − t)^{a}A_{a,b}(t, q) mod (1 + q)
≡ (1 − t)^{a}A_{a+b}(t) mod (1 + q)
.

Thus THEOREM 1 is a particular case of THEOREM 2.

2. The q-Eulerian polynomials

As usual let

(u; q)_{n} = \{ \begin{matrix}1, & if n = 0; \\ (1 − u)(1 − uq) … (1 − uq^{n−1}), & if n ≥ 1; \end{matrix}

denote the q-ascending factorial and also let

(u; q)_{∞} = ∏_{n=0}^{∞}(1 − uq^{n}).

The two q-exponentials are then given by (see [An, chap. 2])

(2.1)  e(u; q) = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} = (u; q)_{∞}^{−1} ;

(2.2)  E(u; q) = ∑_{n≥0} q^{n(n−1)/2} \frac{u^{n}}{(q; q)_{n}} = (−u; q)_{∞}.

On the other hand, the exponential generating function for the Eulerian polynomials has the form

(2.3)  ∑_{n≥0} A_{n}(t)\frac{u^{n}}{n!} = \frac{1 − t}{1 − t exp((1 − t)u)},

(see, e.g., [Fo-Sch, p. 68]), while the generating function for the polynomials A_{n}(t, q), as it was derived probably for the first time by STANLEY [St], reads

(2.4)  ∑_{n≥0} A_{n}(t, q)\frac{u^{n}}{(q; q)_{n}} = \frac{1 − t}{1 − t e((1 − t)u; q)}.

Notice that (2.4) is obtained from (2.3) by replacing the factorial by the q-ascending factorial and the exponential by the first q-exponential. When the second q-exponential E(u; q) is used instead, we obtain other q-analogs of the Eulerian polynomials that also have a combinatorial interpretation (see, e.g., [De-Fo]).

The right-hand side of (2.4) is also equal to

(1 − t ∑_{n≥1}(1 − t)^{n−1} \frac{u^{n}}{(q; q)_{n}} )^{−1},

so that (2.4) is equivalent to the recurrence relation

(2.5)  A_{n}(t, q) = t(1 − t)^{n−1} + ∑_{1≤i≤n−1} \left[{n \atop i}\right]_{q}A_{i}(t, q) t (1 − t)^{n−1−i},

where \left[{n \atop i}\right]_{q} denotes the q-binomial coefficient (q; q)_{n}/(q; q)_{i}(q; q)_{n−i}. With q = 1 we obtain the recurrence relation for the Eulerian polynomials

(2.6)  A_{n}(t) = t(1 − t)^{n−1} + ∑_{1≤i≤n−1} \binom{n}{i}A_{i}(t) t (1 − t)^{n−1−i}.

Thus to calculate B_{n}(t) it suffices to let q tend to −1 in (2.5). It is readily seen that

lim_{q→−1} \left[{2m \atop 2i}\right]_{q} = lim_{q→−1} \left[{2m + 1 \atop 2i}\right]_{q} = lim_{q→−1} \left[{2m + 1 \atop 2i + 1}\right]_{q} = \binom{m}{i},

lim_{q→−1} \left[{2m \atop 2i + 1}\right]_{q} = 0.

Hence (2.5) yields

(2.7) B_{2n}(t) = t(1 − t)^{2n−1} + ∑_{1≤i≤n−1} \binom{n}{i}B_{2i}(t) t (1 − t)^{2n−1−2i};

(2.8) B_{2n+1}(t) = t(1 − t)^{2n} + ∑_{1≤i≤n} \binom{n}{i}B_{2i}(t) t (1 − t)^{2n−2i}

+ ∑_{0≤i≤n−1} \binom{n}{i}B_{2i+1}(t) t (1 − t)^{2n−2i−1}.

By comparing (2.6) and (2.7) we see that the polynomials (1 − t)^{n}A_{n}(t) satisfy the same recurrence relation as the polynomials B_{2n}(t). Hence (1.10a) holds.

To establish (1.10b) we proceed by induction on n. If (1.10b) holds up to (2n − 1), the right-hand side of (2.8) becomes

t(1−t)^{2n}+ ∑_{1≤i≤n} \binom{n}{i}A_{i}(t) t (1−t)^{2n−i}+ ∑_{0≤i≤n−1} \binom{n}{i}A_{i+1}(t) t (1−t)^{2n−1−i}

= t(1 − t)^{2n} + ∑_{1≤i≤n} \binom{n}{i}A_{i}(t) t (1 − t)^{2n−i}

+ ∑_{1≤i≤n} \binom{n}{i − 1}A_{i}(t) t (1 − t)^{2n−i}

= (1 − t)^{n}[t(1 − t)^{n} + ∑_{1≤i≤n} \binom{n + 1}{i}A_{i}(t) t (1 − t)^{(n+1)−1−i}]

= (1 − t)^{n}A_{n+1}(t),

by using recurrence relation (2.6) in the last step. This achieves the proof

of THEOREM 1.

3. Symmetric functions

Let x = (x_{1}, x_{2}, …) be an infinite sequence of variables and for each r = 1, 2, … denote by h_{r}(x) the homogeneous symmetric function in the x_{j}’s and by p_{r}(x) the power sum ∑_{j} x_{j}^{r}. By convention, h_{0}(x) = 1. The generating function H(u; x) = ∑_{r≥0} u^{r}h_{r}(x) can be evaluated in different forms :

(3.1)  H(u; x) = ∏_{j≥1}(1 − ux_{j})^{−1} = exp ∑_{r≥1} u^{r} \frac{p_{r}(x)}{r}.

(See, e.g., [Mac, p. 14 and 17].)

Recall that a partition of an integer n can be expressed as a nonincreasing sequence λ = (λ_{1}, λ_{2}, …) (λ_{1} ≥ λ_{2} ≥ ⋯), or as a word λ = 1^{m_{1}}2^{m_{2}} … (the multiplicative notation) with the meaning that λ has m_{1} parts λ_{i} equal to 1, m_{2} parts λ_{i} equal to 2, etc… As usual, to each partition λ we attach the constant

z_{λ} = 1^{m_{1}}2^{m_{2}} … m_{1}! m_{2}! …

and the power symmetric function

p_{λ}(x) = p_{λ_{1}}(x)p_{λ_{2}}(x) …

Also |λ| = n means that λ is a partition of n and the notation l(λ) stands for the number of parts of λ.

Now let (c_{i}) (i = 0, 1, …) be a sequence of elements belonging to some given field. The relation

(3.2)  ∑_{i≥0} C_{i} \frac{u^{i}}{i!} = ∑_{i≥0} c_{i}(e^{u} − 1)^{i}

defines a sequence (C_{i}) in a unique manner. Let v be another variable independent from u and the x_{j}’s and expand the series

∑_{i≥0} c_{i}(H(u; x)e^{v} − 1)^{i}.

We may write

(3.3)  ∑_{m≥0, n≥0} C_{m,n}(x)u^{n} \frac{v^{m}}{m!} = ∑_{i≥0} c_{i}(H(u; x)e^{v} − 1)^{i},

where each C_{m,n}(x) is a symmetric function in the x_{j}’s of degree n. Our first goal is to express each C_{m,n}(x) in the basis (p_{λ}(x)) of the ring of the symmetric functions.

Lemma 3.1. — Let C_{m,n}(x) be the symmetric function defined by (3.3). Then

(3.4)  C_{m,n}(x) = ∑_{λ} C_{m+l(λ)} \frac{p_{λ}(x)}{z_{λ}},  (|λ| = n),

where the C_{i} are the coefficients defined in (3.2).

Proof. — Expand the right-hand side of (3.3)

∑_{m≥0, n≥0} C_{m,n}(x)u^{n} \frac{v^{m}}{m!} = ∑_{i≥0} c_{i}(H(u; x)e^{v} − 1)^{i}

= ∑_{i≥0} c_{i}(exp(∑_{r} u^{r} \frac{p_{r}(x)}{r} + v) − 1)^{i}

= ∑_{a≥0} \frac{C_{a}}{a!} (∑_{r} u^{r} \frac{p_{r}(x)}{r} + v)^{a}, (3.5)

by (3.1) and (3.2). Thus C_{m,n}(x)/m! is equal to the coefficient of degree m in v and n in u of the expansion of the right-hand of (3.5). In short, write

\frac{C_{m,n}(x)}{m!} = [v^{m}u^{n}] ∑_{a≥0} \frac{C_{a}}{a!} (∑_{r} u^{r} \frac{p_{r}(x)}{r} + v)^{a}

= [v^{m}u^{n}] ∑_{b≥0} \frac{C_{m+b}}{(m + b)!}(∑_{r} u^{r} \frac{p_{r}(x)}{r} + v)^{m+b}

= [u^{n}] ∑_{b≥0} \frac{C_{m+b}}{m! b!} (∑_{r} u^{r} \frac{p_{r}(x)}{r})^{b}.

Hence

C_{m,n}(x) = [u^{n}] ∑_{b≥0} \frac{C_{m+b}}{b!} (∑_{r=1}^{n} u^{r} \frac{p_{r}(x)}{r})^{b}

= [u^{n}] ∑_{b≥0} \frac{C_{m+b}}{b!} ∑_{m_{1},m_{2},...} \frac{b!}{1!^{m_{1}}2!^{m_{2}} …}u^{n} \frac{p_{1}(x)^{m_{1}}}{1^{m_{1}}} \frac{p_{2}(x)^{m_{2}}}{2^{m_{2}}} …

[m_{1} + m_{2} + ⋯ = b; 1.m_{1} + 2.m_{2} + ⋯ = n.]

= ∑_{λ} C_{m+l(λ)} \frac{p_{λ}(x)}{z_{λ}}, (|λ| = n).

Next for each partition λ = 1^{m_{1}}2^{m_{2}} … of the integer n let

(3.6)  T_{λ}(q) = \frac{(q; q)_{n}}{∏_{j}(1 − q^{j})^{m_{j}}} = (q; q)_{n} p_{λ}(1, q, q^{2}, …).

It is easy to verify that T_{λ}(q) is a polynomial of degree n(n − 1)/2. Let

(3.7)  K_{m,n}(q) = (q; q)_{n} C_{m,n}(1, q, q^{2}, …).

By (3.4)

(3.8)  K_{m,n}(q) = ∑_{λ} C_{m+l(λ)} \frac{T_{λ}(q)}{z_{λ}}  (|λ| = n),

so that, by (3.6), K_{m,n}(q) is a polynomial in q of degree at most equal to n(n − 1)/2. Now replace each variable x_{i} by q^{i−1} (i = 1, 2, …) in (3.3) and use notation (3.7). We obtain the identity

(3.9)  ∑_{m≥0, n≥0} K_{m,n}(q)\frac{u^{n}}{(q; q)_{n}} \frac{v^{m}}{m!} = ∑_{i} c_{i}(e(u; q)e^{v} − 1)^{i}.

Lemma 3.2. — Let n = ka + b, 0 ≤ b ≤ k − 1 and λ = 1^{m_{1}}2^{m_{2}} … be a partition of n. Then the following congruences hold :

(i) if m_{k} ≠ a, then T_{λ}(q) ≡ 0 mod Φ_{k}(q).

(ii) if m_{k} = a, let λ^{∗} = 1^{m_{1}} … (k−1)^{m_{k−1}}(k+1)^{m_{k+1}} … be the partition obtained from λ by deleting the m_{k} = a parts equal to k. Then

T_{λ} ≡ k^{a}a! T_{λ^{∗}}(q) mod Φ_{k}(q).

The proof of the lemma follows from the following congruence already proved in ([De1], lemma 2.1) :

(q; q)_{n}/(1 − q^{k})^{a} ≡ k^{a}a! (q; q)_{b} mod Φ_{k}(q).

Note that when m_{k} = a, we have l(λ) = l(λ^{∗}) + a and z_{λ} = z_{λ^{∗}} k^{a}a! Reporting the foregoing congruences into (3.8) leads to

(3.10) K_{m,n}(q) ≡ ∑_{λ^{∗}} C_{m+l(λ^{∗})+a} \frac{T_{λ^{∗}}(q)}{z_{λ^{∗}}} mod Φ_{k}(q) (|λ^{∗}| = b).

In particular by (3.8)

K_{m+a,b}(q) = ∑_{λ^{∗}} C_{m+l(λ^{∗})+a} \frac{T_{λ^{∗}}(q)}{z_{λ^{∗}}} (|λ^{∗}| = b).

Therefore (3.11) K_{m,ka+b}(q) ≡ K_{m+a,b}(q) mod Φ_{k}(q).

4. Eulerian polynomials

We now apply the previous results to the sequence of the Eulerian polynomials. Let

(4.1)  c_{1} = \frac{t}{1 − t},  c_{i} = (c_{1})^{i} (i ≥ 1).

First, the generating functions (2.3), (2.4) and (1.12) may be rewritten as

(4.2)  ∑_{n≥0} \frac{A_{n}(t)}{(1 − t)^{n}} \frac{u^{n}}{n!} = ∑_{i≥0}(\frac{t}{1 − t})^{i}(e^{u} − 1)^{i},

(4.3)  ∑_{n≥0} \frac{A_{n}(t, q)}{(1 − t)^{n}} \frac{u^{n}}{(q; q)_{n}} = ∑_{i≥0}(\frac{t}{1 − t})^{i}(e(u; q) − 1)^{i},

(4.4) ∑_{n≥0} \frac{A_{m,n}(t, q)}{(1 − t)^{m+n}} \frac{v^{m}}{m!} \frac{u^{n}}{(q; q)_{n}} = ∑_{i≥0}(\frac{t}{1 − t})^{i}(e(u; q) exp v − 1)^{i},

so that when the c_{i}’s are given by (4.1), the coefficients C_{i} of (3.2) are equal to

(4.5)  C_{i} = \frac{A_{i}(t)}{(1 − t)^{i}}  (i ≥ 0).

When u = 0, formula (3.9) becomes

∑_{m≥0} K_{m,0}(q)\frac{v^{m}}{m!} = ∑_{i≥0} c_{i}(e^{v} − 1)^{i},

and for v = 0

∑_{n≥0} K_{0,n}(q)\frac{u^{n}}{(q; q)_{n}} = ∑_{i≥0} c_{i}(e(u; q) − 1)^{i}.

By comparison with (4.2), (4.3) and (4.4) we then have

\frac{A_{m}(t)}{(1 − t)^{m}} = K_{m,0}(q) = C_{m}, \frac{A_{n}(t, q)}{(1 − t)^{n}} = K_{0,n}(q),

and

\frac{A_{m,n}(t, q)}{(1 − t)^{m+n}} = K_{m,n}(q).

By (3.11) we conclude that

\frac{A_{m,ka+b}(t, q)}{(1 − t)^{m+ka+b}} ≡ \frac{A_{m+a,b}(t)}{(1 − t)^{m+a+b}} mod Φ_{k}(q),

i.e.,

A_{m,ka+b}(t, q) ≡ (1 − t)^{(k−1)a}A_{m+a,b}(t, q) mod Φ_{k}(q).

This achieves the proof of THEOREM 2.

Acknowledgement. — The authors should like to thank the two referees for their careful reading of the manuscript. They both corrected the recurrence formula (2.8) and spotted a few misprints.

REFERENCES

[An] ANDREWS (George E.). — The Theory of Partitions. — Reading, Mass., Addison-Wesley, 1976 (Enclycopedia of Math. and Its. Appl., 2).

[De1] D^{}ÉSARM^{}ÉNIEN (Jacques). — Un analogue des congruences de Kummer pour les q-nombres d’Euler, Europ. J. Combin., v. 3, 1982, p. 19–28.

[De2] D^{}ÉSARM^{}ÉNIEN (Jacques). — Fonctions symétriques associées à des suites clas-

siques de nombres, Ann. scient. Éc. Norm. Sup., v. 16, 1983, p. 271–304.

[De-Fo] D^{}ÉSARM^{}ÉNIEN (Jacques) et FOATA (Dominique). — Statistiques d’ordre sur les

permutations colorées, to appear in Discrete Math..

[Fo-Sch] FOATA (Dominique) and SCH^{}ÜTZENBERGER (Marcel-Paul). — Théorie géométrique des polynômes eulériens. — Berlin, Springer-Verlag, 1970 (Lecture Notes in Math., 138).

[Fo-Sch2] FOATA (Dominique) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Major Index and

Inversion of Permutations, Math. Nachr., v. 83, 1978, p. 143–159.

[Lo] LODAY (Jean-Louis). — Opérations sur l’homologie cyclique des algèbres commutatives, Inv. Math., v. 96, 1989, p. 205–230.

[Mac] MACDONALD (I.G.). — Symmetric Functions and Hall polynomials. — Oxford,

Clarendon Press, 1979.

[Ri] RIORDAN (John). — An Introduction to Combinatorial Analysis. — New York, J. Wiley, 1958.

[St] STANLEY (Richard P.). — Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A, v. 20, 1976, p. 336–356.

[Wa] WACHS (Michelle). — An involution for signed Eulerian numbers, submitted.

Jacques Désarménien, Département d’informatique, Institut universitaire de technologie, Université Robert-Schumann, 72, route du Rhin, F-67400 Illkirch-Graffenstaden.

email : A18630@FRCCSC21.BITNET

Dominique Foata,

Département de mathématique, Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg Cedex.

email : FOATA@FRCCSC21.BITNET