Publ. I.R.M.A. Strasbourg, 1984, 229/S–08 Actes 8^{e} Séminaire Lotharingien, p. 31–36

EULERIAN NUMBERS, FOULKES CHARACTERS

AND LEFSCHETZ CHARACTERS OF S_{n}

BY

Adalbert KERBER AND Karl-Joseph THÜRLINGS

ABSTRACT. — The aim of this talk is to point out a connection between the characters which FOULKES introduced in order to give a representation theoretical generalization of Eulerian numbers and certain Lefschetz characters of S_{n} which A. BJ^{}ÖRNER mentioned at his talk in Feuerstein and which were described in detail by R. STANLEY in [1]. The missing link is a theorem on the irreducible constituents of Foulkes’ characters.

1. Eulerian numbers. — Let π = (π(1) … π(n)) be an element of the symmetric group S_{n}, e.g. (13248765) ∈ S_{8} (list notation !) with the up-and-down-sequence A(π) (rises indicated by +, falls denoted by −), for example

A((13248765)) = + − + + − − − .

The number of permutations with a given number of rises, i.e. of entries + in its up-down sequence, defines an Eulerian number :

A(n, k) := |{π ∈ S_{n} | A(π) has k rises}| .

According to FOULKES, A(π) yields a skew diagram via the rule

\begin{aligned}+ ← & × \\ & ↓ − \end{aligned}

This means, that to an entry + of A(π) there corresponds a node × that has to be added at the left of the last node added, and in the same row. Correspondingly to an entry − there corresponds a node that has to be added just below the last node. For example the sequence (+−++−−−) mentioned above gives

\begin{aligned}& & × & × \\ × & × & × \\ × \\ × \\ × \end{aligned} according to \begin{aligned}& & + & × \\ + & + & − \\ − \\ − \\ − \end{aligned} .

A. KERBER AND K.-J. THÜRLINGS

This resulting skew diagram is the rim part of λ(A) : R_{11}^{λ(A)} = (431^{3})/(2). Recall the definition of skew representation by the Littlewood-Richardson rule :

[λ/μ] := ∑_{ν}([μ][ν], [λ])[ν].

Theorem (Foulkes). — The number of permutations with given up-down sequence A can be identified with a dimension of a skew representation :

|{π | A(π) = A}| = dim[R_{11}^{λ(A)}].

For example, if we put A := + − + + − − − then the number of permutations with this sequence isthe dimension of [(431^{3})/(2)] which has the decomposition [421^{2}] + [41^{4}] + [3^{2}1^{2}] + [321^{3}] and therefore the dimension 245. More generally we have the following generalization of Foulkes’ result :

Theorem (K/Th). — The decomposition of [R_{11}^{λ(A)}] is obtained from A by successive applications of the rule

\begin{matrix}× & ↗+ \\ ↙− \end{matrix}

By this pictorial description we mean that to an entry + of A there corresponds a node × which has to be added to the right of the last node, maybe in a higher row, while to an entry − there corresponds a node added to the left of the last node or in a lower row. Consider once more the example A = (+ − + + − − −). We start with a node ×, and the first entry of A is a +, so the corresponding node has to be added, according to the rule, to the right of the starting node, i.e. we obtain the diagram ×⊗, where the last node added is encircled. Now the second entry of A is a minus sign, hence the corresponding addition of a node is again uniquely determined, and we get the diagram

\begin{matrix}× & × \\ ⊗ \end{matrix} .

The next entry of A is a plus sign, so that there are two places open for an additional node which are to the right of the node which was added last time :

\begin{matrix}× & × & ⊗ \\ × \end{matrix} and \begin{matrix}× & × \\ × & ⊗ \end{matrix} .

The next steps yield the following cascade of diagrams :

\begin{aligned}× & × & × & ⊗ \\ × \\ & ↙ & ↘ \end{aligned}  \begin{aligned}× & × & ⊗ \\ × & × \\ & ↙ & ↘ \end{aligned}

FOULKES AND LEFSCHETZ CHARACTERS

\begin{aligned}× & × & × & × \\ × \\ ⊗ \\ & & ↓ \end{aligned} \begin{aligned}× & × & × & × \\ × & ⊗ \\ & ↓ \end{aligned} \begin{aligned}× & × & × \\ × & × \\ ⊗ \\ & ↓ \end{aligned} \begin{aligned}× & × & × \\ × & × & ⊗ \\ & ↓ \end{aligned}

\begin{matrix}× & × & × & × \\ × \\ × \\ × \\ × \end{matrix} \begin{matrix}× & × & × & × \\ × & × \\ × \\ × \end{matrix} \begin{matrix}× & × & × \\ × & × \\ × \\ × \\ × \end{matrix} \begin{matrix}× & × & × \\ × & × & × \\ × \\ × \end{matrix}

Hence from A = (+ − + + − − −) we obtain the diagrams

[4, 1^{4}], [4, 2, 1^{2}], [3, 2, 1^{3}], [3^{2}, 1^{2}],

and each one of them exactly once.

Proof. — “By example”

R_{11}^{λ((+−−++−−+++))} = det ( \begin{matrix}[2] & [3] & [6] & [7] & [11] \\ 1 & [1] & [4] & [5] & [9] \\ 0 & 1 & [3] & [4] & [8] \\ 0 & 0 & 1 & [1] & [5] \\ 0 & 0 & 0 & 1 & [4] \end{matrix} )

= [4] det ( \begin{matrix}[2] & [3] & [6] & [7] \\ 1 & [1] & [4] & [5] \\ 0 & 1 & [3] & [4] \\ 0 & 0 & 1 & [1] \end{matrix} ) − det ( \begin{matrix}[2] & [3] & [6] & [11] \\ 1 & [1] & [4] & [9] \\ 0 & 1 & [3] & [8] \\ 0 & 0 & 1 & [5] \end{matrix} )

= [4][(7, 6, 6, 4)/(5, 5, 3, 3)] − [(8, 7, 7, 5)/(6, 6, 4)]

= [4][R_{11}^{λ((+−−++−))}] − [R_{11}^{λ((+−−++−++++))}].

Hence, the following lemma completes the proof.

Lemma. — Let A denote an up-and-down sequence. Then, for each k ∈ N we have

[k + 1][R_{11}^{λ(A)}] = [R_{11}^{λ((A++···+))}] + [R_{11}^{λ((A−+···+))}].

2. Foulkes characters. — Foulkes’ result gives the following interpretation of Eulerian numbers as sums of dimensions of skew representations :

A(n, k) = ∑_{A,k ups} dim[R_{11}^{λ(A)}],

while the above generalization gives a more general result in terms of characters :

χ^{n,k} := ∑_{A,k ups} χ^{R_{11}^{λ(A)}}.

We suggest to call these characters Foulkes characters. They have the following remarkable properties :

Theorem (Foulkes). — (i) no. of cycles of π = no. of cycles of ρ ⇒ χ^{n,k}(π) = χ^{n,k}(ρ) ; (ii) χ^{n,0} = ζ^{(1^{n})}, χ^{n,n−1} = ζ^{(n)}, χ^{n,k} = ζ^{(1^{n})} ⊗ χ^{n,n−1−k}; (iii) The Foulkes characters satisfy the following recursion :

χ_{μ}^{n,k} = χ_{μ^{∗}}^{n−1,k−1} − χ_{μ^{∗}}^{n−1,k}, μ^{∗} := (μ_{1}, …, μ_{i−1}, μ_{i} − 1, μ_{i+1}, …).

Further Properties.

(i) (χ^{n,k}, ζ^{λ}) > 0 ⇒ λ_{1} ≤ k + 1, λ′_{1} ≤ n − k;

(ii) (χ^{n,k}, ζ^{(j+1,1^{n−j−1})}) > 0 ⇔ j = k; (iii) The χ^{n,k} are linearly independent ; (iv) If χ : S_{n} → C denotes a character, depending only on the number of cyclic factors, then we have

χ = ∑_{i} \frac{(χ, ζ^{(i+1,1^{n−i−1})})}{f^{(i+1,1^{n−i−1})}}χ^{n,i}.

Using 5.8.30 in KERBER-THÜRLINGS we obtain

Theorem. — The “Pólya-character” χ, defined by

χ(π) := m^{no. of cycles of π}

has the following decomposition into irreducibles :

χ = ∑_{k} \binom{m + k}{n}χ^{n,k}.

3. Foulkes tables. — This section contains the Foulkes tables F_{i} := (χ_{j}^{n,k}) of the symmetric groups S_{n}, for n ≤ 7. We recall that the j-th column of the Foulkes table contains in its i-th row the value of the Foulkes characters χ^{n,i} on the classes of elements which consist of j cyclic factors.

The 0-th row indicates the column numbers j, while the 0-th column shows the row numbers i.

F_{1} = \begin{matrix}i\j & 1 \\ 0 & 1 \end{matrix} , F_{2} = \begin{matrix}i\j & 2 & 1 \\ 0 & 1 & −1 \\ 1 & 1 & 1 \end{matrix} , F_{3} = \begin{matrix}i\j & 3 & 2 & 1 \\ 0 & 1 & −1 & 1 \\ 1 & 4 & 0 & −2 \\ 2 & 1 & 1 & 1 \end{matrix} ,

F_{4} = \begin{matrix}i\j & 4 & 3 & 2 & 1 \\ 0 & 1 & −1 & 1 & −1 \\ 1 & 11 & −3 & −1 & 3 \\ 2 & 11 & 3 & −1 & −3 \\ 3 & 1 & 1 & 1 & 1 \end{matrix} , F_{5} = \begin{matrix}i\j & 5 & 4 & 3 & 2 & 1 \\ 0 & 1 & −1 & 1 & −1 & 1 \\ 1 & 26 & −10 & 2 & 2 & −4 \\ 2 & 66 & 0 & −6 & 0 & 6 \\ 3 & 26 & 10 & 2 & −2 & −4 \\ 4 & 1 & 1 & 1 & 1 & 1 \end{matrix} ,

F_{6} = \begin{matrix}i\j & 6 & 5 & 4 & 3 & 2 & 1 \\ 0 & 1 & −1 & 1 & −1 & 1 & −1 \\ 1 & 57 & −25 & 9 & −1 & −3 & 5 \\ 2 & 302 & −40 & −10 & 8 & 2 & −10 \\ 3 & 302 & 40 & −10 & −8 & 2 & 10 \\ 4 & 57 & 25 & 9 & 1 & −3 & −5 \\ 5 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} ,

F_{7} = \begin{matrix}i\j & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ 0 & 1 & −1 & 1 & −1 & 1 & −1 & 1 \\ 1 & 120 & −56 & 24 & −8 & 0 & 4 & −6 \\ 2 & 1191 & −245 & 15 & 19 & −9 & −5 & 15 \\ 3 & 2416 & 0 & −80 & 0 & 16 & 0 & −20 \\ 4 & 1191 & 245 & 15 & −19 & −9 & 5 & 15 \\ 5 & 120 & 56 & 24 & 8 & 0 & −4 & −6 \\ 6 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} .

4. The connection with a result of Stanley. — We consider groups acting on posets M such that x ≤ y ⇔ gx ≤ gy. An important example is the action of S_{n} on 2^{n}, the power set of n, with the inclusion as partial order.

Denote by R a subset of the set of ranks, and by K_{R}(M) a set of rank selected chains. Put K_{R}(M, C) := C^{K_{R}(M)} and denote by H_{i}(M_{R}, C) the homology group. Using these notions we can introduce

κ_{R}(g) := trace of g on K_{R}(M, C), γ_{R,i}(g) := trace of g on H_{i}(M_{R}, C),

and

ν_{R}(g) := ∑_{i=0}^{r}(−1)^{|R|−i}γ_{R,i}(g),

the Lefschetz character. Then, to begin with, we have the following well known facts :

κ_{R} = ∑_{T ⊆R} ν_{T} , or, equivalently, ν_{R} = ∑_{T ⊆R}(−1)^{|R\T |}T.

Theorem (Stanley). — If R := (n_{1}, …, n_{k})_{<}, ρ := (n_{1}, n_{2} − n_{1}, …, n_{k} − n_{k−1}, n − n_{k}) ; ρ^{∗} := partition obtained by reordering, then

(i) κ_{R} = ξ^{ρ^{∗}}, the Young character, = ∑_{λ⊢n} |ST^{λ′}(ρ^{∗})| ζ^{λ} (standard

tableaux, shape λ′, content ρ^{∗}).

(ii) ν_{R} = ∑_{λ⊢n} |ST_{R}^{λ′}(1^{n})| ζ^{λ} (standard Young tableaux with R as set of

ascents).

Hence we obtain from the above discussion of Foulkes characters :

Theorem.

χ^{n,n−k−1} = ∑_{R} ν_{R} (|R| = k).

This shows the connection between Foulkes characters and the Lefschetz characters of S_{n} on 2^{n}.

REFERENCES

[1] FOULKES (H.O.). — Eulerian numbers, Newcomb’s problem and representations of symmetric groups, Discrete Math., vol. 30, 1980, p. 3–49.

[2] KERBER (Adalbert) and TH^{}ÜRLINGS (Karl-Josef). — Symmetrieklassen von Funktionen und ihre Abzählungstheorie II (in print), III (in preparation), Bayreuther Math. Schriften.

[3] STANLEY (Richard). — Some aspects of groups acting on finite posets, J. Combinatorial Theory, Ser. A, vol. 32, 1982, p. 132–161.

Adalbert Kerber and Karl-Josef Thürlings, Lehrstuhl II für Mathematik, Universität Bayreuth, D-95440 Bayreuth, Deutschland email : kerber@btm2x6.mat.uni-bayreuth.de