=Paper=
{{Paper
|id=Vol-2925/paper1
|storemode=property
|title=Bijective proofs for Eulerian numbers in types B and D
|pdfUrl=https://ceur-ws.org/Vol-2925/paper1.pdf
|volume=Vol-2925
|authors=Luigi Santocanale
|dblpUrl=https://dblp.org/rec/conf/algos/Santocanale20
}}
==Bijective proofs for Eulerian numbers in types B and D==
https://ceur-ws.org/Vol-2925/paper1.pdf
B IJECTIVE PROOFS FOR E ULERIAN NUMBERS IN TYPES B AND D
Luigi Santocanale
LIS, CNRS UMR 7020, Aix-Marseille Université, France
luigi.santocanale@lis-lab.fr
A BSTRACT
D E D E D E
Let nk , Bkn , and Dkn be the Eulerian numbers in the types A, B, and D, respectively—that is,
number of permutations of n elements with k descents, the number of signed permutations (of n el-
ements) with k type B descents, the number of even signed permutations (of n elements) with k type
P n 1 Dn E k P n DB n E k P n DDn E k
D descents. Let Sn (t) = k=0 k t and Bn (t) = k=0 k t , and Dn (t) = k=0 k t .
We give bijective proofs of the identity
Bn (t2 ) = (1 + t)n+1 Sn (t) 2n tSn (t2 ) .
and of Stembridge’s identity
Dn (t) = Bn (t) n2n 1 tSn 1 (t) .
These bijective proofs rely on a representation of signed permutations as paths. Using the same
representation we establish a bijective correspondence between even signed permutations and pairs
(w, E) with ([n], E) a threshold graph and w a degree ordering of ([n], E).
1 Introduction
For n 0, we use [n] for the set { 1, . . . , n } and Sn for the set of permutations of n-elements—that is, bijections of
[n]. We write a permutation w 2 Sn as a word w1 w2 . . . wn with wi 2 [n] and wi 6= wjD for E i 6= j. A descent of
w 2 Sn is an index (or position) i 2 [n 1] such that wi > wi+1 . The Eulerian number nk counts the number of
permutations w 2 Sn that have k descent positions. This is, of course, one among the many interpretations that we can
give to these numbers, see e.g. [14]. The given interpretation is closely related to order theory. Let us recall that the set
Sn can be endowed with a lattice structure, see e.g. [11, 6]. The lattice Sn is known under the name of Permutohedron
or weak D (Bruhat)
E order. Exploiting the bijection between descent positions and lower covers ofDwE2 Sn , the Eulerian
number k counts the number of permutations w 2 Sn with k lower covers. In particular, n1 = 2n n 1 is
n
the number of join-irreducible elements in Sn . A subtler order-theoretic interpretation is given in [2]: since the Sn are
(join-)semidistributive
D E as lattices, every element can be written canonically as the join of join-irreducible elements [9];
the numbers nk counts then the permutations w 2 Sn that can be written canonically as the join of k join-irreducible
elements.
The symmetric groups Sn are particular instances of Coxeter groups, see [4]. Under the usual classification of finite
Coxeter groups, the symmetric group Sn yields a concrete model for the Coxeter group An 1 in the family A. Similarly
to the symmetric groups, notions of length, descent, and inversion, and a weak order as well, can be defined for
elements of an arbitrary Coxeter group [3]. We move our focus to the families B and D of Coxeter D Egroups. DMore E
precisely, this paper concerns the Eulerian numbers in the types B and D. The Eulerian number Bkn (resp., Dkn )
counts the number of elements in the group Bn (resp., Dn ) with k descent positions. Order-theoretic interpretations
of these numbers, analogous to the ones mentioned for the standard Eulerian numbers, are still valid. As the abstract
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
group An 1 has a concrete realization as the symmetric group Sn , the group Bn (resp., Dn ) has a realization as the
hyperoctahedral group of signed permutations (resp., the group of even signed permutations). Starting from these
concrete representations of Coxeter groups in the types B and D, we pinpoint some new representations of signed
permutations relying on which we provide bijective proofs of known formulas for Eulerian numbers in the types B
and D. These formulas allow to compute the Eulerian numbers in the types B and D. from the better known Eulerian
numbers in type A.
Let Sn (t) and Bn (t) be the Eulerian polynomials in the types A and B:
X1 ⌧n
n n ⌧
X Bn k
Sn (t) := tk , Bn (t) := t . (1)
k k
k=0 k=0
In [14, §13, p. 215] the following polynomial identity is stated:
2Bn (t2 ) = (1 + t)n+1 Sn (t) + (1 t)n+1 Sn ( t) . (2)
P
Considering that, for f (t) = k 0 ak t
k
,
X
f (t) + f ( t) = 2 a2k t2k ,
k 0
the polynomial identity (2) amounts to the following identity among coefficients:
⌧ X2k ⌧ ✓ ◆
Bn n n+1
= . (3)
k i 2k i
i=0
We present a bijective proof of (3) and also establish the identity
⌧ X ⌧n ✓ n + 1 ◆
2k+1
n
2n = . (4)
k i 2k + 1 i
i=0
P
Considering that, for f (t) = k 0 ak tk ,
X
f (t) f ( t) = 2 a2k+1 t2k+1 ,
k 0
the identity (4) yields the polynomial identity:
2n+1 tSn (t2 ) = (1 + t)n+1 Sn (t) (1 t)n+1 Sn ( t) .
More importantly, (3) and (4) jointly yield the polynomial identity
(1 + t)n+1 Sn (t) = Bn (t2 ) + 2n tSn (t2 ) . (5)
Let now Dn (t) be the Eulerian polynomial in type D:
n ⌧
X Dn k
Dn (t) := t .
k
k=0
Investigating further the terms 2 Sn (t), we also ended up finding a simple bijective proof, that we present here, of
n
Stembridge’s identity [22, Lemma 9.1]
Dn (t) = Bn (t) n2n 1 tSn 1 (t) , (6)
which, in terms of the Eulerian numbers in type D, amounts to
⌧ ⌧ ⌧
Dn Bn n 1 n 1
= n2 .
k k k 1
Let us remark that the proofs presented here follow different paths from known proofs of the identities (2) and (6). As
suggested in [14], the first identity may be derived by computing the f -vector of the type B Coxeter complex and then
by applying the transform yielding h-vector from the f -vector. A similar method is used in [22] to prove the identity
(6). On the other hand, our proofs directly rely on the combinatorial properties of signed/even signed permutations and
on the representation of these objects that we call the path representation of a signed permutation and simply barred
permutations.
2 Notation, elementary definitions, and facts
The notation used is chosen to be consistent with [14]. As mentioned before, we use [n] for the set { 1, . . . , n } and
Sn for the set of permutations of [n]. We use [n]0 for the set { 0, 1, . . . , n }, [ n] for { n, . . . , 1 }, and [±n] for
{ n, . . . , 1, 1, . . . , n }. We write a permutation w 2 Sn as a word w = w1 w2 . . . wn , with wi 2 [n]. For w 2 Sn ,
its set of descents and its set of inversions1 are defined follows:
Des(w) := { i 2 { 1, . . . , n 1 } | wi > wi+1 } , Inv(w) := { (i, j) | 1 i < j n, w 1 (i) > w 1 (j) } .
Then, we let
des(w) := |Des(w)| .
D E
The Eulerian number nk , counting the number of permutations of n elements with k descents, can be formally
defined as follows:
⌧
n
:= |{ w 2 Sn | des(w) = k }| .
k
Let us define a signed permutation of [n] as a permutation u of [±n] such that, for each i 2 [±n], u i = ui . We use
Bn for the set of signed permutations of [n]. When writing a signed permutation u as a word u n . . . u 1 u1 . . . un ,
we prefer writing ui = x in place of x if ui < 0 and |ui | = x. Also, we often write u 2 Bn in window notation,
that is, we only write the suffix u1 u2 . . . un ; indeed, the prefix u n un 1 . . . u 1 is uniquely determined by the suffix
u1 u2 . . . un , by mirroring it and by exchanging the signs. Obviously, the set Bn is a group and, as mentioned before, it
is the standard model for a Coxeter group in the family B with n generators. Therefore, general notions from the theory
of Coxeter groups (descent, inversion) apply to signed permutations. We present below as definitions the well-known
explicit formulas for the descent and inversion sets of u 2 Bn . We let
DesB (u) := { i 2 { 0, . . . , n 1 } | ui > ui+1 } , InvB (u) := { (i, j) | 1 |i| j n, u 1 (i) > u 1 (j) } ,
where we set u0 := 0, so 0 is a descent of u if and only if u1 < 0,
⌧
Bn
desB (u) = |DesB (u)| , := |{ u 2 Bn | desB (u) = k }| .
k
Finally, and recalling the definition in (1) of the Eulerian polynomials in the types A and B, let us mention that the
type A Eulerian polynomial is often (for example in [5]) defined as follows:
Xn ⌧
n
An (t) := tk = tSn (t) .
k 1
k=1
We shall exclusively manipulate the polynomials Sn (t) and not the An (t). Notice that Sn (t) has degree n 1 and
Bn (t) has degree n.
We shall introduce later even signed permutations and their groups, as well as related notions arising from the fact that
these groups are standard models for Coxeter groups in the family D.
For the time being, let us observe the following. For u 2 Bn we let Des+ +
B (u) := DesB (u) \ { 0 }—thus DesB (u) is
the set of strictly positive descents of u. We have then:
D E
n n
Lemma 2.1. | { u 2 Bn | Des+ B (u) = k } | = 2 k .
Proof. By considering its window notation, a signed permutation u yields a mapping ũ : [n] ! [±n] with a unique
decomposition of the form ũ = ◆ w with w 2 Sn and ◆ : [n] ! [±n] an order preserving injection such that
x 2 ◆([n]) iff x 62 ◆([n]). The monotone injections with this property are uniquely determined by their positive
image ◆([n]) \ [n], so there are 2n such injections. Moreover, for i = 1, . . . , n 1, wi > wi+1 if and only if
ui > ui+1 , so |Des+
B (◆ w)| = |Des(w)|.
1
It is also also possible to define Inv(w) as the set { (i, j) | 1 i < j n, wi > wj }. We stick in this paper to the one given
here.
3 Path representation of signed permutations, simply barred permutations
We present here our combinatorial tools to deal with signed permutations, the path representation and the simply
barred permutations.
Definition 3.1. The path representation of u 2 Bn is a triple (⇡ u , ux , uy ) where ⇡ u is a discrete path, drawn on a
grid [n]0 ⇥ [n]0 and joining the point (0, n) to the point (n, 0), ux : [n] ! [n], and uy : [n] ! [ n]. The triple
(⇡ u , ux , uy ) is constructed from u according to the following algorithm: (i) u is written in full notation as a word and
scanned from left to right: each positive letter yields an East step (a length 1 step along the x-axis towards the right),
and each negative letter yields a South step (a length 1 step along the y-axis towards the bottom) ; (ii) the labelling
x : [n] ! [n] is obtained by projecting each positive letter on the x-axis, (iii) the labelling y : [n] ! [ n] is
u u
obtained by projecting each negative letter on the y-axis.
Example 3.2. Consider the signed permutation u := 2316475, in window notation, that is, 57461322316475, in full
notation. Applying the algorithm above, we draw the path ⇡ u and the labellings ux , uy as follows:
5
6
1
3
2
4
7
7 4 2 3 1 6 5
Therefore, ⇡ u is the dashed blue path, x is the permutation 7423165, and
u
y is 7 4 2 3 1 6 5.
u
⌃
It is easily seen that, for an arbitrary u 2 Bn , (⇡ u , u
x, y ) has the following properties:
u
(i) ⇡ u is symmetric along the diagonal,
(ii) ux 2 Sn and, moreover, it is the subword of u of positive letters,
(iii) for each i 2 [n], y (i) = x (i) and, moreover, y is the mirror of the subword of u of negative letters.
u
In particular, we see that the data (⇡ u , ux , uy ) is redundant, since we could give away uy which is completely deter-
mined from ux .
Proposition 3.3. The mapping u 7! (⇡ u , ux ) is a bijection from the set of signed permutations Bn to the set of pairs
(⇡, w), where w 2 Sn and ⇡ is a discrete path from (0, n) to (n, 0) with East and South steps which, moroever, is
symmetric along the diagonal.
We leave the reader convince himself of the above statement. Let us argue that the path representation of a signed
permutation is, possibly, the more interesting combinatorial representation available to represent signed permutations.
For example, the type B inversions of u can be identified with the type A inversions of ux and the unordered pairs or
singletons {wi , wj } with 1 i j n such that the square (i, j) lies below ⇡ u (we index squares from left to right
and from bottom to top). Indeed, (i, j) lies below ⇡ u if and only if (j, i) does, by symmetry of ⇡ u .
With respect to Example 3.2, the set of type B inversions of 2316475 is the disjoint union of the set of type A inversions
of 7423165 and the set
{ ( 7, 7), ( 4, 7),( 2, 7), ( 3, 7), ( 1, 7), ( 6, 7), ( 4, 4), ( 2, 4), ( 3, 4), ( 1, 4), ( 4, 6), ( 2, 2) }
corresponding to the set of unordered pairs
{ {7, 7}, {7, 4},{7, 2}, {7, 3}, {7, 1}, {7, 6}, {4, 4}, {4, 2}, {4, 3}, {4, 1}, {4, 6}, {2, 2} } .
Let us argue for this formally.
Proposition 3.4. Let u 2 Bn . For each i, j with 1 |i| j n, (i, j) 2 InvB (u) if and only if either 1 i < j n
and (i, j) 2 Inv( ux ) or i < 0 and (( ux ) 1 (i), ( ux ) 1 (j)) appears below ⇡ u .
Proof. Let in the following w = ux . If i > 0, then the state-
ment that (i, j) 2 InvB (u) if and only if (i, j) 2 Inv(w) fol-
lows since w is the subword of u (written in full notation) of
positive integers. On the other hand, if i < 0, then recall that
( i, j) 2 InvB (u) if and only if ( i, j) 2 Inv(u) if and only if
( j, i) 2 Inv(u), where, in the expression Inv(u), u is consid-
ered as a permutation of the linear order [±n]. Moreover, since
the ⇡xu is symmetric along the diagonal, observe that (i, j) is y •
below the ⇡xu if and only (j, i) is below the ⇡xu . Therefore, it
will be enough to observe that for y < 0 and x > 0, (x, y) is
below ⇡xu if and only if x appears before y in u, as suggested
in the picture on the right.
x
We introduce next a second representation of signed permutations.
Definition 3.5. A simply barred permutation of [n] is a pair (w, B) where w 2 Sn and B ✓ { 1, . . . , n }. We let SBPn
be the set of simply barred permutations of [n].
We think of B as a set of positions of w, the barred positions. We have added the adjective “simply” to “barred
permutation” since we do not require that B is a superset of Des(w), as for example in [10].
Example 3.6. Consider (w, B) with w = 7423165 and B = { 2, 4, 6 }. We represent (w, B) as a permutation divided
into blocks by the bars, placing a vertical bar after ui for each i 2 B, e.g. 74|23|16|5. Notice that we allow a bar to
appear in the last position, for example 34|1|265|7| stands for the simply barred permutation (3412657, { 2, 3, 6, 7 }).
Thus, a bar appears in the last position if and only if the last block is empty. ⌃
We describe next a bijection—that we call —from the set SBPn to Bn . Let us notice that, in order to establish
equipotence of these two sets, other bijections are available and more straightforward.
Definition 3.7. For (w, B) 2 SBPn , we define the signed permutation (w, B) 2 Bn according to the following
algorithm: (i) draw the grid [n]0 ⇥ [n]0 ; (ii) since B ✓ [n], B ⇥ B defines a subgrid of [n]0 ⇥ [n]0 , construct the
upper anti-diagonal ⇡ of this subgrid; (iii) (w, B) is the signed permutation u whose path representation (⇡ u , ux , uy )
equals (⇡, w, w).
Example 3.8. The required construction can be understood as raising the bars and transforming them into a grid. For
example, for the simply barred permutation 74|2|316|5 (that is (w, B) with w = 7423165 and B = { 2, 3, 6 }) the
construction is as follows:
5
6
1
3
2
4
7
7 4 2 3 1 6 5
The dashed path is the anti-diagonal of the subgrid. The resulting signed permutation (w, B) is 2316475 as from
Example 3.2. ⌃
Notice that the inverse image of has a possibly easier description, as it can be constructed according to the following
algorithm: for u 2 Bn (i) construct the path representation (⇡ u , ux , uy ) of u, (ii) insert a bar in w at each vertical step
of ⇡ u (and remove consecutive bars), (iii) remove a bar at position 0 if it exists. Said otherwise, (w, B) = 1
(u) is
obtained from u by transforming each negative letter into a bar, by removing consecutive bars, and then by removing
a bar at position 0 if needed.
In the following chapter we shall deal mostly with simply barred permutations. Even if we understand simply barred
permutations just as shorthands for path representations of even signed permutations, some remarks are due:
Lemma 3.9. If u = (w, B), then there is a bijection between the set B of bars and the set of xy-turns of ⇡ u .
4 Descents from simply barred permutations
We start investigating how the type B descent set can be recovered from a simply barred permutation.
Proposition 4.1. For a simply barred permutation (w, B), we have
⇠ ⇡
|B|
desB ( (w, B)) = |Des(w) \ B| + . (7)
2
Proof. Write u = (w, B) in window notation and divide it in maximal blocks of consecutive letters having the same
sign. If the first block has negative sign, add a zero positive block which is empty. Each change of sign + among
consecutive blocks yields a descent. These changes of sign bijectively correspond to xy-turns of ⇡ u that lie on or
below the diagonal. By Lemma 3.9, each bar determinesl an mxy-turn and, by symmetry of ⇡ u along the diagonal, the
number of xy-turns that are on or below the diagonal is |B| 2 . Therefore this quantity counts the number of descents
determined by a change of sign.
The other descents of (w, B) are either of the form wi wi+1 with wi > wi+1 and wi , wi+1 belonging to the same
positive block, or of the form wi+1 wi with wi > wi+1 and wi , wi+1 belonging to the same negative block. These
descents are in bijection with the descent positions of w that do not belong to the set B.
The following lemma might be immediately proved by considering that 0 2 DesB (u) if and only if, in the path
representation of (w, B), the first step of ⇡ u is along the y-axis. In this case (and only in this case), ⇡ u makes an
xy-turn on the diagonal. This happens exactly when ⇡ u has an odd number of xy-turns.
Lemma 4.2. We have 0 2 DesB ( (w, B)) if and only if |B| is odd.
For each k 2 { 0, 1,l. . . ,mn }, in the following we let SBPn,k be the set simply barred permutations (w, B) 2 SBPn such
|B|
that |D(w) \ B| + 2 = k.
Corollary 4.3. The set SBPn,k is in bijection with the set of signed permutations of n with k descents.
Definition 4.4. A loosely barred permutation of [n] is a pair (w, B) where w is a permutation of [n] and B ✓
{ 0, . . . , n } is a set of positions (the bars). We let LBPn be the set of loosely barred permutations of [n].
Loosely barred permutations are being introduced only as a tool to index simply barred permutations independently
of the even/odd cardinalities of their set of bars. Namely, for a loosely barred permutation (w, B), let us define its
simplification &(w, B) by
&(w, B) := (w, B \ { 0 }) .
Then &(w, B) is a simply barred permutation whose set of bars has even (resp., odd) cardinality if either 0 2 B and
|B| is odd (resp., even), or 0 62 B and
l |B| is even
m (resp., odd). For a loosely barred permutations (w, B), we shall
|B\{ 0 }|
often need to evaluate the expression 2 . We record this value once for all in the lemma below.
Lemma 4.5. For a loosely barred permutation (w, B) we have
8
> |B| if |B| is even,
⇠ ⇡ >> 2 ,
<
|B \ { 0 }| |B| 1
= , if |B| is odd and 0 2 B , (8)
2 > 2
>
>
: |B|+1 , if |B| is odd and 0 62 B .
2
Next, we define an involution—that we name ✓—from the set of loosely barred permutations to itself. For a loosely
barred permutation (w, B), ✓(w, B) is defined by:
✓(w, B) := (w, Des(w) B) , (9)
where stands for symmetric difference. Let us insist that this involution is defined for all loosely barred permuta-
tions, not just for the simply barred permutations.2
Lemma 4.6. If (u, C) = ✓(w, B), then
|D(w)| + |B| = 2|D(u) \ C| + |C| . (10)
Proof. Recall that C = D(w) B and so D(u) \ C = D(w) \ B. Equation (10) follows since |D(w)| + |B| =
|D(w) B| + 2|D(w) \ B|.
More formally, we define a variant ⇥n of the correspondences ✓ defined in (9) as follows:
⇥n (w, B) := &(✓(w, B)) = (w, Des(w) B \ { 0 }) .
Notice that, this time, ⇥n : LBPn ! SBPn .
Definition 4.7. For each n 0 and k 2 [2n]0 , we let LBPn,k be the set of loosely barred permutations (w, B) such
that |Des(w)| + |B| = k.
Proposition 4.8. For each n 0 and k 2 [n]0 , the restriction of ⇥n to LBPn,2k yields a bijection ⇥n,k from LBPn,2k
to SBPn,k .
Proof. Let (w, B) 2 LBPn,2k , so |Des(w)| + |B| = 2k. Let also (u, C) = ✓(w, B), so ⇥n (w, B) = (w, C \ { 0 }).
Then, by (10),
2k = 2|D(u) \ C| + |C|
and so |C| is even. Therefore
⇠ ⇡ ⇠ ⇡
|C \ { 0 }| |C \ { 0 }| |C|
|D(w) \ (C \ { 0 })| + = |D(u) \ C| + = |D(u) \ C| + = k,
2 2 2
where in the last step we have used equation (8).
The transformation ⇥n,k is injective. If ⇥n (w, B) = ⇥n (w0 , B 0 ), then w = w0 and Des(w) = Des(w0 ). Moreover,
from Des(w) B \ { 0 } = Des(w) B 0 \ { 0 } we deduce B \ { 0 } = B 0 \ { 0 }. If moreover (w, B), (w0 , B 0 ) 2
LBPn,2k , then |B| = 2k |Des(w)| = |B 0 | and B \ { 0 } = B 0 \ { 0 } imply that 0 2 Des(w) B if and only if
0 2 Des(w) B 0 . It follows that B = B 0 .
l m
In order to show that the transformation ⇥n,k is surjective, let us fix (u, C) 2 SBPn,k , so |Des(u) \ C| + |C|
2 = k.
If |C| is even, then (w, B) := ✓(u, C) is such that ⇥n (w, B) = ✓(w, B) = (u, C) and, using equations (8) and (10),
(w, B) 2 LBPn,2k :
⇠ ⇡
|C|
|Des(w)| + |B| = 2|Des(u) \ C| + |C| = 2( |Des(u) \ C| + ) = 2k.
2
If |C| is odd, then (w, B) := ✓(u, C [ { 0 }) is such that ⇥(w, B) = (u, C) and (w, B) 2 LBPn,2k :
|C| + 1
|Des(w)| + |B| = 2|Des(u) \ (C [ { 0 })| + |C [ { 0 }| = 2|Des(u) \ C| + 2
⇠ ⇡ 2
|C|
= 2( |Des(u) \ C| + ) = 2k .
2
Definition 4.9. For each k 2 [n 1]0 , we let SBPkn be the set of simply barred permutations (w, B) 2 SBPn such that
|Des+
B ( (w, B))| = k.
Notice that 8
<0 62 DesB ( (w, B)) and desB ( (w, B)) = k, or
|Des+
B ( (w, B))| = k iff
:0 2 Des ( (w, B)) and des ( (w, B)) = k + 1 .
B B
Using Lemma 4.2 and equation (7), for (w, B) 2 SBPn we have
8 l m
> |B|
<|B| is even and |D(w) \ B| + 2 = k, or
k
(w, B) 2 SBPn iff l m
>
:|B| is odd and |D(w) \ B| + |B| = k + 1 .
2
2
At the moment of writing we cannot pinpoint any other usage of this involution apart, of course, from yielding our bijections
and counting results.
Proposition 4.10. For each k 2 [n 1]0 , the restriction of ⇥n to LBPn,2k+1 yields a bijection ⇥kn from LBPn,2k+1 to
SBPkn .
Proof. Let (w, B) 2 LBPn,2k+1 and (u, C) = ✓(w, B), so ⇥n (w, B) = (w, C \ { 0 }). Thus |Des(w)| + |B| = 2k + 1
and, by (10),
2k = 2|D(u) \ C| + |C| 1 ,
so in particular |C| is odd. Using equation (8), we obtain
8
⇠ ⇡ <|D(u) \ C| + |C| 1 = k , 0 2 C,
|C \ { 0 }| 2
|D(u) \ C|+ =
2 :|D(u) \ C| + |C|+1 = k + 1 , 0 62 C .
2
Considering that |C| is odd, we have
⇠ ⇡ ⇢
|C \ { 0 }| k, |C \ { 0 }| is even,
|D(u) \ (C \ { 0 })| + =
2 k + 1, |C \ { 0 }| is odd,
that is, (u, C \ { 0 }) = ⇥n (w, B) 2 SBPkn .
The transformation ⇥kn is injective, the reason being similar to the one for ⇥n,k . If ⇥n (w, B) = ⇥n (w0 , B 0 ) then
w = w0 and Des(w) = Des(w0 ). Moreover, from Des(w) B \ { 0 } = Des(w) B 0 \ { 0 } we deduce B \ { 0 } =
B 0 \{ 0 }. Considering now that |B| = 2k +1 |Des(w)| = |B 0 | and B \{ 0 } = B 0 \{ 0 }, we derive 0 2 Des(w) B
if and only if 0 2 Des(w) B 0 , whence B = B 0 .
In order to show
l that
m the transformation ⇥n is surjective, let
k
l usmfix (u, C) 2 SBPn , so either (i) |C| is even and
k
|C| |C|
|D(u) \ C| + 2 = k or (ii) |C| is odd and |D(u) \ C| + 2 = k + 1.
Let us suppose (i). Then (w, B) := ✓(u, C [ { 0 }) is such that ⇥n (w, B) = (u, C) and, using equations (8) and (10),
(w, B) 2 LBPn,2k+1 :
|C| + 1
|Des(w)| + |B| = 2|Des(u) \ C| + |C [ { 0 }| = 2|Des(u) \ C| + 2
⇠ ⇡ 2
|C| 1
= 2( |Des(u) \ C| + + ) = 2k + 1.
2 2
Let us suppose (ii). Then (w, B) := ✓(u, C) is such that ⇥n (w, B) = ✓(w, B) = (u, C) and, using equations (8) and
(10), (w, B) 2 LBPn,2k+1 :
|C|
|Des(w)| + |B| = 2|Des(u) \ C| + |C| = 2|Des(u) \ C| + 2
⇠ ⇡ 2
|C| 1
= 2( |Des(u) \ C| + ) = 2(k + 1) 1 = 2k + 1.
2 2
To end this section, we collect the consequences of the bijections established so far.
Theorem 4.11. The following relations hold:
⌧ X2k ⌧ ✓ ◆
Bn n n+1
= , (3)
k i 2k i
i=0
⌧ X ⌧n ✓ n + 1 ◆
2k+1
n
2n = . (4)
k i 2k + 1 i
i=0
Proof. We have seen that signed permutations u 2 Bn such that desB (u) = k are in bijection (via the mapping of
Definition 3.7) with simply barred permutations in SBPn,k . Next, this set is in bijection (see Proposition (4.8)) with the
set LBPn,2k of loosely barred permutations (w, B) 2 LBPn such that des(w) + |B| = 2k. The cardinality of LBPn,2k
is the right-hand side of equality (3).
The left-hand side of equality (4) is the cardinality of the set of signed permutations u such that |Des+
B (u)| = k, see
Lemma 2.1. This set is in bijection with the set SBPkn (via defined in 3.7 and by the definition of SBPkn ) which, in
turn, is in bijection (see Proposition (4.10)) with the set LBPn,2k+1 of loosely barred permutations (w, B) 2 LBPn
such that des(w) + |B| = 2k + 1. The cardinality of this set is the right-hand side of equality (4).
Theorem 4.12. The following relation holds:
Bn (t2 ) = (1 + t)n+1 Sn (t) 2n tSn (t2 ) . (11)
D E
Bn
Proof. By (3), k , which is the coefficient of t2k in the polynomial Bn (t2 ), is also the coefficient of t2k in (1 +
D E
t)n+1 Sn (t). By (4), 2n nk is the coefficient of t2k+1 in the polynomials 2n tSn (t2 ) and (1 + t)n+1 Sn (t). Therefore
Bn (t2 ) + 2n tSn (t2 ) = (1 + t)n+1 Sn (t) , (5)
whence equation (11).
5 Stembridge’s identity for Eulerian numbers in type D
Let us recall that a signed permutation u 2 Bn is even signed if the number of negative letters in its window notation
is even. The even signed permutations of Bn form a subgroup Dn of Bn and in fact the groups Dn are the standard
models for abstract Coxeter groups of type D.
Definitions analogous to those given in Section 2 for the types A and B can be given for type D. Namely, for u 2 Dn ,
we set
DesD (u) := { i 2 { 0, 1, . . . , n 1 } | ui > ui+1 } , (12)
where we have set u0 = u2 ,
⌧ n ⌧
X
Dn Dn k
desD (u) := |DesD (u)| , := |{ u 2 Dn | desD (u) = k }| , Dn (t) := t .
k k
k=0
The formula in (12) is the standard one, see e.g. [4, §8.2] or [1]. The reader will have no difficulties verifying that, up
to renaming 0 by 1, the type D descent set of u can also be defined using the following, see [14, §13]:
DesD (u) := { i 2 { 1, 1, . . . , n 1 } | ui > u|i|+1 } . (13)
It is convenient to consider a more flexible representation of elements of Dn . If u 2 Bn , then its mate is the signed
permutation u 2 Bn that differs from u only for the sign of the first letter. Notice that u = u. We define a forked
signed permutation (see [14, §13]) as an unordered pair of the form {u, u} for some u 2 Bn . Clearly, just one of the
mates is even signed and therefore forked signed permutations are combinatorial models of Dn .
The path representation of a forked signed permutation is insensitive of how the diagonal is crossed, either from the
West, or from the North. The following are possible ways to draw a forked signed permutation on a grid:
5 5
4 4
3 3
2 2
1 1
1 2 3 4 5 1 2 3 4 5
Even if the formulas in (12) and (13) have been defined for even signed permutations, they still can be computed for
all signed permutations. The formula in (13) is not invariant under taking mates, however the following lemma shows
that this formula suffices
D E to compute the number of type D descents of a forked signed permutation and therefore the
Eulerian numbers Dkn .
Lemma 5.1. For each u 2 Bn , 1 2 DesD (u) if and only if 1 2 DesD (u). Therefore desD (u) = desD (u).
Proof. Suppose 1 2 DesD (u), that is u1 > u2 . Then u 1 = ( u1 ) = u1 > u2 , and so 1 2 DesD (u). The
opposite implication is proved similarly.
For the last statement, observe that DesD (u) = u [ { i 2 { 2, . . . , n 1 } | ui > ui+1 } with u := { i 2 { 1, 1} |
ui > u|i|+1 } and, by what we have just remarked, we have | u | = | u |. It follows that |DesD (u)| = |DesD (u)|.
Our next aim is to derive Stembridge’s identity
Dn (t) = Bn (t) n2n 1 tSn 1 (t) , (14)
see [22, Lemma 9.1], which, in term of the coefficients of these polynomials, amounts to
⌧ ⌧ ⌧
Dn Bn n 1 n 1
= n2 . (15)
k k k 1
Definition 5.2. A signed permutation u is smooth if u1 , u2 have equal sign and, otherwise, it is non-smooth.
The reason for naming a signed permutation smooth arises again from the path representation of a signed permutation:
the smooth signed permutation is, between the two mates, the one that minimizes the turns nearby the diagonal, as
suggested below with two pairs of mates as examples:
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
Lemma 5.3. If u 2 Bn is smooth, then 1 2 DesD (u) if and only if 0 2 DesB (u) and therefore desD (u) = desB (u).
Proof. Suppose 0 2 DesB (u), so u1 < 0 and u2 < 0 as well, since u is smooth. Then u 1 = u1 > 0 > u2 , so
1 2 DesD (u). Conversely, suppose 1 2 DesD (u), that is, u 1 > u2 . If u1 > 0, then 0 > u1 = u 1 > u2 , so
u1 , u2 have different sign, a contradiction. Therefore u1 < 0 and 0 2 DesB (u).
Next, we consider the correspondence—let us call it —sending a non-smooth signed permutation u 2 Bn to the pair
(|u1 |, u0 ), where u0 is obtained from u2 . . . un by normalising this sequence, so that it takes absolute values in the set
[n 1]. For example (6123475) = (6, 123465) and (2316475) = (2, 215364), as suggested below:
6123475 (6, 123475) (6, 123465) , 2316475 (2, 316475) (2, 215364) .
The process of normalizing the sequence u2 . . . un can be understood as applying to each letter of this sequence the
unique order preserving bijection Nn,x : [±n] \ { x, x } ! [± n 1] where, in general, x 2 [n] and, in this case,
x = |u1 |.
Lemma 5.4. Let n 2. For each pair (x, v) with x 2 [n] and v 2 Bn 1 , there exists a unique non-smooth u 2 Bn
such that (u) = (x, v).
Proof. We construct u firstly by renaming v to v 0 so that none of x, x appears in v 0 (that is, we apply to each letter of
v the inverse of Nn,x ) and then by adding in front of v 0 either x or x, according to the sign of the first letter of v 0 .
Lemma 5.5. The correspondence restricts to a bijection from the set of non-smooth signed permutations u 2 Bn
such that desB (u) = k to the set of pairs (x, v) where x 2 [n] and v 2 Bn 1 is such that |Des+
B (v)| = k 1.
Proof. We have already argued that is a bijection from the set of non-smooth signed permutations u of [n] to the
set of pairs (x, v) with x 2 [n] and v 2 Bn 1 . Therefore, we are left to argue that, for non-smooth u and v, if
desB (u) = k, then |Des+ B (v)| = k 1. Since u1 , u2 have different sign, then |DesB (u) \ { 0, 1 }| = 1. Clearly, if
(u) = (x, v), then Des+B (v) = { i 1 | i 2 DesB (u) \ { 2, . . . , n 1 } }, from which the statement of the lemma
follows.
Theorem 5.6. The following relations hold:
⌧ ⌧ ⌧
Bn Dn n 1
= + n2n 1 , Bn (t) = Dn (t) + n2n 1 tSn 1 (t) .
k k k 1
Proof. Every signed permutation is either smooth or non-smooth. By Lemma 5.3, the smooth signed permutations
with k type B descents are in bijection with the even signed permutations with k type D descents. By Lemma 5.5, the
non-smooth signed permutations u 2 Bn with k type B descents are in bijectionD with Ethe pairs (x, v) 2 [n] ⇥ Bn 1
n 1
such |Des+
B (v)| = k 1. Using Lemma 2.1, the number of these pairs is n2n 1 k 1 .
Example 5.7. We end this section exemplifying the use of formulas (3) and (15) by which computation of the Eulerian
numbers in type B and D is reduced to computing Eulerian numbers in type A. Let us mention that our interest in
Eulerian numbers originates from our lattice theoretic work on the lattice variety of Permutohedra [19] and its possible
extensions to generalized forms of Permutohedra [15, 18, 17]. Among these generalizations, we count lattices of finite
Coxeter groups in the types B and D [3]. While it is known that the lattices Bn span the same lattice variety of the
permutohedra, see [6, Exercice 1.23], characterising the lattice variety spanned by the lattices Dn is an open problem.
A first step towards solving this kind of problem is to characterize (and count) the join-irreducible elements of a class
of lattices. In our case, this amounts to Dcharacterizing
E D Ethe elements u in Bn (resp., in Dn ) such that desB (u) = 1 (resp.,
such that desD (u) = 1). The numbers 1 and D1n are known to be equal to 3n n 1 and 3n n 1 n2n 1
Bn
respectively, see [14, Propositions 13.3 and 13.4]. Let us see how to derive these identities using the formulas (3) and
(15). To this end, we also need the alternating sum formula for Eulerian numbers, see e.g. [14, page 12]:
⌧ Xk ✓ ◆
n n+1
= ( 1)j (k + 1 j)n . (16)
k j
j=0
For type B, we have
⌧ ⌧ ✓ ◆ ⌧ ✓ ◆ ⌧ ✓ ◆
Bn n+1
n n n+1 n n+1
= + +
1 0 2 1 1 2 0
✓ ◆ ⌧
n+1 n
= + (2n n 1)(n + 1) +
2 2
✓ ◆ ✓ ◆
n+1 n n n n+1
= + (2 n 1)(n + 1) + 3 2 (n + 1) + , by (16)
2 2
✓ ◆
n+1
= 3n (n + 1)2 + 2 = 3n (n + 1)(n + 1 n) = 3n n 1.
2
The computation in type D is then immediate from Stembridge’s identity (15):
⌧ ⌧ ⌧
Dn Bn n 1
= n2n 1 = 3n n 1 n2n 1 . ⌃
1 1 0
6 Threshold graphs and their degree orderings
Besides presenting the bijective proofs, a goal of this paper is to exemplify the potential of the path representation of
signed permutations. The attentive reader might object then that the path representation is not being used in Section 5.
Indeed, after discovering this proof via this representation of signed permutations, we realized that the presentation
of the proof could be simplified by avoiding mention of the path representation. It might be asked then whether the
path representation yields something more, in particular with respect to the lattices of the Coxeter groups Dn . We
answer. The type D set of inversions of an even signed permutation (or of a forked signed permutation) can be defined
as follows:
InvD (u) := InvB (u) \ { ( i, i) | i 2 [n] } ,
which, graphically, amounts to ignoring boxes on the diagonal:
2 ⇥
5 ⇥
1 ⇥
4 ⇥
3 ⇥
3 4 1 5 2
As mentioned in Proposition 3.4, we can identify the set of inversions of a signed permutation u with the disjoint union
of Inv( ux ) and a set of unordered pairs. For even signed permutations, this identification yields
InvD (u) = Inv( ux ) [ E u with E u := { {i, j} | i, j 2 [n], i 6= j, (( ux ) 1 (i), ( ux ) 1 (j)) lies below ⇡ u } .
Figure 1: The (unlabelled) graphs K2,2 , P3 , and C4
Thus, we may consider ([n], E u ) as a simple graph on the set of vertices [n]. Let us recall the following standard
definitions that apply to an arbitrary simple graph (V, E) and to a vertex v 2 V :
NE (v) := { u 2 V | {v, u} 2 E } , degE (v) := |NE (v)| , NE [v] := N (v) [ { v } .
A linear ordering v1 , . . . , vn of V is a degree ordering of (V, E) if degE (v1 ) degE (v2 ) . . . degE (vn ). The
vicinal preorder of a graph (V, E), noted C E , is defined by saying that v C E u iff NE (v) ✓ NE [u]. That the vicinal
preorder is indeed a preorder is well known, see e.g. [12]. Next, we take Theorem 1 in [7] as the definition of the
class of threshold graphs and consider, among the possible characterisations of this class, the one that uses the vicinal
preorder.
Definition 6.1. A graph (V, E) is threshold if it does not contain an induced subgraph isomorphic to one among K2,2 ,
P3 and C4 (these graphs are illustrated in Figure 1).
Proposition 6.2 (see e.g. [12, Theorem 1.2.4]). A graph (V, E) is threshold if and only if the vicinal preorder is total.
With these tools available, let us observe the following:
Theorem 6.3. The mapping sending u to ( ux , E u ) is a bijection from the set Dn to the set of pairs (w, E) such that
([n], E) is a threshold graph and w 2 Sn is a degree ordering on this graph.
Proof. We start arguing that, for u 2 Dn , ([n], E u ) is a threshold graph and that ux is a degree ordering on this graph.
Notice that E u = E u , so we can suppose that u is the mate such that u1 > 0. Clearly, we can also suppose that ux
is the identity permutation. Under these hypothesis, the paths ⇡ u that are symmetric along the diagonal bijectively
correspond to fixed-point free self-adjoint Galois connections, see e.g. [16] for the general correspondence between
paths and sup-preserving functions. For a fixed-point free self-adjoint Galois connection we mean an antitone map
f : [n]0 ! [n]0 such that, for each x, y 2 [n]0 , x f (y) iff y f (x) and x 6= f (x). Moreover, under these
hypothesis, we have that {x, z} 2 E u if and only if z 6= x and z f (x), where f bijectively corresponds to ⇡ u .
Then, if y < x and z 2 NE u (x), then z f (x) f (y) and so either z = y or z 2 NE u (y). We have argued that
x < y implies that NE u (y) ✓ NE u [x] which, in particular, implies that the identity permutation is a degree ordering
on E u and that the vicinal preorder is total, so ([n], E u ) is a threshold graph.
The mapping sending u to ( ux , E u ) is clearly injective, so we are left to argue that every pair (w, E), with ([n], E) a
threshold graph and w 2 Sn a degree ordering on it, arises in this way. Again, we can assume that w is the identity
permutation, so we need to find a fixed-point free self-adjoint Galois connection f : [n]0 ! [n]0 such that, for
x, z 2 [n], {x, z} 2 E if and only if x 6= z and z f (x).
Observe that if degE (y) degE (x), then necessarily we have NE (y) ✓ NE [x], otherwise NE (x) ✓ NE [y] and we
get a contradiction. Thus, if x < y, then NE (y) ✓ NE [x], since the identity permutation is a degree ordering. Define
then f (x) = max NE (x), with the conventions that max ; = 0 and NE (0) = [n]0 . For x, z 2 [n], if {x, z} 2 E, then
z 2 NE (x) and then z f (x). Conversely, if z f (x), then x 2 NE (f (x)) ✓ NE [z], so if x 6= z, then x 2 NE (z)
and {x, z} 2 E. Finally f is a fixed-point free self-adjoint Galois connection: it is fixed-point free since x 62 NE (x),
and it is easily seen that y f (x) if and only if x f (y), for each x, y 2 [n]0 , property that also implies that f is
antitone.
Let us remark that Theorem 6.3 also yields a natural representation of the weak ordering on Dn as follows: under the
bijection, (w1 , E1 ) (w2 , E2 ) holds if and only if w1 w2 in the weak ordering of Sn and, moreover, E1 ✓ E2 .
This poset (actually a lattice, since it is isomorphic to Dn ) is built out from threshold graphs but is only loosely related
to the lattice of threshold graphs of [13] where unlabeled (that is, up to isomorphism) threshold graphs are considered.
That threshold graphs are related to the families B and D in the theory of Coxeter groups has already been observed, see
e.g. [8], [20, Exercise 5.25], and [21, Exercise 3.115]. As part of possible future research, it is tempting to investigate
further the bijection presented in Theorem 6.3 (which can be further adapted to fit the type B) and try to understand if
it plays any important role with respect to the problem, partly solved in [8], of characterizing free sub-arrangements
of the Coxeter arrangements Bn .
References
[1] E. Bagno, R. Biagioli, and D. Garber. Stirling and eulerian numbers of types B and D. In L. Ferrari and M. Vam-
vakari, editors, Proceedings of the 11th International Conference on Random and Exhaustive Generation of
Combinatorial Structures, GASCom 2018, Athens, Greece, June 18-20, 2018, volume 2113 of CEUR Workshop
Proceedings, pages 53–59. CEUR-WS.org, 2018.
[2] E. Barnard. The canonical join complex. Preprint, retrievable from https://arxiv.org/abs/1610.05137,
2016.
[3] A. Björner. Orderings of Coxeter groups. In Combinatorics and Algebra (Boulder, Colo., 1983), volume 34 of
Contemp. Math., pages 175–195. Amer. Math. Soc., Providence, RI, 1984.
[4] A. Björner and F. Brenti. Combinatorics of Coxeter groups, volume 231 of Graduate Texts in Mathematics.
Springer, New York, 2005.
[5] M. Bóna. Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). CRC Press,
Boca Raton, FL, second edition, 2012. With a foreword by Richard Stanley.
[6] N. Caspard, L. Santocanale, and F. Wehrung. Permutohedra and associahedra. In Lattice theory: special topics
and applications. Vol. 2, pages 215–286. Birkhäuser/Springer, Cham, 2016.
[7] V. Chvátal and P. L. Hammer. Aggregation of inequalities in integer programming. In Studies in integer pro-
gramming (Proc. Workshop, Bonn, 1975), pages 145–162. Ann. of Discrete Math., Vol. 1, 1977.
[8] P. H. Edelman and V. Reiner. Free hyperplane arrangements between An 1 and Bn . Math. Z., 215(3):347–365,
1994.
[9] R. Freese, J. Ježek, and J. Nation. Free Lattices, volume 42 of Mathematical Surveys and Monographs. American
Mathematical Society, Providence, RI, 1995.
[10] I. Gessel and R. P. Stanley. Stirling polynomials. J. Combinatorial Theory Ser. A, 24(1):24–33, 1978.
[11] G. Guilbaud and P. Rosenstiehl. Analyse algébrique d’un scrutin. Math. Sci. Hum., 4:9–33, 1963.
[12] N. V. R. Mahadev and U. N. Peled. Threshold graphs and related topics, volume 56 of Annals of Discrete
Mathematics. North-Holland Publishing Co., Amsterdam, 1995.
[13] R. Merris and T. Roby. The lattice of threshold graphs. JIPAM. J. Inequal. Pure Appl. Math., 6(1):Article 2, 21,
2005.
[14] T. K. Petersen. Eulerian numbers. Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts:
Basel Textbooks]. Birkhäuser/Springer, New York, 2015. With a foreword by Richard Stanley.
[15] M. Pouzet, K. Reuter, I. Rival, and N. Zaguia. A generalized permutahedron. Algebra Universalis, 34(4):496–
509, 1995.
[16] L. Santocanale. On discrete idempotent paths. In R. Mercaş and D. Reidenbach, editors, WORDS 2019, volume
11682 of Lecture Notes in Comput. Sci., pages 312–325. Springer, Cham, 2019.
[17] L. Santocanale and M. J. Gouveia. The continuous weak order. Journal of Pure and Applied Algebra, 2020. In
press.
[18] L. Santocanale and F. Wehrung. Generalizations of the permutohedron. In Lattice Theory: Special Topics and
Applications. Vol. 2, pages 287–397. Birkhäuser, 2016.
[19] L. Santocanale and F. Wehrung. The equational theory of the weak Bruhat order on finite symmetric groups.
Journal of the European Mathematical Society, 20(8):1959–2003, 2018.
[20] R. P. Stanley. An introduction to hyperplane arrangements. In Geometric combinatorics, volume 13 of IAS/Park
City Math. Ser., pages 389–496. Amer. Math. Soc., Providence, RI, 2007.
[21] R. P. Stanley. Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics.
Cambridge University Press, Cambridge, second edition, 2012.
[22] J. R. Stembridge. Some permutation representations of Weyl groups associated with the cohomology of toric
varieties. Adv. Math., 106(2):244–301, 1994.