Séminaire Lotharingien de Combinatoire 72 (2015), Article B72e

BIJECTIVE PROOFS OF CHARACTER EVALUATIONS USING THE TRACE FOREST OF JEU DE TAQUIN

WENJIE FANG

Abstract. Irreducible characters of the symmetric group are of special interest in combinatorics. They can be expressed either combinatorially using ribbon tableaux, or algebraically using contents. In this paper, these two expressions are related in a combinatorial way. We first introduce a fine structure in the famous jeu de taquin called “trace forest”, with the help of which we are able to count certain types of ribbon tableaux, leading to a simple bijective proof of a character evaluation formula in terms of contents that dates back to Frobenius (1901). Inspired by this proof, we give an inductive scheme that provides combinatorial proofs of more complicated character formulae in terms of contents.

1. Introduction

Irreducible characters in the symmetric group have long attracted the attention of combinatorialists and group theorists. When evaluated at a fixed small partition padded with parts of size 1, they can be expressed in terms of contents. More precisely, such an evaluation (or “character value”), when divided by the dimension and multiplied by a suitable falling factorial, can be expressed as a polynomial in content power sums. This normalization is sometimes called “central character”, and the study of these central characters dates back to Frobenius. In [Fro01, Ing50], for a partition λ of an integer n, the following evaluations were given:

n(n − 1)χ_{2,1^{n−2}}^{λ} = 2f^{λ} (∑_{w∈λ} c(w)) ,

n(n − 1)(n − 2)χ_{3,1^{n−3}}^{λ} = 3f^{λ} (∑_{w∈λ}(c(w))^{2} + n(n − 1)/2) ,

n(n − 1)(n − 2)(n − 3)χ_{4,1^{n−4}}^{λ} = 4f^{λ} (∑_{w∈λ}(c(w))^{3} + (2n − 3) ∑_{w∈λ} c(w)) .

Here, χ_{μ}^{λ} is the irreducible character indexed by λ evaluated at the conjugacy class indexed by another partition μ of n, f^{λ} is the dimension of the corresponding representation, c(w) is the content of the cell w, and we sum over cells w in the Ferrers diagram of λ. We postpone detailed definitions of these notions and related ones to Section 2. We observe that these character evaluations can be expressed as a polynomial in n and certain sums of powers of contents called content evaluations. This fact was proved in [CGS04] for the general case, and in [Las08] an explicit formula for χ_{μ,1^{n−k}}^{λ} was given, where μ is a partition of k and n ≥ k. Furthermore, functions of contents appear in many contexts, such as in the proof that the generating function of some family of combinatorial maps is a solution to the KP hierarchy (cf. [GJ08]). Therefore, a better understanding of the combinatorial importance of contents would also help us better understand other combinatorial phenomena related to contents.

This work is partially supported by ANR IComb (ANR-08-JCJC-0011) and ANR Cartaplus (ANR-12-JS02-001-01).

Such character evaluations in terms of contents are mostly obtained in an algebraic way, either using the Jucys–Murphy elements (e.g., [DG89]), or with the help of symmetric functions (e.g., [CGS04, Las08]). They are also related to shifted symmetric functions evaluated at parts of a partition (e.g., [KO94]). On the other hand, there is a well-developed combinatorial representation theory of the symmetric group (cf. [Sta99, Sag01]), in which we can express characters combinatorially in terms of ribbon tableaux using the Murnaghan– Nakayama rule. It is thus interesting to relate ribbon tableaux to content evaluations using combinatorial tools, for example Schützenberger’s famous jeu de taquin.

Our main results are combinatorial proofs of the aforementioned character formulae, and a promising general method to obtain such proofs of other similar formulae expressing characters in terms of content power sums. In this article, we look into the fine structure of jeu de taquin. In Section 3, we define a notion called “trace forest” for skew tableaux that encapsulates the paths of all possible jeu de taquin moves on such tableaux. Using this notion, we give a simple bijective proof of the formula above for χ_{2,1^{n−2}}^{λ} by counting corresponding ribbon tableaux. To the author’s knowledge, no such bijective proof has been known before. Inspired by this simple proof, in Section 4 we investigate the possibility of using trace forests to give counting proofs of more involved character evaluation formulae. For this purpose, we sketch a general scheme using induction on the tree structure of trace forests to count certain ribbon tableaux. This scheme leads to combinatorial proofs of the other two character evaluation formulae above for χ_{3,1^{n−2}}^{λ} and χ_{4,1^{n−2}}^{λ}. Further possible development of this scheme is also discussed.

2. Preliminaries

2.1. Partitions and standard tableaux. A partition λ is a finite non-increasing sequence (λ_{i})_{i>0} of positive integers. We say that λ is a partition of n (denoted by λ ⊢ n) if ∑_{i} λ_{i} = n. The Ferrers diagram (in French convention) of a partition λ (also denoted by λ by abuse of notation) is the graphical representation of λ consisting of left-aligned rows of boxes (also called cells), in which the i-th row has λ_{i} boxes. We assume that cells are all unit squares, and the center of the first cell in the first row is the origin of the plane. This representation in French convention will be used throughout this article. For a cell w whose center is in (i, j), we define its content to be c(w) = i − j. Figure 1 gives an example of a Ferrers diagram, drawn in French convention, with the content of each cell.

A standard tableau of shape λ ⊢ n is a filling of the Ferrers diagram of λ using integers from 1 to n such that each number is used exactly once, with increasing rows and columns. Figure 1 also gives an example of a standard tableau. We denote by f^{λ} the number of standard tableaux of shape λ. The number f^{λ} is also the dimension of the irreducible representation of the symmetric group S_{n} indexed by λ (cf. [Sag01, VO04]).

0 1 2 3 4 -1 0 1 -2 -1 0 -3 -2 (a)  1 2 5 9 11 3 7 10 4 8 13 6 12 (b)  (c)  4 6 5 1 3 8 2 7 (d)

Figure 1. (a) the Ferrers diagram of the partition (5, 3, 3, 2), with the content of each cell. (b) a standard tableau of shape (5, 3, 3, 2). (c) the skew diagram of the skew partition (5, 3, 3, 2)/(3, 2). (d) a skew tableau of shape (5, 3, 3, 2)/(3, 2).

The definitions above can be generalized to so-called skew-partitions. A skew-partition λ/μ is a pair of partitions (λ, μ) such that, for all i > 0, we have λ_{i} ≥ μ_{i}. Graphically, this inequality condition is equivalent to the condition that the Ferrers diagram of λ totally covers that of μ. We then define the skew diagram of shape λ/μ as the (set-theoretic) difference of the Ferrers diagrams of λ and of μ, i.e., the Ferrers diagram of λ without cells that also appear in that of μ. Figure 1 gives an example of a skew diagram.

We now define the counterpart of standard tableau for skew diagrams. A skew tableau of shape λ/μ is a filling of the skew diagram of λ/μ that satisfies all conditions of standard tableaux. Figure 1 gives an example of a skew tableau. We denote the number of skew tableaux of shape λ/μ by f^{λ/μ}.

Standard tableaux and skew tableaux are classical combinatorial objects closely related to the representation theory of the symmetric group. In [VO04, Sag01, Sta99], details of this relationship are described.

2.2. Ribbon tableaux and the Murnaghan–Nakayama rule. We denote by S_{n} the symmetric group formed by permutations of n elements. For partitions λ, μ of n, we denote the irreducible character of S_{n} indexed by λ evaluated at the conjugacy class indexed by μ by χ_{μ}^{λ}.

Irreducible characters can be expressed in a combinatorial way using so-called ribbon tableaux. A ribbon is a special skew diagram that is connected and has no 2 × 2 block of cells. The height ht(λ/μ) of a ribbon λ/μ is the number of rows it spans minus one. A ribbon tableau T of shape λ is a sequence of partitions ∅ = λ^{(0)}, λ^{(1)}, …, λ^{(k)} = λ such that λ^{(i)}/λ^{(i−1)} is a ribbon for all i > 0. This ribbon tableau T can also be represented as a filling of the Ferrers diagram of λ, where cells in λ^{(i)}/λ^{(i−1)} are filled with entry i. The entry sequence of T is (a_{1}, a_{2}, …, a_{k}), with a_{i} the number of cells in λ^{(i)}/λ^{(i−1)}. The total height of T is defined by ht(T) = ∑_{i} ht(λ^{(i)}/λ^{(i−1)}), and the sign of T is defined by sgn(T) = (−1)^{ht(T)}. Figure 2 gives an example of a ribbon and a ribbon tableau.

The Murnaghan–Nakayama rule (cf. Chapter 7.17 of [Sta99]) provides a combinatorial interpretation of the irreducible characters. According to this rule, we have χ_{μ}^{λ} = ∑_{T} sgn(T), where we sum over all ribbon tableau T of shape λ and entry sequence μ. For a partition μ ⊢ k and an integer n > k, we denote by μ, 1^{n−k} the partition obtained by padding μ with

(a)  1 1 1 1 1 2 2 2 2 3 3 4 5 (b)

Figure 2. (a) the ribbon (5, 4, 4)/(3, 3, 1) of height 2. (b) a ribbon tableau T of shape (5, 3, 3, 2) with entry sequence (5, 4, 2, 1, 1) and sgn(T) = 1.

n − k parts of size 1. In this article, for a fixed “small” partition μ ⊢ k, we are interested in the evaluation of χ_{μ,1^{n−k}}^{λ} for arbitrary λ ⊢ n in terms of contents. According to the Murnaghan–Nakayama rule, this involves ribbon tableaux of shape λ and entry sequence μ, 1^{n−k}.

Lemma 2.1 (cf. [CGS04]). For partitions λ ⊢ n, μ ⊢ k and n > k, we have

χ_{μ,1^{n−k}}^{λ} = ∑_{ν⊢k} f^{λ/ν}χ_{μ}^{ν}.

Proof. Let T_{0} be a ribbon tableaux of shape λ and entry sequence μ, 1^{n−k}. By retaining only the last n − k ribbons of size 1 in T_{0}, we obtain a skew tableau T_{1}, and T = T_{0} \ T_{1} is a ribbon tableau with entry sequence μ. This is clearly a bijection between T_{0} and (T_{1}, T). Moreover, sgn(T) = sgn(T_{0}). We now add up all the signs of all T_{0} in bijection with (T_{1}, T), first by the shape ν of T, then by each T_{1} of shape λ/ν, and finally by each T. The proof is completed by applying the Murnaghan–Nakayama rule. □

If we suppose that the character table of S_{k} is known, then, by the above lemma and the fact that irreducible characters linearly span the space of class functions (cf. Chapter 2.6 of [Ser77]), for all λ ⊢ n > k and all μ ⊢ k, the evaluation of the character χ_{μ,1^{n−k}}^{λ} is equivalent to computing the number of skew tableaux of shape λ/θ for all θ ⊢ k. Furthermore, it is already known (cf. [KO94] and Theorem 8.1 in [OO97]) that f^{λ/θ} can be expressed in content power sums via shifted Schur functions. It is thus interesting for us to study skew tableaux.

2.3. Jeu de taquin. The jeu de taquin is a bijection between skew tableaux of different shapes. It was first introduced by Schützenberger, and it turned out to be a powerful tool in the combinatorial representation theory of the symmetric group. Its applications include the Schützenberger involution, the Littlewood–Richardson rule (c.f [Sta99] for both), and also a bijective proof of Stanley’s hook-content formula (cf. [Kra99]). An introduction to jeu de taquin can be found in Appendix A of [Sta99].

We now define building blocks of jeu de taquin on skew tableaux, which are local exchanges of entries in the tableaux. Given a skew tableau T with a distinguished entry ∗, the incoming step tries to exchange ∗ with one of its “inward” neighbours (the ones immediately below or to the left) while preserving increase of entries of the skew tableau along rows and columns except for the distinguished entry ∗. This is always possible as on the left side of Figure 3. The out-going step is similarly defined, by exchange with entries immediately above or to the

\begin{matrix}x \\ y \\ * \\ * \\ y \\ x \\ x \\ * \\ y \\ x ≥ y \\ x < y \\ (a) \end{matrix}  \begin{matrix}y \\ x \\ * \\ * \\ x \\ y \\ y \\ * \\ x \\ x > y \\ x ≤ y \\ (b) \end{matrix}

Figure 3. Incoming step (a) and out-going step (b) in jeu de taquin

right. Figure 3 illustrates the precise rule of both kinds of steps. We verify that incoming steps are exactly the reverse of out-going steps.

We now define the incoming slide of the distinguished entry ∗ as successive applications of the incoming steps to ∗ until it has no neighbour below and to the left, then remove the cell where ∗ is located in the end. Since incoming steps are reversible, given the distinguished entry and the resulting skew tableau, we can also reverse an incoming slide. Therefore, the incoming slide, which is a global operation on tableaux, is also reversible by restoring the cell with ∗, doing successive out-going steps and stopping at the point where the distinguished entry also verifies the conditions of increase of entries.

We now give a bijection that relates standard tableaux and skew tableaux using jeu de taquin.

Lemma 2.2. For a partition λ ⊢ n and an integer k > 0, jeu de taquin gives a bijection between the following two sets:

• the set of tuples (T, a_{1}, …, a_{k}), where T is a standard tableau of shape λ, and the a_{i}’s are distinct integers between 1 and n;

• the set of tuples (μ, T_{0}, T_{1}, a_{1}, …, a_{k}), where μ is a partition of k, T_{0} a skew tableau of shape λ/μ with entries from 1 to n − k, T_{1} a standard tableau of shape μ with entries from 1 to k, and the a_{i}’s are distinct integers between 1 and n.

Proof. We apply the incoming slide to a_{1}, …, a_{k} successively in T. In this way, we obtain a skew tableau T′_{0} of shape λ/μ for a certain partition μ ⊢ k and a standard tableau T_{1} of shape μ of entries from 1 to k that indicates the exclusion order of cells (the first excluded cell has entry 1, the second has entry 2, etc.). The entries in T′_{0} are all integers from 1 to n except all a_{i}’s. Since all the a_{i}’s are known, we can renumber entries in T′_{0} to produce a standard tableau of entries from 1 to n − k, and the reconstruction from T_{0} to T′_{0} is easy given the a_{i}’s. Since incoming slides are reversible, given (a_{1}, …, a_{k}), T_{0}, T_{1}, we can reconstruct T. We conclude that this defines indeed a bijection. Figure 4 gives an example with λ = (5, 3, 3, 2) and μ = (2). □

From the proof above, we conclude that, to compute a certain f^{λ/μ} for μ ⊢ k, it suffices to count the number of tuples (T, (a_{1}, …, a_{k})), with T a standard tableau of shape λ, that are associated to any tuple of the form (μ, T_{0}, T_{1}, (a_{1}, …, a_{k})). To accomplish this task, we need to know more about the fine structure of jeu de taquin.

\begin{matrix}1 \\ 2 \\ 5 \\ 9 \\ 11 \\ 3 \\ 7 \\ 10 \\ 4 \\ 8 \\ 13 \\ 6 \\ 12 \\ (12,5) \\ T \\ 12 \\ 2 \\ 5 \\ 9 \\ 11 \\ 1 \\ 3 \\ 10 \\ 4 \\ 7 \\ 13 \\ 6 \\ 8 \\ (12,5) \\ 12 \\ 5 \\ 2 \\ 9 \\ 11 \\ 1 \\ 3 \\ 10 \\ 4 \\ 7 \\ 13 \\ 6 \\ 8 \\ (12,5) \\ 1 \\ 2 \\ 2 \\ 8 \\ 10 \\ 1 \\ 3 \\ 9 \\ 4 \\ 6 \\ 11 \\ 5 \\ 7 \\ (12,5) \\ T_{1} \\ T_{0} \end{matrix}

Figure 4. Example of the bijective relation between standard tableaux and skew tableaux via jeu de taquin

1 2 5 9 11 3 7 10 4 8 13 6 12 4 9 10 3 5 1 6 7 2 8

Figure 5. Examples of skew tableaux and their trace forests

3. Trace forest of jeu de taquin

We will now define a structure related to jeu de taquin in skew tableaux called “trace forest”. It is essentially a directed graph whose vertices are cells in the tableau, and it encapsulates the trace of the incoming slide of each entry. We begin with a definition. For a cell c in F, we call the cell immediately to its right the right child of c, and the cell immediately above the upper child of c. We write c_{<} and c_{∨} for these cells, respectively.

Definition 3.1. Given a skew tableau T, its trace forest is the directed graph F with cells in T as vertices, the edges being defined as follows. For a cell c in T, we put an arc from c to the cell with larger entry among the cells immediately below or to the left.

Remark. The trace forest of a skew tableau T as defined above is indeed a forest. For, by the order of coordinates, it is clear that no oriented cycle exists. If we assume, by contradiction, that there exists a cycle in the underlying unoriented graph, then there is at least one vertex with at least two out-going arcs. However, this is impossible in our construction. Therefore the constructed graph is a forest, rooted at cells without neighbour below and to the left.

Figure 5 gives some examples of skew tableaux and their trace forests, where directions of arcs are omitted since they either point down or to the left, which is unambiguous. For a skew tableau T, let F be its trace forest. By definition, the incoming step out of any cell c ∈ T follows exactly the out-going arc from c, if there is. By a simple induction on F, we see that the incoming slide of the entry of any cell c ∈ T coincides with the path from c to its root in F, which gives the structure F the name “trace forest”. It is also clear that, if a cell c is on a tree S rooted at the cell a in the trace forest F, the incoming slide for the entry in c must end in a. We denote by F_{<} and F_{∨} the subtree of F rooted in c_{<} and c_{∨} respectively.

We now study how an incoming slide changes the trace forest of a skew tableau.

Let T be a skew tableau, S a tree in its trace forest rooted in r. For a cell c ∈ S, we write T^{c} for the tableau obtained by applying an incoming slide to the entry contained in c, and

P_{h} P_{v} D_{<} cR A D_{∨} ry∗ z∗ T d d_{2} d_{0} d_{1} ∗ yz∗ T^{c} d d_{2} d_{0} d_{1} z > y

Figure 6. Fine structure of the trace forest

F^{c} its trace forest. The cells in S \ {r} are partitioned into the following categories, as in Figure 6:

• D_{<}(c) (respectively D_{∨}(c)), the subtree rooted at the right child (respectively the upper child) of c;

• P_{h}(c) (respectively P_{v}(c)), the set of cells among c and its ancestors with a horizontal (respectively vertical) out-going arc;

• R(c) (respectively A(c)), the set of cells not in categories above and whose incoming

slide path lies weakly below (respectively weakly above) that of c. We define C_{<}(c, S) = D_{<}(c) ∪ P_{h}(c) ∪ R(c) and C_{∨}(c, S) = D_{∨}(c) ∪ P_{v}(c) ∪ A(c), and, by

abuse of notation, we consider these sets of cells as subsets of cells of both T and T^{c}. We can see that C_{<}(c, S) and C_{∨}(c, S) divide cells in S \ {r} into two groups. In the following lemma, we see that this grouping of cells is related to the structure of F^{c}.

Lemma 3.2. For a skew tableau T, let S be a tree in its trace forest, and c a cell in S. The two sets C_{<}(c, S) and C_{∨}(c, S) are in disjoint sets of trees in the trace forest of T^{c}.

Proof. We only need to show that there is no no arc between elements in C_{<}(c, S) and C_{∨}(c, S) in the trace forest of T^{c}. We will first prove that there is no arc from C_{<}(c, S) to C_{∨}(c, S) in the trace forest of T^{c}. Let d ∈ C_{<}(c, S), x be the entry of d in T^{c}, d_{1} the cell immediately to the left of d, d_{2} the one below d, and d_{0} the one in the south-west. There are three cases: d ∈ P_{h}(c), d ∈ D_{<}(c), and d ∈ R(c).

For d ∈ P_{h}(c) and d ∈ R(c), the only possible way that d_{1} ∈ C_{∨}(c, S) is the case where d_{1} ∈ P_{v}(c). For d ∈ D_{<}(c), it suffices to look at the root d = r_{1} of D_{<}(c). The only possibility that d_{1} ∈ C_{∨}(c, S) is that we still have d_{1} ∈ P_{v}(c). Therefore, in all three cases, the arc of d_{1} points to d_{0} in F.

Let y be the entry in d_{1} and z in d_{2} in T^{c}. By definition of P_{v}(c), d_{0} contains y in T. This implies y < z by the definition of skew tableau. Therefore, in T^{c}, the arc from d points to d_{2} according to the rule of jeu de taquin, and we have the desired separation. The right side of Figure 6 illustrates this argument.

The proof that there is no arc from C_{∨}(c, S) to C_{<}(c, S) in the trace forest of T^{c} is similar. □

We have the following corollary when T is a standard tableau.

Corollary 3.3. For a standard tableau T of shape λ, let r be the first cell of the first row, and c an arbitrary cell. We perform jeu de taquin on the entry in c to obtain a skew tableau of shape λ/(1). Let F_{<} and F_{∨} be the two trees of the trace forest of T^{c} rooted at r_{<} and r_{∨}, respectively. The set of cells in F_{<} (respectively F_{∨}) is exactly C_{<}(c, S) (respectively C_{∨}(c, S)), and, when we perform an incoming slide for the entry in one of the cells in C_{<}(c, S) (respectively C_{∨}(c, S), it must end in r_{<} (respectively r_{∨}).

Proof. Since the trace forest of T^{c} has only two trees, and C_{<}(c, S), C_{∨}(c, S) partition cells in T^{c}, we know that C_{<}(c, S), C_{∨}(c, S) must each consist of all the cells in the tree F_{<} or the tree F_{∨}. Since a_{<} is both in F_{<} and C_{<}(c, S), the claim follows. □

Lemma 3.2 can be seen as a clarification of an argument in Lemma HC^{∗} in [Kra99]. Using Lemma 3.2, we have the following simple bijective proof of a well-known character formula (cf. [Ing50, CGS04, Las08]). To the author’s knowledge, no purely bijective proof was known before for this simple formula.

Theorem 3.4. For a partition λ ⊢ n, we have

n(n − 1)χ_{2,1^{n−2}}^{λ} = 2f^{λ} ∑_{w∈λ} c(w).

Proof. Since, from Lemma 2.1, it follows that χ_{2,1^{n−2}}^{λ} = f^{λ/(2)} −f^{λ/(1,1)}, we want to count the difference between the number of skew tableaux of shape λ/(2) and those of shape λ/(1, 1).

Let (T, e_{1}, e_{2}) be a tuple with T a standard tableau of shape λ and e_{1} ≠ e_{2} two entries in T. We let ST (T, e_{1}, e_{2}) denote the skew tableau T_{0} such that (T, e_{1}, e_{2}) is associated with (μ, T_{0}, T_{1}, e_{1}, e_{2}) in the bijection in Lemma 2.2, in which μ can only be either (2) or (1, 1), and T_{1} is fixed by μ in our case. Therefore, when going through all (T, e_{1}, e_{2}), then ST (T, e_{1}, e_{2}) “hits” each skew tableau of shape either λ/(2) or λ/(1, 1) exactly n(n − 1) times.

For entries e_{1}, e_{2} with e_{1} < e_{2}, we consider the contribution of ST (T, e_{1}, e_{2}) and ST (T, e_{2}, e_{1}) to f^{λ/(2)} − f^{λ/(1,1)}. There are two cases for e_{1}, e_{2}, either one of their cells is an ancestor of the other or not, and we will show that only the “ancestor case” has a nonzero total contribution that can be computed explicitly. Let c_{1} and c_{2} be the cells containing e_{1} and e_{2} in T, respectively, and let F be the trace forest of T.

If c_{1} is not an ancestor of c_{2} in F, the two cells have a common ancestor c, and by symmetry we can suppose that c_{2} is in the subtree rooted in c_{∨}, while c_{1} is in the subtree rooted in c_{<}. By definition, in T^{e_{1}}, the cell c_{2} still contains e_{2} and is in A(c_{1}) ⊂ C_{∨}(c_{1}, F), and, in T^{e_{2}}, the cell c_{1} still contains e_{1} and is in R(c_{2}) ⊂ C_{<}(c_{2}, F). From Corollary 3.3, we know that ST (T, e_{1}, e_{2}) is of shape λ/(1, 1), while ST (T, e_{2}, e_{1}) is of shape λ/(2). Thus this case does not contribute to f^{λ/(2)} − f^{λ/(1,1)}.

The other case is that c_{1} is an ancestor of c_{2} in F, and the path in F from c_{2} to c_{1} can end with either a horizontal or a vertical arc. We suppose that the path ends with a horizontal arc. Let c_{1,<} be the cell to the right of c_{1} (thus the right child of c_{1} in T). By the definition of incoming slide, we know that, in T^{e_{2}}, the cell containing e_{1} will be c_{1,<}, while, in T^{e_{1}}, the cell c_{2} still contains e_{2}. We have c_{2} ∈ D_{<}(c_{1}) ⊂ C_{<}(c_{1}, F) in T^{e_{1}} and c_{1,<} ∈ P_{1}(c_{2}) ⊂ C_{<}(c_{2}, F) in T^{e_{2}}. From Corollary 3.3, we infer that ST (T, e_{1}, e_{2}) and ST (T, e_{2}, e_{1}) are both of shape λ/(2). For the case where the path from c_{2} to c_{1} ends with a vertical arc, we infer similarly that ST (T, e_{1}, e_{2}) and ST (T, e_{2}, e_{1}) are both of shape λ/(1, 1).

The path in the trace forest from c_{2} at (i, j) to the cell at (0, 0) consists of i horizontal arcs and j vertical arcs. Therefore, if we sum over all ancestors c_{1} of c_{2}, among all ST (T, e_{1}, e_{2}) and ST (T, e_{2}, e_{1}), we have 2i tableaux of shape λ/(2) and 2j tableaux of shape λ/(1, 1). This yields a contribution of 2c(c_{2}) to f^{λ/(2)} − f^{λ/(1,1)}, which is independent of T.

In the end, we conclude the proof by observing that

n(n − 1)(f^{λ/(2)} − f^{λ/(1,1)}) = 2f^{λ} ∑_{w∈λ} c(w). □

4. Character evaluation using the trace forest

We will now use the notion of trace forest to calculate f^{λ/μ} with fixed small μ. In [CGS04] and [Las08] (see also [KO94]), it was proved that χ_{μ}^{λ} can be expressed using so-called “content evaluation”. By Lemma 2.1, we know that f^{λ/μ} can also be expressed by such content evaluation. It is now interesting to study the interaction between content evaluation and trace forest, and how it applies to character evaluation.

In this section, we will define a notion called the “inductive form” of functions on the set of subtrees in the trace forest. It enables the computation of such functions by identification of the inductive form. Some examples of inductive forms will be given. Then we proceed to the bijective counting of skew tableaux of different shapes using jeu de taquin, and, by identification of the inductive form, we obtain an expression for f^{λ/μ} for general λ and small μ in terms of content evaluation. This provides counting proofs of various character evaluation formulae.

4.1. Content power sums. We will start by defining various content power sums on subtrees of the trace forest of skew-tableaux related to contents.

For a skew tableau T, let S be a subtree in its trace forest and r a cell. We denote by c_{r}(c) the relative content of a cell c with respect to the cell r, i.e., r is taken as the origin when computing the relative content c_{r}(c). We have c_{r}(c) = c(c) − c(r), where c(·) stands for the usual content. For any partition α = (α_{1}, …, α_{l}), we define the content power sum of S, denoted by cp_{r}^{α}(S), as follows, with the convention that 0^{0} = 1:

cp_{r}^{α}(S) = ∏_{i=1}^{l} ∑_{c∈S} c_{r}(c)^{α_{i}−1}.

When r is also the root of S, we omit the r in cp_{r}^{α}(S) and denote the function by cp^{α}(S).

We can also define the function cp^{α} on a partition λ by identifying λ with the set of all cells in the Ferrers diagram of λ, and by using the first cell of the first row as the referential cell r. We notice that, for any standard tableau T of shape λ and F_{T} its only tree in its trace forest, we have cp^{α}(λ) = cp^{α}(F_{T}).

We make the choice of using α_{i} − 1 in the exponent of the power sum because we want to include the size n of the partition λ as cp^{1}(λ). In this way, we can express any polynomial in n and power sums of contents as a linear combination of cp^{α}(λ)’s for various partitions α.

By abuse of notation, given a subset C of cells in T, we define cp_{r}^{α}(C) as the sum ∑_{i} cp_{r}^{α}(F_{i}), where the F_{i}’s are subtrees in the trace forest of T whose disjoint union is C.

We note that the subscript r in cp_{r}^{α} represents the “origin” for the relative contents used in the function. When evaluated over a tree with the root as origin, we will omit the subscript. We notice that cp^{(k)} is the sum of the content power sums of power k − 1.

We will now show that the algebra spanned by the cp_{r}^{α}’s is independent of the choice of r. We recall that, for a cell r in a Ferrers diagram, we denote by r_{<} the cell to its right and by r_{∨} the cell above. We define two linear operators Γ_{+} and Γ_{−} as follows:

Γ_{+}cp_{r}^{(k)} = cp_{r_{<}}^{(k)}, Γ_{−}cp_{r}^{(k)} = cp_{r_{∨}}^{(k)}.

By requiring Γ_{+} and Γ_{−} to be compatible with multiplication, i.e., Γ_{+}(fg) = (Γ_{+}f)(Γ_{+}g) and the same for Γ_{−}, these two operators are thus defined on the algebra generated by the cp_{r}^{α}(S)’s.

Lemma 4.1. For any integer k ≥ 1, the result of application of Γ_{+} and Γ_{−} is given by

Γ_{+}cp_{r}^{(k)} = ∑_{i=1}^{k}(−1)^{k−i}\binom{k − 1}{i − 1}cp_{r}^{(i)}, Γ_{−}cp_{r}^{(k)} = ∑_{i=1}^{k} \binom{k − 1}{i − 1}cp_{r}^{(i)}.

Therefore the algebra spanned by the cp_{r}^{α}’s is invariant under application of Γ_{+} and Γ_{−}. Moreover, Γ_{+}Γ_{−} = Γ_{−}Γ_{+} = id.

Proof. It is a simple observation that, for any cell c and r, we have c_{r_{<}}(c) + 1 = c_{r}(c) = c_{r_{∨}}(c) − 1. This is simply due to the change of origin.

Now, for any subtree S, we have

(Γ_{+}cp_{r}^{(k)})(S) = ∑_{c∈S} c_{r_{<}}^{k−1}(c) = ∑_{c∈S}(c_{r}(c) − 1)^{k−1} = ∑_{i=1}^{k}(−1)^{k−i}\binom{k − 1}{i − 1}cp_{r}^{(i)}(S)

and

(Γ_{−}cp_{r}^{(k)})(S) = ∑_{c∈S} c_{r_{∨}}^{k−1}(c) = ∑_{c∈C}(c_{r}(c) + 1)^{k−1} = ∑_{i=1}^{k} \binom{k − 1}{i − 1}cp_{r}^{(i)}(S).

For establishing Γ_{+}Γ_{−} = Γ_{−}Γ_{+} = id, we only need to notice that c_{(r_{<})_{∨}}(c) = c_{r}(c) = c_{(r_{∨})_{<}}(c) for any cell c. □

Therefore, for any choice of r, the algebra spanned by the cp_{r}^{α}’s is the same. We denote this algebra formed by real-valued functions over subtrees in the trace forests of skew tableaux by Λ. We notice that, when restricted to a partition λ, a function f ∈ Λ is a shifted symmetric function (cf. [CGS04, KO94]) evaluated at the parts λ_{i} of λ. Conversely, for any shifted symmetric function s_{μ}^{∗}, there is a function f ∈ Λ such that s_{μ}^{∗}(λ_{1}, λ_{2}, …) = f(λ) for any partition λ. Therefore, the algebra Λ is isomorphic to the algebra of shifted symmetric functions.

4.2. Content evaluation and inductive form. We start with some definitions. For S a subtree of a trace forest rooted at r, we write S_{<} and S_{∨} for the subtrees rooted at r_{<} and r_{∨}, respectively (if they exist, otherwise they are defined to be the empty tree). For a partition α ⊢ k, we introduce the notations <^{(α)} (S) (respectively ∨^{(α)}(S)) by

<^{(α)} (S) = cp_{r}^{α}(S_{<}), ∨^{(α)}(S) = cp_{r}^{α}(S_{∨}).

We now define a transformation called inductive form. Let f be a real-valued function on subtrees of a trace forest. Its inductive form Δf is defined by (Δf)(∅) = 0 and (Δf)(S) = f(S) − f(S_{<}) − f(S_{∨}) for any non-empty subtree S. The transformation Δ is clearly linear.

Lemma 4.2. Let f and g be two functions on subtrees of trace forests. If f(∅) = g(∅) and Δf = Δg, then we have f = g.

Proof. Since Δ is linear, for any S, we have (f − g)(S) = (f − g)(S_{<}) + (f − g)(S_{∨}). The proof is then completed by an induction on the size of the tree S. □

We now prove that the inductive form of cp^{α} can be explicitly expressed as a polynomial of <^{(k)} and ∨^{(k)}. These expressions, combined with Lemma 4.2, will be used to recover content power sums from their inductive form.

Proposition 4.3. For any non-empty subtree S in a trace forest and any integer k > 1, we have

(4.1)  cp^{(1)}(S) = 1+ <^{(1)}(S) + ∨^{(1)}(S);  cp^{(k)}(S) =<^{(k)}(S) + ∨^{(k)}(S);
(4.2)  cp^{(k)}(S_{<}) = ∑_{i=0}^{k−1}(−1)^{i}\binom{k − 1}{i} <^{(k−i)}(S); cp^{(k)}(S_{∨}) = ∑_{i=0}^{k−1} \binom{k − 1}{i} ∨^{(k−i)} (S).

Furthermore, for any partition α, Δcp^{α} can be expressed as a polynomial in <^{(k)} and ∨^{(k)}.

Proof. The equalities in (4.1) come directly from the definition of cp^{(k)}. For establishing those in (4.2), we notice that cp^{(k)}(S_{<}) is rooted at r_{<}, thus we have cp^{(k)}(S_{<}) = (Γ_{+}cp_{r}^{(k)})(S_{<}), and we conclude by Lemma 4.1. For cp^{(k)}(S_{∨}) we similarly have cp^{(k)}(S_{∨}) = (Γ_{−}cp_{r}^{(k)})(S_{∨}).

By (4.1) and (4.2), for any subtree S of a trace forest, we can express cp^{α}(S), cp^{α}(S_{<}), and cp^{α}(S_{∨}) as polynomials in <^{(k)}(S) and ∨^{(k)}(S). The fact that (Δcp^{α})(S) = cp^{α}(S) − cp^{α}(S_{<}) − cp^{α}(S_{∨}) then completes the proof. □

Here are some examples of the inductive form of some cp^{α}’s; for simplicity, we consider cp^{α}, <^{(α)}, ∨^{(α)} as functions and omit their arguments:

Δcp^{(1)} = 1; Δcp^{(2)} =<^{(1)} −∨^{(1)}; Δcp^{(1,1)} = 2 <^{(1)} ∨^{(1)} + 2 <^{(1)} +2 ∨^{(1)} +1;
Δcp^{(3)} = 2 <^{(2)} −2 ∨^{(2)} − <^{(1)} −∨^{(1)};
Δcp^{(2,1)} =<^{(2)} ∨^{(1)}+ <^{(1)} ∨^{(2)}+ <^{(2)} + ∨^{(2)} + <^{(1,1)} −∨^{(1,1)};
Δcp^{(1,1,1)} = 3 <^{(1,1)} ∨^{(1)} + 3 <^{(1)} ∨^{(1,1)} + 3 <^{(1,1)} +6 <^{(1)} ∨^{(1)} + 3 ∨^{(1,1)} +3 <^{(1)} +3 ∨^{(1)} +1.

4.3. Inductive counting of skew tableaux. It is now natural to try to count skew tableaux of different shapes using induction. For integers n, k ≥ 0, we define the falling factorial (n)_{k} = n(n − 1) ⋯ (n − k + 1). Evidently, the number of k-tuples of distinct elements from {1, 2, …, n} is exactly (n)_{k}. Given a standard tableau of shape λ and a small partition μ, we now try to inductively count the number of tuples that lead to a skew tableau of shape λ/μ using the bijection in Lemma 2.2.

We now describe a general scheme for computing such quantities. We will first recursively define a family of functions G_{(k)} on the set of subtrees of a standard tableau T that will be related to f^{λ/(k)}. The definition of G_{(k)}(S) for a subtree S is essentially a sum over all cells c ∈ S of a certain evaluation involving G_{(k−1)}, and we want to compute this sum. This is done inductively for all subtrees in the trace forest of T. For such a subtree S rooted at r, instead of computing directly the sum we want, we try to find out the inductive form of that sum. The idea is that the sum over c ∈ S splits into three cases: c = r, c ∈ S_{<}, and c ∈ S_{∨}. The first case is readily expressed as content evaluation for S_{<} and S_{∨}, and the latter two cases consist of a sum of the same type we are computing. They can, hopefully, also be reduced to some content evaluation for S_{<} and S_{∨}. We thus obtain the inductive form, and by comparing those of cp^{α}, we can identify the sum as a linear combination of content evaluations of S, thus proving that G_{(k)} is in fact in Λ, and that f^{λ/(k)} can be expressed in terms of content power sums.

Before proceeding to examples of application of our scheme, we first present some definitions and facts we need. The conjugate of a partition λ, denoted by λ^{†}, is the partition whose Ferrers diagram is that of λ flipped alongside the line y = x.

Lemma 4.4. For a skew tableau T, a subtree S in its trace forest rooted in r, and c ∈ S, we have the following three cases:

• c = r. In this case, C_{<}(r, S) = S_{<} and C_{∨}(r, S) = S_{∨}.

• c ∈ S_{<}. In this case, C_{<}(c, S) = C_{<}(c, S_{<}) ∪ {r_{<}} and C_{∨}(c, S) = C_{∨}(c, S_{<}) ∪ S_{∨}.

• c ∈ S_{∨}. In this case, C_{<}(c, S) = C_{<}(c, S_{∨}) ∪ S_{<} and C_{∨}(c, S) = C_{∨}(c, S_{∨}) ∪ {r_{∨}}.

Proof. The case c = r is trivial. We now analyse the case where c ∈ S_{<}. The case where c ∈ S_{∨} can be treated similarly.

If c ∈ S_{<}, the common ancestor of any cell in S_{∨} and c is the root r, thus S_{∨} ⊂ A(c) ⊂ C_{∨}(c, S). Now we only need to consider the cells in S_{<}. By definition, we know that {r_{<}}, C_{<}(c, S_{<}), and C_{∨}(c, S_{<}) is a partition of the set S_{<}. We already know that r_{<} ∈ C_{<}(c, S) by definition. Also, by definition, we have C_{<}(c, S_{<}) ⊂ C_{<}(c, S) and C_{∨}(c, S_{<}) ⊂ C_{∨}(c, S). This finishes the proof. □

Since we will evaluate functions in Λ on disjoint union of sets, we need the following proposition to “decompose” the evaluation.

Proposition 4.5. For a partition α = (α_{1}, …, α_{l}), two disjoint subsets A, B of cells in a tableau T, and r an arbitrary cell in T, we have

cp_{r}^{α}(A ⊎ B) = ∑_{α^{(1)}⊎α^{(2)}=α} (∏_{i≥1} \binom{m(α, i)}{m(α^{(1)}, i)}) cp_{r}^{α^{(1)}}(A)cp_{r}^{α^{(2)}}(B).

Here, ⊎ stands for the union of multisets, and m(α, i) (respectively m(α^{(1)}, 1)) is the multiplicity of i in α (respectively α^{(1)}).

Proof. It follows from the definition of cp_{r}^{(k)} that

cp_{r}^{α}(A ⊎ B) = ∏_{i=1}^{l} (cp_{r}^{(α_{i})}(A) + cp_{r}^{(α_{i})}(B))

= ∑_{α^{(1)}⊎α^{(2)}=α} (∏_{i≥1} \binom{m(α, i)}{m(α^{(1)}, i)}) cp_{r}^{α^{(1)}}(A)cp_{r}^{α^{(2)}}(B).  □

We will now investigate some relations on partitions that enable us to simplify some calculations.

Proposition 4.6. For a partition μ, let P (μ) be the set of partitions whose Ferrers diagram can be obtained by adding a cell to that of μ. For any partition λ, we have f^{λ/μ} = ∑_{μ′∈P (μ)} f^{λ/μ′}.

Proof. This follows from the classification of all skew tableaux of shape λ/μ by the cell containing 1. □

Proposition 4.7. For a partition μ and its conjugate μ^{†}, let F be a function such that, for any λ, we have

(|λ|)_{(|μ|)}f^{λ/μ}/f^{λ} = F (cp^{(1)}(λ), cp^{(2)}(λ), …, cp^{(i)}(λ), …).

Then we have

(|λ|)_{(|μ^{†}|)}f^{λ/μ^{†}}/f^{λ} = F (cp^{(1)}(λ), −cp^{(2)}(λ), …, (−1)^{i−1}cp^{(i)}(λ), …).

Proof. By flipping skew tableaux alongside y = x, we see that f^{λ/μ^{†}} = f^{λ^{†}/μ}. The claim then follows by observing that cp^{(k)}(λ) = (−1)^{k−1}cp^{(k)}(λ^{†}). □

We now recursively define a family of functions G_{(k)} on sets of cells that will be related to f^{λ/(k)} as follows. Let T be a skew tableau and d a cell in T. We first impose the unconnected additivity of G_{(k)}, that is, for any disjoint sets of cells A, B in T that are not connected in the trace forest of T, we have

G_{(k)}(A ⊎ B, d) = G_{(k)}(A, d) + G_{(k)}(B, d).

We then recursively define the function G_{(k)} on subtrees S in the trace forest of T by

G_{(1)}(S, d) = cp_{d}^{(1)}(S) = |S|, G_{(k)}(S, d) = ∑_{c∈S} G_{(k−1)}(C_{<}(c, S), d_{<}) for k ≥ 2.

By abuse of notation, when d is also the root of the subtree S, we omit d in G_{(k)}(S, d), and only write G_{(k)}(S). The referential point d may seem pointless since the function G_{(k)}(S, d) in the recursive definition does not depend on d. However, the referential point becomes important for repositioning when computing G_{(k)}(S), since in this case we need to reposition every term to the root of S. Therefore, although seemingly pointless at first, we decide to keep it for the clarity of later calculations. The definition of G_{(k)} seems to depend on the skew tableau T, but, in later applications, we always fix such T and then prove that G_{(k)} belongs to Λ and does not really depend on T.

This family of functions is closely related to the number of skew tableaux of the form λ/(k) by the following proposition.

Proposition 4.8. For a partition λ, a standard tableau T of shape λ and F the only tree in its trace forest, let r be the root of F. Then G_{(k)}(F) equals the number of tuples (e_{1}, e_{2}, …, e_{k}) with each e_{i} situated in a cell in S from which, by performing the incoming slide for each e_{i} successively on T, we can obtain a skew tableau of the shape λ/(k).

Proof. We proceed by direct counting of the tuples satisfying our conditions. For such a tuple (e_{1}, e_{2}, …, e_{k}), for 1 ≤ i ≤ k, let T_{i} be the tableau obtained by performing the incoming steps for e_{1}, e_{2}, …, e_{i}, and let T_{0} = T. T_{i} is a skew tableau of shape λ/(i). We should note that each T_{i} depends on the entries e_{1}, e_{2}, …, e_{i}.

The trace forest F_{i} of T_{i} consists of two trees, one rooted at the (i + 1)-st cell r_{i} of the first row, denoted by S_{<,i}, the other rooted at the first cell of the second row, denoted by S_{∨,i}. Let c_{i} be the cell containing e_{i} in T_{i−1}. Since the incoming step of e_{i} turns T_{i−1}, a skew tableau of shape λ/(i − 1), into the skew tableau T_{i} of shape λ/(i), we have c_{i} ∈ S_{<,i−1}. It is clear that S_{∨,i−1} does not intersect S_{<,i} by imagining the standard tableau T_{∗} obtained by filling in entries of smaller values in T_{i−1} and applying Corollary 3.3 to the cell containing e_{1} in T_{∗}. By Lemma 3.2, C_{<}(c_{i}, S_{<,i−1}) is disconnected from C_{∨}(c_{i}, S_{<,i−1}) in F_{i}. We also know that C_{<}(c_{i}, S_{<,i−1}) contains the root of S_{<,i}. Therefore C_{∨}(c_{i}, S_{<,i−1}) does not intersect S_{<,i} either. Since S_{∨,i−1}, C_{<}(c_{i}, S_{<,i−1}), and C_{∨}(c_{i}, S_{<,i−1}) partition the set of cells in T_{i}, we know that C_{<}(c_{i}, S_{<,i−1}) is the set of the cells of the tree S_{<,i}.

We recall that T_{i}, and hence S_{<,i}, depends on e_{1}, e_{2}, …, e_{i}. Let H_{(k,i)}(T, e_{1}, e_{2}, …, e_{i}) be the number of possible choices of e_{i+1}, …, e_{k} when e_{1}, e_{2}, …, e_{i} is fixed. It is clear that H_{k,k−1}(T, e_{1}, …, e_{k−1}) = G_{(1)}(S_{<,k−1}, r_{k−1}). Since S_{<,k−a} = C_{<}(c_{k−a}, S_{<,k−a−1}) in the sense of sets of cells, if H_{k,k−a}(T, e_{1}, …, e_{k−a}) = G_{(a)}(S_{<,k−a}, r_{k−a}), we have

H_{k,k−a−1}(T, e_{1}, …, e_{k−a−1}) = ∑_{c_{k−a}∈S_{<,k−a−1}} H_{k,k−a}(e_{1}, …, e_{k−a})

= ∑_{c_{k−a}∈S_{<,k−a−1}} G_{(a)}(S_{<,k−a}, r_{k−a})

= ∑_{c_{k−a}∈S_{<,k−a−1}} G_{(a)}(C_{<}(c_{k−a}, S_{<,k−a−1}), r_{k−a})

= G_{(a+1)}(S_{<,k−a−1}, r_{k−a−1}).

The proof is completed by an induction on a to obtain H_{(k,0)}(T) = G_{(k)}(S, r). □

With the help of the family G_{(k)}, we can now proceed to examples of computing f^{λ/(k)} with our scheme. We recall that, for a cell r in a trace forest, we denote by r_{<} the cell to the right of r, and by r_{∨} the cell above r.

Proposition 4.9. For a partition λ ⊢ n, we have

(n)_{2}f^{λ/(2)}/f^{λ} = \frac{1}{2}cp^{(1,1)}(λ) + cp^{(2)}(λ) − \frac{1}{2}cp^{(1)}(λ) = n(n − 1)/2 + ∑_{w∈λ} c(w).

Proof. The number (n)_{2}f^{λ/(2)} equals the number of tuples ((2), T′, T′′, e_{1}, e_{2}), where T′ is of shape λ/(2). Therefore, by taking the correspondence in Lemma 2.2, and by Proposition 4.8, writing F_{T} for the trace forest (consisting of one single tree) of the standard tableau T, we have

(n)_{2}f^{λ/(2)} = ∑_{T of shape λ} G_{(2)}(F_{T}).

We now compute G_{(2)}(S) for S rooted at r. We notice that G_{(1)} is in Λ, and that

G_{(2)}(S) = ∑_{c∈S} G_{(1)}(C_{<}(c, S), r_{<}) = ∑_{c∈S}(Γ_{+}cp_{r}^{(1)})(C_{<}(c, S)) = ∑_{c∈S} cp_{r}^{(1)}(C_{<}(c, S)).

We now compute the inductive form of G_{(2)}(S) using Lemma 4.4 and Proposition 4.5:

(ΔG_{(2)})(S) = G_{(2)}(S) − G_{(2)}(S_{<}) − G_{(2)}(S_{∨})

= ∑_{c∈S={r}∪S_{<}∪S_{∨}} cp_{r}^{(1)}(C_{<}(c, S)) − ∑_{c∈S_{<}}(Γ_{+}cp_{r}^{(1)})(C_{<}(c, S_{<}))

− ∑_{c∈S_{∨}}(Γ_{−}cp_{r}^{(1)})(C_{<}(c, S_{∨}))

= cp_{r}^{(1)}(C_{<}(r, S)) + ∑_{c∈S_{<}} (cp_{r}^{(1)}(C_{<}(c, S)) − cp_{r}^{(1)}(C_{<}(c, S_{<})))

+ ∑_{c∈S_{∨}} (cp_{r}^{(1)}(C_{<}(c, S)) − cp_{r}^{(1)}(C_{<}(c, S_{∨}))) .

By the use of Lemma 4.4, the differences in the summand can be computed:

(ΔG_{(2)})(S) = cp_{r}^{(1)}(C_{<}(r, S)) + ∑_{c∈S_{<}} cp_{r}^{(1)}({r_{<}}) + ∑_{c∈S_{∨}} cp_{r}^{(1)}(S_{<})

=<^{(1)}(S) + ∑_{c∈S_{<}} 1 + ∑_{c∈S_{∨}} <^{(1)}(S)

= 2 <^{(1)}(S)+ <^{(1)}(S) ∨^{(1)}(S)

= (Δ (\frac{1}{2}cp^{(1,1)} + cp^{(2)} − \frac{1}{2}cp^{(1)})) (S).

By Lemma 4.2, we have G_{(2)} = \frac{1}{2}cp^{(1,1)} +cp^{(2)} − \frac{1}{2}cp^{(1)} ∈ Λ. We notice that, since G_{(2)} ∈ Λ, for any standard tableau T of shape λ, we have G_{(2)}(F_{T}) = G_{(2)}(λ), which does not depend on T. We thus may finish the proof by combining G_{(2)}(F_{T}) = G_{(2)}(λ) with the sum formula at the beginning of the proof, noticing that there are f^{λ} standard tableaux of shape λ. □

A formula for f^{λ/(1,1)} can be found either by the same approach, or by using Proposition 4.6 applied to μ = (1), or by using Proposition 4.7. Proposition 4.9 implies Theorem 3.4, thus can be viewed as an alternative proof. We have the first evidence that our scheme may work.

We now investigate the next case, μ = (3), to see that our scheme also works in greater generality.

Proposition 4.10. For a partition λ ⊢ n, we have

(n)_{3}f^{λ/(3)}/f^{λ} = \frac{1}{6}cp^{(1,1,1)}(λ) + cp^{(2,1)}(λ) + cp^{(3)}(λ) − cp^{(1,1)}(λ) − 2cp^{(2)}(λ) + \frac{5}{6}cp^{(1)}(λ).

Proof. The number (n)_{3}f^{λ/(3)} equals the number of tuples ((3), T′, T′′, e_{1}, e_{2}, e_{3}), where T′ is of shape λ/(3). Therefore, by using the correspondence in Lemma 2.2, and by Proposition 4.8, writing F_{T} for the trace forest (consisting of one single tree) of the standard tableau T, we have

(n)_{3}f^{λ/(3)} = ∑_{T of shape λ} G_{(3)}(F_{T}).

We now compute G_{(3)}(S) for S rooted at r. By the proof of Proposition 4.9, we see that G_{(2)} is in Λ. Furthermore, by the definition of G_{(3)}(S), we have

G_{(3)}(S) = ∑_{c∈S} G_{(2)}(C_{<}(c, S), r_{<}) = ∑_{c∈S} (Γ_{+} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{1}{2}cp_{r}^{(1)})) (C_{<}(c, S))

= ∑_{c∈S} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)}) (C_{<}(c, S)).

We now compute the inductive form of G_{(3)} using Lemma 4.4 and Proposition 4.5:

(ΔG_{(3)})(S) = ∑_{c∈S} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)}) (C_{<}(c, S))

− ∑_{c∈S_{<}} (Γ_{+} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)})) (C_{<}(c, S_{<}))

− ∑_{c∈S_{∨}} (Γ_{−} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)})) (C_{<}(c, S_{∨}))

= ∑_{c∈S} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)}) (C_{<}(c, S))

− ∑_{c∈S_{<}} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{5}{2}cp_{r}^{(1)}) (C_{<}(c, S_{<}))

− ∑_{c∈S_{∨}} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{1}{2}cp_{r}^{(1)}) (C_{<}(c, S_{∨})).

By Lemma 4.4, the differences can be simplified by splitting the first sum into three parts: c = r, c ∈ S_{<}, and c ∈ S_{∨}. We notice that, by Proposition 4.5, for two disjoint sets of cells A and B, we have cp_{r}^{(1,1)}(A ⊎ B) = cp_{r}^{(1,1)}(A) + 2cp_{r}^{(1)}(A) + cp_{r}^{(1,1)}(B). Hence,

(ΔG_{(3)})(S) = (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)}) (S_{<}) + ∑_{c∈S_{<}} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)}) (\{r_{<}\})

+ (cp_{r}^{(1)}({r_{<}}) + 1) ∑_{c∈S_{<}} cp_{r}^{(1)}(C_{<}(c, S_{<}))

+ ∑_{c∈S_{∨}} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)}) (S_{<})

+ (cp_{r}^{(1)}(S_{<}) − 1) ∑_{c∈S_{∨}} cp_{r}^{(1)}(C_{<}(c, S_{∨})).

We know from the definition of G_{(2)} that G_{(2)}(S) = ∑_{c∈S} cp_{r}^{(1)}(C_{<}(c, S)), and from the definition of cp_{r}^{(1)} and Lemma 4.1 that cp_{r}^{(1)}(S) = cp_{r_{<}}^{(1)}(S) = cp_{r_{∨}}^{(1)}(S) = |S|. These facts, combined with the expression of G_{(2)}(S) in Proposition 4.9, yield

(ΔG_{(3)})(S) = \frac{1}{2} <^{(1,1)}(S)+ <^{(2)}(S) − \frac{3}{2} <^{(1)}(S) + 2G_{(2)}(S_{<})

+ ∨^{(1)}(S) (\frac{1}{2} <^{(1,1)}(S)+ <^{(2)}(S) − \frac{3}{2} <^{(1)}(S)) + (<^{(1)}(S) − 1)G_{(2)}(S_{∨}).

We now compute G_{(2)}(S_{<}) and G_{(2)}(S_{∨}). Since the root of S_{<} is r_{<}, we have

G_{(2)}(S_{<}) = (\frac{1}{2}cp_{r_{<}}^{(1,1)} + cp_{r_{<}}^{(2)} − \frac{1}{2}cp_{r_{<}}^{(1)}) (S_{<}) = (Γ_{+} (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{1}{2}cp_{r}^{(1)})) (S_{<})

= (\frac{1}{2}cp_{r}^{(1,1)} + cp_{r}^{(2)} − \frac{3}{2}cp_{r}^{(1)}) (S_{<}) = \frac{1}{2} <^{(1,1)}(S)+ <^{(2)}(S) − \frac{3}{2} <^{(1)}(S).

Similarly, we have G_{(2)}(S_{∨}) = \frac{1}{2} ∨^{(1,1)}(S)+∨^{(2)}(S)+ \frac{1}{2} ∨^{(1)}(S). By substituting both expression back into the computation of (ΔG_{(3)})(S), we obtain

(ΔG_{(3)})(S) = \frac{1}{2} <^{(1,1)}(S) ∨^{(1)}(S) + \frac{1}{2} <^{(1)}(S) ∨^{(1,1)}(S)+ <^{(2)}(S) ∨^{(1)}(S)+ <^{(1)}(S) ∨^{(2)}(S)

− <^{(1)}(S) ∨^{(1)}(S) + 3 <^{(2)}(S) − ∨^{(2)}(S) + \frac{3}{2} <^{(1,1)}(S) − \frac{1}{2} ∨^{(1,1)}(S) − \frac{9}{2} <^{(1)}(S)

− \frac{1}{2} ∨^{(1)}(S)

= (Δ (\frac{1}{6}cp^{(1,1,1)} + cp^{(2,1)} + cp^{(3)} − cp^{(1,1)} − 2cp^{(2)} + \frac{5}{6}cp^{(1)})) (S)

By Lemma 4.2, we have G_{(3)} = \frac{1}{6}cp^{(1,1,1)} + cp^{(2,1)} + cp^{(3)} − cp^{(1,1)} − 2cp^{(2)} + \frac{5}{6}cp^{(1)} ∈ Λ. Therefore, for any standard tableau T of shape λ, we have G_{(3)}(F_{T}) = G_{(3)}(λ), which is independent of T. We then apply this fact and the expression of G_{(3)} in cp^{α} to the sum formula of (n)_{3}f^{λ/(3)} at the beginning of the proof to complete the proof. □

Combining this proposition with Propositions 4.6 and 4.9, we are also able to compute f^{λ/(2,1)} and f^{λ/(1,1,1)}, and we obtain the character evaluated at a 3-cycle for λ ⊢ n:

\frac{(n)_{3}}{f^{λ}} χ_{(3,1^{n−3})}^{λ} = 3cp^{(3)}(λ) − \frac{3}{2}cp^{(1,1)}(λ) + \frac{3}{2}cp^{(1)}(λ) = 3 ∑_{w∈λ}(c(w))^{2} − 3\binom{n}{2}.

Thus, we have another example of a bijective proof of a character evaluation formula given by our scheme.

Still following our scheme, with the help of some more tedious computation which can be automatized, we obtain the following result for f^{λ/(4)}.

Proposition 4.11. For a partition λ ⊢ n,

(n)_{4}f^{λ/(4)}/f^{λ} = \frac{1}{24}cp^{(1,1,1,1)}(λ) + \frac{1}{2}cp^{(2,1,1)}(λ) + \frac{1}{2}cp^{(2,2)}(λ) + cp^{(3,1)}(λ) + cp^{(4)}(λ)

− \frac{3}{4}cp^{(1,1,1)}(λ) − \frac{9}{2}cp^{(2,1)}(λ) − \frac{9}{2}cp^{(3)}(λ) + \frac{71}{24}cp^{(1,1)}(λ) + 6cp^{(2)}(λ) − \frac{9}{4}cp^{(1)}(λ).

Here we omit the proof, which is essentially a long (but automatic) computation of the inductive form of G_{(4)}. Using Proposition 4.7, we also obtain an expression for f^{λ/(1,1,1,1)}, and, by Proposition 4.6 applied to μ = (3) and μ = (1, 1, 1), we obtain expressions for f^{λ/(3,1)} and f^{λ/(2,1,1)}. We can thus compute χ_{(4,1^{n−4})}^{λ} using Lemma 2.1. The corresponding formula reads

(n)_{4}χ_{(4,1^{n−4})}^{λ}/f^{λ} = 4 ∑_{w∈λ}(c(w))^{3} + 4(2n − 3) ∑_{w∈λ} c(w).

Our proof of this character evaluation formula is indeed a counting proof in line with general idea of the present article. Furthermore, since we are also able to compute f^{λ/(2,2)} using Proposition 4.6, we can also obtain a counting proof for the character χ_{(2,2,1^{n−4})}^{λ}. We remark that our proofs above never depend on the precise structure of the trace forest F_{T}, but rather on the fact that it is a binary tree.

5. Discussion

In this article, using the notion of “trace forest” which reflects a fine structure in the famous jeu de taquin, we gave a simple bijective proof of Theorem 3.4 through counting skew tableaux of different shapes. Inspired by this simple proof, we sketched a scheme for counting skew tableaux of more general shapes in an elementary way, using induction on the trace forest, and this scheme also led to combinatorial proofs of several more sophisticated character evaluation formulae.

We would like to extend the range of application of our scheme. Empirically, our scheme seems to work for f^{λ/μ} for μ a hook. We conjecture that, in that case, our scheme will indeed always give a combinatorial proof for formulae for f^{λ/μ} of the type discussed in this article.

One of the difficulties of extension is that, for a general partition μ, the corresponding function G_{μ} cannot always be so easily defined as in the case μ = (k) we treated here. However, for μ a hook, it seems to be possible to define G_{μ} by supposing that, in the successive incoming slides, the arm of μ is formed before the leg. However, for general μ, the precise definition of G_{μ} should depend on the exact ordering of cells that are excluded from the tableau in successive incoming slides, in other words, the tableau T_{0} in the bijection of Lemma 2.2. Xiaomei Chen observed that, even for the hook μ = (3, 1), for a certain standard tableau T, the number of tuples (T, a_{1}, a_{2}, a_{3}, a_{4}) corresponding to T_{0} is not invariant under the choice of T_{0}. Therefore, the choice of order in the definition of G_{μ} is important.

However, there is another difficulty in obtaining any generic result, even in the case where μ = (k). In the computation of the inductive form, we have to deal with a certain kind of sums over a ∈ F_{<} and a ∈ F_{∨}, but there is no guarantee that these sums can be expressed in terms of <^{(k)} and ∨^{(k)}. To obtain a more general statement, a further study of the action of the difference operator Δ on elements of Λ seems necessary.

When passing from f^{λ/μ} to χ_{μ,1^{n−k}}^{λ}, we notice that χ_{μ,1^{n−k}}^{λ} often has a much simpler form, due to some cancellations in the sum. Thus it might be easier to directly deal with the inductive form of characters, and we might see the combinatorial reason behind.

Acknowledgement

The author is grateful for the invaluable comments from anonymous reviewers that significantly improved this paper. The author also thanks Xiaomei Chen for pointing out that, for some standard tableau T, the number of tuples (T, a_{1}, a_{2}, a_{3}, a_{4}) corresponding to T_{0} of shape (3, 1) varies for different choices of T_{0}.

References

[CGS04] Sylvie Corteel, Alain Goupil, and Gilles Schaeffer. Content evaluation and class symmetric functions. Adv. Math., 188(2):315–336, 2004.

[DG89] Persi Diaconis and Curtis Greene. Applications of Murphy’s elements. Technical report, Department of statistics, Stanford University, 1989.

[Fro01] Georg Frobenius. Über die Charaktere der symmetrischen Gruppe. Berliner Berichte, 1901.

[GJ08] Ian P. Goulden and David M. Jackson. The KP hierarchy, branched covers, and triangulations. Adv. Math., 219(3):932–951, 2008.

[Ing50] Richard E. Ingram. Some characters of the symmetric group. Proc. Amer. Math. Soc., 1:358–369, 1950.

[KO94] Sergey Kerov and Grigori I. Olshanski. Polynomial functions on the set of Young diagrams. C. R. Acad. Sci. Paris Sér. I Math., 319(2):121–126, 1994.

[Kra99] Christian Krattenthaler. Another involution principle-free bijective proof of Stanley’s hook-content formula. J. Combin. Theory Ser. A, 88(1):66–92, 1999.

[Las08] Michel Lassalle. An explicit formula for the characters of the symmetric group. Math. Ann., 340(2):383–405, 2008.

[OO97] Andrei Yu. Okounkov and Grigori I. Olshanskii. Shifted Schur functions. Algebra i Analiz, 9(2):73– 146, 1997.

[Sag01] Bruce E. Sagan. The symmetric group, volume 203 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2001.

[Ser77] Jean-Pierre Serre. Linear representations of finite groups. Springer-Verlag, New York, 1977. Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42.

[Sta99] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[VO04] Anatoly M. Vershik and Andrei Yu. Okounkov. A new approach to representation theory of symmetric groups. II. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 307 (Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 10):57–98, 281, 2004.

LIAFA, Université Paris Diderot - Paris 7