In this paper we generalize a well-known identity relating Stirling numbers of the second kind and Eulerian numbers to Coxeter groups of types B and D. 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
Stirling numbers of the second kind, denoted by S(n; k), arise in a variety of problems in enumerative combinatorics. They rst appeared as the coe cients of the expansion of the polynomial xn in terms of the falling polynomials as presented in the following identity: xn = n X S(n; k) [x(x k=0 1) (x k + 1)]; see the survey of Boyadzhiev [Boy12]. However, their most common combinatorial interpretation is as counting the number of partitions of the set [n] := f1; : : : ; ng 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 de nition of the Eulerian numbers was rst given by Euler in an analytic context [Eul36, x13]. 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 2 Sn is an element of
Des( ) := fi 2 [n 1] j (i) > (i + 1)g; (1)
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
S(n; r) = 1 Xr A(n; k) n r! k=0 r k k :
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 2 W , namely the minimum k for which w = s1 sk with si 2 S. The right descent set of w 2 W is de ned to be
DR(w) := fs 2 S j `(ws) < `(w)g: 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] n f0g onto itself such that ( i) = (i) for all i 2 [ n; n] n f g
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 2 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. = [3; 2; 1; 4; 5] = As set of generators for Bn we take SB := fs1B; : : : ; snB 1; s0Bg where for i 2 [n siB := [1; : : : ; i
1; i + 1; i; i + 2; : : : ; n] and s0B := [ 1; 2; : : : ; n]: It is well known that (Bn; SB) is a Coxeter system of type B (see e.g., [BB05, x8.1]). The following characterizations of the right descent set of 2 Bn is well known [BB05].
2 Bn. Then
= where (0) := 0 (we use the usual order on the integers). In particular, 0 2 DesB( ) is a descent if and only if (1) < 0. We set desB( ) := jDesB( )j.
We set:
AB(n; k) := jf 2 Bn j desB( ) = k 1gj; 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 := fs0D; s1D; : : : ; snD 1g where for i 2 [n 1]
siD := siB and s0D := [ 2; 1; 3; : : : ; n]:
There is a well-known direct combinatorial way to compute the right descent set of x8.2]).
2 Dn, (see, e.g., [BB05,
= consists of subspaces which look typically like: fx 2 R8 j x1 = which can be represented in a simpler way like this: This was Reiner's motivation for de ning the partitions of type B as follows [Rei97]. Set [ n] := f 1; : : : ; ng. De nition 3.1. A set partition of type Bn is a partition of the set [ n] into blocks such that the following conditions are satis ed:
of the form f i j i 2 Eg for some E [n]).
C = C. This block is called the zero-block (if it exists, it is a set De nition 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 ff1; 2g; f 1; 2g; f 3gg is a set partition of type B3 but not of type D3, while ff1g; f 1g; f 2; 3gg 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 de ne now the concept of an ordered set partition: De nition 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 satis ed:
If the zero-block exists, then it appears as the rst block.
For each block C which is not a zero-block, the blocks C and
Theorem 4.1. For all positive integers n and r, we have
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
AB(n; k) = k X ( 1)k r 2rr! SB(n; r) r=1 n k r r : Corollary 4.2. For all positive integers n and r, we have
AD(n; k) = k X( 1)k r 2rr! SD(n; r) + n2n 1(r r=1
(i)g, where i denotes the rst descent of = [3; 2; 1; 4; 5] 2 B5. We add the separators after the descents, = 3 When is written in complete notation, the de nition 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. = 1. If r = k (where desB( ) = k), the above construction produces an ordered set partition of type Bnwith exactly r pairs of blocks. In fact, if 0 62 DesB( ), then the digits in the rst 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 fCig; f Cig, where Ci denotes the increasing run starting after the ith descent. If 0 2 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 62 DesB( ) then one might also add a separator before the rst place (which means that the rst 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 nr kk , and it is independent whether 0 is a descent of or not. 2 For example = [1; 4 j
5; 3; 2] 2 B5 produces the ordered set partition of type B5: with one pair of non-zero blocks. Moreover,
produces exactly 41 partitions with two pairs of blocks, namely ff 1; 4g; f 5; 3; 2g; f5; 3; 2gg ff1; 4g; f 1; 4g; f 5; 3; 2g; f5; 3; 2gg; ff 1g; f4g; f 4g; f 5; 3; 2g; f5; 3; 2gg; ff 1; 4g; f5g; f 5g; f 3; 2g; f3; 2gg; ff 1; 4g; f 5; 3g; f5; 3g; f2g; f 2gg; 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 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 arti cial 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 arti cial one) between (1) and (2), but not before (1).
In order to solve this problem, for any such 2 Dn, we toggle the sign of (1), obtaining 0 2 Bn n 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 rst entry of produces an element 0 having a descent in 0, i.e. 0(1) + 0(2) < 0. In other words, to obtain the block decomposition associated to 0, toggle the sign of the rst entry of and move the separator from position 1 to position 0.
For example, let = [3; 1; 4; 2; 6; 5] 2 D6. After placing the separators induced by the descents, we have: = [3 j 1; 4 j 2 j Here, since 0 2= DesD( ), the zero-block is f 3g and applying the procedure in type B we obtain the set partition of type B6 ff 3g; f 1; 4g; f1; 4g; f2g; f 2g; f 5; 6g; f5; 6gg; 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 = [ j 3; 1; 4 j 2 j 6; 5] 2 B6 n D6; where the rst separator stands for the descent at 0. This will give us the following set partition of type D6: ff 3; 1; 4g; f3; 1; 4g; f2g; f 2g; f 6; 5g; f6; 5gg:
For the next step, we denote any ordered set partition of type D in an abbreviated form, by writing only the rst block in each pair, e.g. ff 3g; f3g; f 4; 2; 1g; f4; 2; 1gg will now be written as ff 3g; f 4; 2; 1gg. 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 = ff g; P g; where stands for one element of [ n], and P consists of the blocks of a usual ordered set partition of the set [n] n f g with r 1 blocks.
Proof. Note that the singleton f g cannot be a zero-block by the de nition 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 2 Dn by the switch operation, since that operation removes the separator between (1) and (2), and hence it merges the two rst blocks, and the rst 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 = fa1 < a2 < < atg is the rst block of P , where t > 1. If P is obtained from a permutation 0 which itself is a switch of some 2 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 and we add an arti cial separator between required in order to get 0.
by the switch operation, where (1) = a1 and (2) = a2 (1) and (2). Since 0 2= DesD( ), the switch operation is 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 2= DesD( ) so that the switch is indeed required. 3. If a1 < 0 and a2 > 0, then there is a permutation 2 Dn such that (1) = a1 > 0 and (2) = a2 > 0 so that 0 2= DesD( ) and the switch is required either due to a separator induced by a descent between (1) and (2), or due to an arti cial separator that we added.
In the next lemma we count the number of odd partitions of the form ff g; P g Lemma 6.2. The number of odd partitions which cannot be obtained from permutations in Dn by a switch operation is: Proof. For constructing an odd partition, with structure given in Lemma 6.1, one can start by choosing the unique element in the singleton f g, 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 = ff g; P g, in such a way that an odd number of entries will be signed, and this can be done in 2n 1 ways.
2rr!SD(n; r) = n2n 1(r 1)!S(n :
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
Mathematics [Car59] L. Carlitz. Eulerian numbers and polynomials. Mathematics Magazine, 32(5):247{260, 1959. [Rei97] V. Reiner. Non-crossing partitions for classical re ection groups. Discrete Mathematics, 177(1{3):195{ 222, 1997.