=Paper=
{{Paper
|id=Vol-2113/paper4
|storemode=property
|title=Stirling and Eulerian numbers of types B and D
|pdfUrl=https://ceur-ws.org/Vol-2113/paper4.pdf
|volume=Vol-2113
|authors=Eli Bagno,Riccardo Biagioli,David Garber
|dblpUrl=https://dblp.org/rec/conf/gascom/BagnoBG18
}}
==Stirling and Eulerian numbers of types B and D==
https://ceur-ws.org/Vol-2113/paper4.pdf
Stirling and Eulerian numbers of types B and D
Eli Bagno Riccardo Biagioli
Jerusalem College of Technology Institut Camille Jordan
21 Havaad Haleumi St. Jerusalem, Israel Université Claude Bernard Lyon 1
bagnoe@g.jct.ac.il 69622 Villeurbanne Cedex, France
biagioli@math.univ-lyon1.fr
David Garber
Department of Applied Mathematics
Holon Institute of Technology
52 Golomb St., PO Box 305 58102 Holon, Israel
garber@hit.ac.il
Abstract
In this paper we generalize a well-known identity relating Stirling num-
bers of the second kind and Eulerian numbers to Coxeter groups of
types B and D.
1 Introduction
Stirling numbers of the second kind, denoted by S(n, k), arise in a variety of problems in enumerative combi-
natorics. They first appeared as the coefficients of the expansion of the polynomial xn in terms of the falling
polynomials as presented in the following identity:
n
X
xn = S(n, k) · [x(x − 1) · · · (x − k + 1)],
k=0
see the survey of Boyadzhiev [Boy12]. However, their most common combinatorial interpretation is as counting
the number of partitions of the set [n] := {1, . . . , n} into k blocks (see [Sta12, page 81]). They count also the
number of vertices of rank k of the intersection poset of the Coxeter hyperplane arrangement of type An−1 , graded
by co-dimension. In that context, they are also called Whitney numbers W (n, n − k) (see Zaslavsky [Zas81] and
Suter [Sut00] for more details).
The original definition of the Eulerian numbers was first given by Euler in an analytic context [Eul36, §13].
Later, they began to appear in combinatorial problems, as the Eulerian number A(n, k) counts the number of
permutations in the symmetric group Sn , having k − 1 descents. We recall that a descent of σ ∈ Sn is an element
of
Des(σ) := {i ∈ [n − 1] | σ(i) > σ(i + 1)}, (1)
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org
53
called the descent set of σ. We also denote des(π) := |Des(σ)| the descent number.
Stirling numbers of the second kind and Eulerian numbers are closely related by the following classical identity,
see e.g. [Bon04, Theorem 1.18].
Theorem 1.1. For all positive integers n and r, we have
r
1 X n−k
S(n, r) = A(n, k) .
r! r−k
k=0
The aim of this note is to give two generalizations of this theorem to the Coxeter groups of types B and D.
2 Coxeter groups of types B and D and their Eulerian numbers
Let (W, S) be a Coxeter system. As usual, denote by `(w) the length of w ∈ W , namely the minimum k for
which w = s1 · · · sk with si ∈ S. The right descent set of w ∈ W is defined to be
DR (w) := {s ∈ S | `(ws) < `(w)}.
A combinatorial characterization of DR (w) in type A, is given by Equation (1) above. Now we recall analogous
descriptions in types B and D.
We denote by Bn the group of all bijections β of the set [−n, n] \ {0} onto itself such that
β(−i) = −β(i)
for all i ∈ [−n, n] \ {0}, with composition as the group operation. This group is usually known as the group of
signed permutations on [n], or as the hyperoctahedral group of rank n. If β ∈ Bn then we write β = [β(1), . . . , β(n)]
and we call this the window notation of β. Occasionally, we will use the complete notation of a permutation, e.g.
−5 −4 −3 −2 −1 1 2 3 4 5
π = [3, −2, 1, −4, 5] = .
−5 4 −1 2 −3 3 −2 1 −4 5
As set of generators for Bn we take SB := {sB B B
1 , . . . , sn−1 , s0 } where for i ∈ [n − 1]
sB B
i := [1, . . . , i − 1, i + 1, i, i + 2, . . . , n] and s0 := [−1, 2, . . . , n].
It is well known that (Bn , SB ) is a Coxeter system of type B (see e.g., [BB05, §8.1]). The following characteri-
zations of the right descent set of β ∈ Bn is well known [BB05].
Proposition 2.1. Let β ∈ Bn . Then
DesB (β) = {i ∈ [0, n − 1] | β(i) > β(i + 1)},
where β(0) := 0 (we use the usual order on the integers). In particular, 0 ∈ DesB (β) is a descent if and only if
β(1) < 0. We set desB (β) := |DesB (β)|.
We set:
AB (n, k) := |{β ∈ Bn | desB (β) = k − 1}|,
and we call them the Eulerian numbers of type B.
We denote by Dn the subgroup of Bn consisting of all the signed permutations having an even number of
negative entries in their window notation. It is usually called the even-signed permutation group. As a set of
generators for Dn we take SD := {sD D D
0 , s1 , . . . , sn−1 } where for i ∈ [n − 1]
sD B D
i := si and s0 := [−2, −1, 3, . . . , n].
There is a well-known direct combinatorial way to compute the right descent set of γ ∈ Dn , (see, e.g., [BB05,
§8.2]).
54
Proposition 2.2. Let γ ∈ Dn . Then
DesD (γ) = {i ∈ [0, n − 1] | γ(i) > γ(i + 1)},
where γ(0) := −γ(2). In particular, 0 ∈ DesD (γ) if and only if γ(1) + γ(2) < 0. We set desD (γ) := |DesD (γ)|.
Then we set
AD (n, k) := |{γ ∈ Dn | desD (γ) = k − 1}|,
and we call it the Eulerian number of type D.
For example, if γ = [1, −3, 4, −5, −2, −6], then DesD (γ) = {0, 1, 3, 5}, but DesB (γ) = {1, 3, 5}.
3 Set partitions of types B and D
It is well-known that the number of elements of rank k in the lattice of set partitions of [n], πA (n), is counted
by the Stirling numbers of the second kind S(n, k).
For Coxeter groups of type B, Reiner [Rei97] defined a natural set partition lattice πB (n) which comes from
the interpretation of the lattice πA (n) as the poset of intersection subspaces of subsets of hyperplanes in the root
system of type An−1 : {xi = xj | 1 ≤ i < j ≤ n}, ordered by reverse inclusion.
For example, the partition {{1, 3, 6}, {2, 5, 4}} is interpreted as the subspace
{~x = (x1 , x2 , . . . , x6 ) ∈ R6 | x1 = x3 = x6 , x2 = x5 = x4 },
which can be written as the intersection of the hyperplanes x1 = x3 , x1 = x6 , x2 = x5 and x4 = x5 .
The poset of intersection subspaces of the subspaces of the root system of type B:
{xi = ±xj | 1 ≤ i < j ≤ n} ∪ {xi = 0 | 1 ≤ i ≤ n},
consists of subspaces which look typically like: {x ∈ R8 | x1 = −x3 = −x4 = −x8 , x2 = x5 = 0, x6 = −x7 }, and
which can be represented in a simpler way like this:
{{1, −3, −4, −8}, {−1, 3, 4, 8}, {2, −2, 5, −5}, {6, −7}, {−6, 7}}.
This was Reiner’s motivation for defining the partitions of type B as follows [Rei97]. Set [±n] := {±1, . . . , ±n}.
Definition 3.1. A set partition of type Bn is a partition of the set [±n] into blocks such that the following
conditions are satisfied:
◦ If C appears as a block in the partition, then −C also appears in that partition.
◦ There exists at most one block satisfying −C = C. This block is called the zero-block (if it exists, it is a set
of the form {±i | i ∈ E} for some E ⊆ [n]).
Definition 3.2. A set partition of type Dn is a set partition of type Bn with the additional restriction that the
zero-block, if presents, contains at least two pairs.
For example, the set partition {{1, 2}, {−1, −2}, {±3}} is a set partition of type B3 but not of type D3 , while
{{1}, {−1}, {±2, ±3}} is a set partition of type D3 .
We denote by SB (n, k) (resp. SD (n, k)) the number of set partitions of type Bn (resp. type Dn ) having
exactly k pairs of non-zero blocks. They are called Stirling numbers of type B (resp. D).
We define now the concept of an ordered set partition:
Definition 3.3. A set partition of type Bn (type Dn ) is ordered if the set of blocks is totally ordered and the
following conditions are satisfied:
◦ If the zero-block exists, then it appears as the first block.
◦ For each block C which is not a zero-block, the blocks C and −C occupy adjacent places.
55
4 Main results
The main results of this paper are two generalizations of Theorem 1.1 to Coxeter groups of type B and type D.
Theorem 4.1. For all positive integers n and r, we have
r
1 X n−k
SB (n, r) = A B (n, k) .
2r r! r−k
k=0
Theorem 4.2. For all positive integers n and r, we have
r !
1 n−1
X n−k
SD (n, r) = r n2 (r − 1)!S(n − 1, r − 1) + AD (n, k) ,
2 r! r−k
k=0
where S(n − 1, r − 1) is the usual Stirling number of the second kind.
Now, by inverting these formulas, similarly to [Bon04, Corollary 1.18], we get the following expression of the
Eulerian numbers of type B (resp. type D) in terms of the Stirling numbers of type B (resp. type D).
Corollary 4.1. For all positive integers n and r, we have
k
X n−r
AB (n, k) = (−1)k−r · 2r r! · SB (n, r) .
r=1
k−r
Corollary 4.2. For all positive integers n and r, we have
k
X
k−r r
n−1
n−r
AD (n, k) = (−1) 2 r! · SD (n, r) + n2 (r − 1)!S(n − 1, r − 1) .
r=1
k−r
5 Proof of Theorem 4.1 - Type B
This proof uses arguments similar to Bona’s proof of Theorem 1.17 in [Bon04] for the corresponding identity in
type A. Theorem 4.1 is equivalent to the following equation:
r
r
X n−k
2 r!SB (n, r) = AB (n, k) .
r−k
k=0
r
The number 2 r!SB (n, r) in the left-hand side counts the number of ordered set partitions of type Bn . Let us
show that the right-hand side counts the same objects in a different way.
Given a signed permutation β ∈ Bn with desB (β) = k, written in its window notation, we show how to
construct ordered set partitions of type Bn having r blocks.
Split β into increasing runs by putting a separator right after every descent. If 0 is a descent we add a
separator just before β(1). This splits β into a set of blocks. Here by a block we mean the set of entries between
two consecutive separators, where by convention the last separator is always right after β(n). This set of blocks
becomes an ordered set partitions of type Bn by performing the following two steps:
1. For each obtained block C, locate the block −C right after it.
2. If 0 6∈ DesB (β), define the zero-block to be equal to {±β(1), . . . , ±β(i)}, where i denotes the first descent of
β. It will be located as the first block.
For illustrating the above construction, let β = [3, −2, 1, −4, 5] ∈ B5 . We add the separators after the descents,
obtaining:
β = 3 −2 1 −4 5 .
The associated ordered set partition of type B5 is:
{{±3}, {−2, 1}, {−1, 2}, {−4, 5}, {−5, 4}}.
56
When β is written in complete notation, the definition of the zero-block become more natural, since it appears
as a usual block when the permutation is split by the separators (one after any descent), i.e.
β = −5 4 −1 2 −3 3 −2 1 −4 5 .
Now, we distinguish between two cases:
1. If r = k (where desB (β) = k), the above construction produces an ordered set partition of type Bn with
exactly r pairs of blocks. In fact, if 0 6∈ DesB (β), then the digits in the first increasing run in the window
notation of β, together with all their signed copies, constitute the zero-block, C0 , and the k descents produce
k pairs of blocks {Ci }, {−Ci }, where Ci denotes the increasing run starting after the ith descent.
If 0 ∈ DesB (β), then there is no zero block, so that each increasing run contributes a pair of blocks which
in total form a set partition of type Bn having k + 1 pairs of blocks as described above.
2. If r > k, we add r − k separators in places which are not descents. Note that if 0 6∈ DesB (β) then one might
also add a separator before the first place (which means that the first increasing run will contribute two
regular blocks instead of one zero-block). Now we produce the desired ordered partition in the same way
we did in the preceding case. The number of ordered partitions obtained from β in this way is n−k r−k , and
it is independent whether 0 is a descent of β or not. 2
For example β = [1, 4 | −5, −3, 2] ∈ B5 produces the ordered set partition of type B5 :
{{±1, ±4}, {−5, −3, 2}, {5, 3, −2}}
with one pair of non-zero blocks. Moreover, β produces exactly 41 partitions with two pairs of blocks, namely
{{1, 4}, {−1, −4}, {−5, −3, 2}, {5, 3, −2}},
{{±1}, {4}, {−4}, {−5, −3, 2}, {5, 3, −2}},
{{±1, ±4}, {5}, {−5}, {−3, 2}, {3, −2}},
{{±1, ±4}, {−5, −3}, {5, 3}, {2}, {−2}},
obtained by placing one extra separator in positions 0,1,3, and 4, respectively. For larger r, the idea is the same,
by adding more separators.
6 Proof of Theorem 4.2 - Type D
The proof for type D is a bit more tricky. The basic idea is the same as before: obtaining the whole set of
ordered set partitions of type D starting from permutations in Dn , by adding separators after every descent and
in the non-descent spots, which we call artificial separators.
The problem which naturally arises now is that, if we follow the same procedure used in the previous section,
we may obtain set partitions of type B which are not of type D, namely set partitions with zero-block containing
exactly one pair of elements. This happens exactly if there is a separator (either induced by a descent or an
artificial one) between γ(1) and γ(2), but not before γ(1).
In order to solve this problem, for any such γ ∈ Dn , we toggle the sign of γ(1), obtaining γ 0 ∈ Bn \ Dn , and
we apply the type B procedure to γ 0 , by obtaining a genuine set partition of type D without a zero-block. We
call this the switch operation.
Note that changing the sign of the first entry of γ produces an element γ 0 having a descent in 0, i.e. γ 0 (1) +
γ (2) < 0. In other words, to obtain the block decomposition associated to γ 0 , toggle the sign of the first entry
0
of γ and move the separator from position 1 to position 0.
For example, let γ = [3, −1, 4, −2, −6, −5] ∈ D6 . After placing the separators induced by the descents, we
have:
γ = [3 | −1, 4 | −2 | −6, −5].
Here, since 0 ∈
/ DesD (γ), the zero-block is {±3} and applying the procedure in type B we obtain the set partition
of type B6
{{±3}, {−1, 4}, {1, −4}, {2}, {−2}, {−5, −6}, {5, 6}},
57
which is not a legal set partition of type D6 , since the zero-block consists of only one pair. Toggling the sign of
γ(1), we have:
γ 0 = [ | −3, −1, 4 | −2 | −6, −5] ∈ B6 \ D6 ,
where the first separator stands for the descent at 0. This will give us the following set partition of type D6 :
{{−3, −1, 4}, {3, 1, −4}, {2}, {−2}, {−6, −5}, {6, 5}}.
For the next step, we denote any ordered set partition of type D in an abbreviated form, by writing only the
first block in each pair, e.g. {{−3}, {3}, {−4, −2, 1}, {4, 2, −1}} will now be written as {{−3}, {−4, −2, 1}}. We
call an ordered set partition of type D having an odd number of negative entries in this abbreviated notation an
odd partition.
The following lemma characterizes the structure of the odd partitions, which can not be obtained from
permutations of Dn by using the switch operation.
Lemma 6.1. The ordered odd partitions having r blocks, which can not be obtained from permutations in Dn
by a switch operation are exactly of the form
P 0 = {{∗}, P },
where ∗ stands for one element of [±n], and P consists of the blocks of a usual ordered set partition of the set
[n] \ {∗} with r − 1 blocks.
Proof. Note that the singleton {∗} cannot be a zero-block by the definition of an odd partition, and this is why
we require the partition P to have r − 1 blocks.
First, it is easy to see that if P is an odd partition starting with a singleton, then P can not be obtained from
any γ ∈ Dn by the switch operation, since that operation removes the separator between γ(1) and γ(2), and
hence it merges the two first blocks, and the first block has at least two elements.
On the other hand, if an odd partition P does not start with a singleton block, we now show that it can be
obtained by a switch of a permutation in Dn . Assume that B = {a1 < a2 < · · · < at } is the first block of P ,
where t > 1. If P is obtained from a permutation γ 0 which itself is a switch of some γ ∈ Dn , then we must have
γ 0 (1) = a1 and γ 0 (2) = a2 . Hence γ(1) = −γ 0 (1) = −a1 and γ(2) = γ 0 (2) = a2 . We deal with this situation
case-by-case:
1. If a1 > 0 and a2 > 0, then γ 0 is obtained from γ by the switch operation, where γ(1) = −a1 and γ(2) = a2
and we add an artificial separator between γ(1) and γ(2). Since 0 ∈ / DesD (γ), the switch operation is
required in order to get γ 0 .
2. If a1 < 0 and a2 < 0, then γ 0 is obtained from γ where γ(1) = −a1 and γ(a2 ) = a2 . Since a1 < a2 < 0, we
have −a1 > a2 , so there is a separator induced by a descent between γ(1) and γ(2), while 0 ∈ / DesD (γ) so
that the switch is indeed required.
3. If a1 < 0 and a2 > 0, then there is a permutation γ ∈ Dn such that γ(1) = −a1 > 0 and γ(2) = a2 > 0 so
that 0 ∈
/ DesD (γ) and the switch is required either due to a separator induced by a descent between γ(1)
and γ(2), or due to an artificial separator that we added.
In the next lemma we count the number of odd partitions of the form {{∗}, P }
Lemma 6.2. The number of odd partitions which cannot be obtained from permutations in Dn by a switch
operation is:
n2n−1 (r − 1)!S(n − 1, r − 1).
Proof. For constructing an odd partition, with structure given in Lemma 6.1, one can start by choosing the
unique element in the singleton {∗}, which can be done in n ways. Afterwards, one has to choose and order the
r − 1 blocks in P , which can be done in (r − 1)!S(n − 1, r − 1) ways. Finally, one has to choose the sign of any
entry in the partition P 0 = {{∗}, P }, in such a way that an odd number of entries will be signed, and this can
be done in 2n−1 ways.
58
Finally, we can now finish the proof of Theorem 4.2.
Proof of Theorem 4.2. As before, the equation in the statement of Theorem 4.2 is equivalent to the following:
r
X n−k
2r r!SD (n, r) = n2n−1 (r − 1)!S(n − 1, r − 1) + AD (n, k) .
r−k
k=0
The left-hand side of the above equation counts the number of ordered set partitions of type Dn with r parts.
The right-hand side counts the same set of partitions divided in two categories: those coming from the usual
procedure or from the switch operation induced by permutations in AD (n, k), and those that are not, which are
counted in Lemma 6.2. This completes the proof. 2
References
[BB05] A. Bjorner and F. Brenti. Combinatorics of Coxeter Groups. Graduate Texts in Mathematics 231,
Springer-Verlag, New York, 2005.
[Bon04] M. Bona. Combinatorics of Permutations. Chapman & Hall /CRC, 2004.
[Boy12] K.N. Boyadzhiev. Close Encounters with the Stirling Numbers of the Second Kind. Mathematics
Magazine, 85(4):252–266, 2012.
[Car59] L. Carlitz. Eulerian numbers and polynomials. Mathematics Magazine, 32(5):247–260, 1959.
[Eul36] L. Eulero. Methodus universalis series summandi ulterious promota. Commentarii academiæscientiarum
imperialis Petropolitanæ, 8:147–158, 1736. Reprinted in his Opera Omnia, series 1, volume 14, 124–137.
[Rei97] V. Reiner. Non-crossing partitions for classical reflection groups. Discrete Mathematics, 177(1–3):195–
222, 1997.
[Sta12] R. P. Stanley. Enumerative combinatorics, Vol. 1, Second edition. Cambridge Studies in Advanced
Mathematics 49, Cambridge Univ. Press, Cambridge, 2012.
[Sut00] R. Suter. Two Analogues of a Classical Sequence. Journal of Integer Sequences, 3, Article 00.1.8, 18 pp.,
2000.
[Zas81] T. Zaslavsky. The geometry of root systems and signed graphs. American Mathematical Monthly,
88:88–105, 1981.
59