\documentclass[12pt]{amsart}

\usepackage[latin1]{inputenc}
\usepackage{subfigure}
\usepackage{tikz}
\usepackage{multicol}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[headings]{fullpage}

\numberwithin{equation}{section}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{coro}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\theoremstyle{definition}
\newtheorem{defi}[thm]{Definition}

\newcommand{\mysqr}[1]{rectangle +(0.5,0.5) +(0.25,0.25) node{#1}}
\newcommand{\mycpr}[1]{<^{(#1)}}
\newcommand{\mycpa}[1]{\vee^{(#1)}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\mydeg}{\operatorname{deg}}


\begin{document}

\author{Wenjie Fang} 

\address{LIAFA, Universit\'e Paris Diderot - Paris 7}

\title[Bijective proofs of character evaluations]{Bijective proofs of character evaluations using the trace forest of jeu de taquin}

\date{}

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


\begin{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.
\end{abstract}

\maketitle

\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 72 \rms (2015), Article~B72e\hfill}
\def\thepage{}

\section{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 \cite{frobenius1900charaktere, ingram1950some}, for a partition $\lambda$ of an integer $n$, the following evaluations were given:
\begin{align*}
n (n-1) \chi^{\lambda}_{2,1^{n-2}} &= 2 f^{\lambda} \left( \sum_{w \in \lambda} c(w) \right), \\
n (n-1) (n-2) \chi^{\lambda}_{3,1^{n-3}} &= 3 f^{\lambda} \left( \sum_{w \in \lambda} (c(w))^2 + n (n-1) / 2 \right), \\
n (n-1) (n-2) (n-3) \chi^{\lambda}_{4,1^{n-4}} &= 4 f^{\lambda} \left( \sum_{w \in \lambda} (c(w))^3 + (2n-3) \sum_{w \in \lambda} c(w) \right).
\end{align*}
Here, $\chi^{\lambda}_{\mu}$ is the irreducible character indexed by $\lambda$ evaluated at the conjugacy class indexed by another partition $\mu$ of $n$, $f^{\lambda}$ 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 $\lambda$. We postpone detailed definitions of these notions and related ones to Section~\ref{sec:prelim}. 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 \cite{corteel2004content} for the general case, 
and in \cite{lassalle2008explicit} an explicit formula for $\chi^{\lambda}_{\mu, 1^{n-k}}$ was given, where $\mu$ is a partition of $k$ and $n \geq 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.\ \cite{goulden2008kp}). Therefore, a better understanding of the combinatorial importance of contents would also help us better understand other combinatorial phenomena related to contents.

Such character evaluations in terms of contents are mostly obtained in an algebraic way, either using the Jucys--Murphy elements (e.g., \cite{diaconis1989applications}), or with the help of symmetric functions (e.g., \cite{corteel2004content, lassalle2008explicit}). They are also related to shifted symmetric functions 
evaluated at parts of a partition (e.g., \cite{kerov1994polynomial}). On the other hand, there is a well-developed combinatorial representation theory of the symmetric group (cf.\ \cite{stanley2001enumerative, sagan2001symmetric}), 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\"utzenberger's famous jeu de taquin.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL WENJIE FANG}{\SMALL 
BIJECTIVE PROOFS OF CHARACTER EVALUATIONS}

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~\ref{sec:jdt}, 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 $\chi^{\lambda}_{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~\ref{sec:chara-eval} 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 $\chi^{\lambda}_{3,1^{n-2}}$ and $\chi^{\lambda}_{4,1^{n-2}}$. Further possible development of this scheme is also discussed.

\section{Preliminaries} \label{sec:prelim}

\subsection{Partitions and standard tableaux}

A \emph{partition} $\lambda$ is a finite non-increasing sequence $(\lambda_i)_{i>0}$ of positive integers. We say that $\lambda$ is a partition of $n$ (denoted by $\lambda \vdash n$) if $\sum_{i} \lambda_i = n$. The \emph{Ferrers diagram} (in French convention) of a partition $\lambda$ (also denoted by $\lambda$ by abuse of notation) is the graphical representation of $\lambda$ consisting of left-aligned rows of boxes (also called \emph{cells}), in which the $i$-th row has $\lambda_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 \emph{content} to be $c(w)=i-j$. Figure~\ref{fig:tableau} gives an example of a Ferrers diagram, drawn in French convention, with the content of each cell. 

A \emph{standard tableau} of shape $\lambda \vdash n$ is a filling of the Ferrers diagram of $\lambda$ using integers from $1$ to $n$ such that each number is used exactly once, with increasing rows and columns. Figure~\ref{fig:tableau} also gives an example of a standard tableau. We denote by $f^{\lambda}$ the number of standard tableaux of shape $\lambda$. The number $f^\lambda$ is also the dimension of the irreducible representation of the symmetric group $S_n$ indexed by $\lambda$ (cf.\ \cite{sagan2001symmetric, vershik2004new}).

\begin{figure} 
\begin{multicols}{4}
\centering
\begin{tikzpicture}
\clip (-0.05,-0.05) rectangle (2.55,2.05);
\draw (0,0) \mysqr{0};
\draw (0.5,0) \mysqr{1};
\draw (1,0) \mysqr{2};
\draw (1.5,0) \mysqr{3};
\draw (2,0) \mysqr{4};
\draw (0,0.5) \mysqr{-1};
\draw (0.5,0.5) \mysqr{0};
\draw (1,0.5) \mysqr{1};
\draw (0,1) \mysqr{-2};
\draw (0.5,1) \mysqr{-1};
\draw (1,1) \mysqr{0};
\draw (0,1.5) \mysqr{-3};
\draw (0.5,1.5) \mysqr{-2};
\end{tikzpicture}

(a)

\columnbreak
\begin{tikzpicture}
\clip (-0.05,-0.05) rectangle (2.55,2.05);
\draw (0,0) \mysqr{1};
\draw (0.5,0) \mysqr{2};
\draw (1,0) \mysqr{5};
\draw (1.5,0) \mysqr{9};
\draw (2,0) \mysqr{11};
\draw (0,0.5) \mysqr{3};
\draw (0.5,0.5) \mysqr{7};
\draw (1,0.5) \mysqr{10};
\draw (0,1) \mysqr{4};
\draw (0.5,1) \mysqr{8};
\draw (1,1) \mysqr{13};
\draw (0,1.5) \mysqr{6};
\draw (0.5,1.5) \mysqr{12};
\end{tikzpicture}

(b)

\columnbreak
\begin{tikzpicture}
\clip (-0.05,-0.05) rectangle (2.55,2.05);
\draw (1.5,0) \mysqr{};
\draw (2,0) \mysqr{};
\draw (1,0.5) \mysqr{};
\draw (0,1) \mysqr{};
\draw (0.5,1) \mysqr{};
\draw (1,1) \mysqr{};
\draw (0,1.5) \mysqr{};
\draw (0.5,1.5) \mysqr{};
\end{tikzpicture}

(c)

\columnbreak
\begin{tikzpicture}
\clip (-0.05,-0.05) rectangle (2.55,2.05);
\draw (1.5,0) \mysqr{4};
\draw (2,0) \mysqr{6};
\draw (1,0.5) \mysqr{5};
\draw (0,1) \mysqr{1};
\draw (0.5,1) \mysqr{3};
\draw (1,1) \mysqr{8};
\draw (0,1.5) \mysqr{2};
\draw (0.5,1.5) \mysqr{7};
\end{tikzpicture}

(d)
\end{multicols}
\caption{(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)$.\label{fig:tableau}} 
\end{figure}

The definitions above can be generalized to so-called skew-partitions. A \emph{skew-partition} $\lambda/\mu$ is a pair of partitions $(\lambda, \mu)$ such that, for all $i>0$, we have $\lambda_i \geq \mu_i$. Graphically, this inequality condition is equivalent to the condition that the Ferrers diagram of $\lambda$ totally covers that of $\mu$. We then define the \emph{skew diagram} of shape $\lambda/\mu$ as the (set-theoretic) difference of the Ferrers diagrams of $\lambda$ and of~$\mu$, i.e., the Ferrers diagram of $\lambda$ without cells that also appear in that of $\mu$. Figure~\ref{fig:tableau} gives an example of a skew diagram.

We now define the counterpart of standard tableau for skew diagrams. A \emph{skew tableau} of shape $\lambda/\mu$ is a filling of the skew diagram of $\lambda/\mu$ that satisfies all conditions of standard tableaux. Figure~\ref{fig:tableau} gives an example of a skew tableau. We denote the number of skew tableaux of shape $\lambda/\mu$ by $f^{\lambda/\mu}$.

Standard tableaux and skew tableaux are classical combinatorial objects closely related to the representation theory of the symmetric group. In \cite{vershik2004new, sagan2001symmetric, stanley2001enumerative}, details of this relationship are described.

\subsection{Ribbon tableaux and the Murnaghan--Nakayama rule}

We denote by $S_n$ the symmetric group formed by permutations of $n$ elements. For partitions $\lambda,\mu$ of $n$, we denote the \emph{irreducible character} of $S_n$ indexed by $\lambda$ evaluated at the conjugacy class indexed by $\mu$ by $\chi^{\lambda}_{\mu}$.

Irreducible characters can be expressed in a combinatorial way using so-called ribbon tableaux. A \emph{ribbon} is a special skew diagram that is connected and has no $2 \times 2$ block of cells. The \emph{height} $ht(\lambda/\mu)$ of a ribbon $\lambda/\mu$ is the number of rows it spans minus one. A \emph{ribbon tableau} $T$ of shape $\lambda$ is a sequence of partitions $\varnothing = \lambda^{(0)}, \lambda^{(1)}, \ldots, \lambda^{(k)} = \lambda$ such that $\lambda^{(i)} / \lambda^{(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 $\lambda$, where cells in $\lambda^{(i)} / \lambda^{(i-1)}$ are filled with entry $i$. The \emph{entry sequence} of $T$ is $(a_1, a_2, \ldots, a_k)$, with $a_i$ the number of cells in $\lambda^{(i)} / \lambda^{(i-1)}$. The total height of $T$ is defined by $ht(T)=\sum_i ht(\lambda^{(i)} / \lambda^{(i-1)})$, and the sign of $T$ is defined by $\sgn(T)=(-1)^{ht(T)}$. Figure~\ref{fig:ribbon-tableau} gives an example of a ribbon and a ribbon tableau. 

\begin{figure}
\begin{multicols}{2}
\centering
\begin{tikzpicture}
\clip (-0.05,-0.05) rectangle (2.55,2.05);
\draw (1.5,0) \mysqr{};
\draw (2,0) \mysqr{};
\draw (1.5,0.5) \mysqr{};
\draw (1.5,1) \mysqr{};
\draw (1,1) \mysqr{};
\draw (0.5,1) \mysqr{};
\end{tikzpicture}

(a)

\columnbreak
\begin{tikzpicture}
\clip (-0.05,-0.05) rectangle (2.55,2.05);
\draw (0,0) -- (2,0) -- (2,0.5) -- (0.5,0.5) -- (0.5,1) -- (0,1) -- cycle;
\path (0.25,0.25) node {1};
\path (0.75,0.25) node {1};
\path (1.25,0.25) node {1};
\path (1.75,0.25) node {1};
\path (0.25,0.75) node {1};
\draw (0.5,0.5) -- (1,0.5) -- (1,1.5) -- (0.5,1.5) -- (0.5,2) -- (0,2) -- (0,1) -- (0.5,1) -- cycle;
\path (0.75,0.75) node {2};
\path (0.75,1.25) node {2};
\path (0.25,1.25) node {2};
\path (0.25,1.75) node {2};
\draw (1,0.5) -- (1.5,0.5) -- (1.5,1.5) -- (1,1.5) -- cycle;
\path (1.25,0.75) node {3};
\path (1.25,1.25) node {3};
\draw (2,0) -- (2.5,0) -- (2.5,0.5) -- (2,0.5) -- cycle;
\path (2.25,0.25) node {4};
\draw (0.5,1.5) -- (1,1.5) -- (1,2) -- (0.5,2) -- cycle;
\path (0.75,1.75) node {5};
\end{tikzpicture}

(b)

\columnbreak

\end{multicols}
\caption{(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 $\protect\sgn(T)=1$.\label{fig:ribbon-tableau}} 
\end{figure}

The Murnaghan--Nakayama rule (cf.\ Chapter~7.17 of \cite{stanley2001enumerative}) provides a combinatorial interpretation of the irreducible characters. According to this rule, we have $\chi^{\lambda}_{\mu}=\sum_T \sgn(T)$, where we sum over all ribbon tableau $T$ of shape $\lambda$ and entry sequence $\mu$. For a partition $\mu \vdash k$ and an integer $n > k$, we denote by $\mu, 1^{n-k}$ the partition obtained by padding $\mu$ with $n-k$ parts of size $1$. In this article, for a fixed ``small'' partition $\mu \vdash k$, we are interested in the evaluation of $\chi^{\lambda}_{\mu, 1^{n-k}}$ for arbitrary $\lambda \vdash n$ in terms of contents. According to the Murnaghan--Nakayama rule, this involves ribbon tableaux of shape $\lambda$ and entry sequence $\mu, 1^{n-k}$.

\begin{lem}[cf.\ \cite{corteel2004content}] \label{lem:character-as-skew-tableau}
For partitions $\lambda \vdash n$, $\mu \vdash k$ and $n > k$, we have
\[ \chi^{\lambda}_{\mu, 1^{n-k}} = \sum_{\nu \vdash k} f^{\lambda / \nu} \chi^{\nu}_{\mu}. \]
\end{lem}
\begin{proof}
Let $T_0$ be a ribbon tableaux of shape $\lambda$ and entry sequence $\mu, 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 \setminus T_1$ is a ribbon tableau with entry sequence $\mu$. 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 $\nu$ of $T$, then by each $T_1$ of shape $\lambda / \nu$, and finally by each $T$. The proof is completed by applying the Murnaghan--Nakayama rule.
\end{proof}

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 \cite{serre1977linear}), for all $\lambda \vdash n > k$ and all $\mu \vdash k$, the evaluation of the character $\chi^\lambda_{\mu, 1^{n-k}}$ is equivalent to computing the number of skew tableaux of shape $\lambda / \theta$ for all $\theta \vdash k$. Furthermore, it is already known (cf.\ \cite{kerov1994polynomial} and Theorem 8.1 in \cite{okounkov1997shifted}) that $f^{\lambda / \theta}$ can be expressed in content power sums via shifted Schur functions. It is thus interesting for us to study skew tableaux.

\subsection{Jeu de taquin}

The jeu de taquin is a bijection between skew tableaux of different shapes. It was first introduced by Sch\"utzenberger, and it turned out to be a powerful tool in the combinatorial representation theory of the symmetric group. Its applications include the Sch\"utzenberger involution, the Littlewood--Richardson rule (\textit{c.f} \cite{stanley2001enumerative} for both), and also a bijective proof of Stanley's hook-content formula (cf.\ \cite{krattenthaler1999another}). An introduction to jeu de taquin can be found in Appendix~A of \cite{stanley2001enumerative}.

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 \emph{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~\ref{fig:jeu-de-taquin}. The \emph{out-going step} is similarly defined, by exchange with entries immediately above or to the right. Figure~\ref{fig:jeu-de-taquin} 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 \emph{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.

\begin{figure}
\begin{multicols}{2}
\centering
\begin{tikzpicture}
\draw (0,-0.5) \mysqr{x};
\draw (-0.5,0) \mysqr{y};
\draw (0,0) \mysqr{*};

\draw (2.5,0.25) \mysqr{*};
\draw (2,0.75) \mysqr{y};
\draw (2.5,0.75) \mysqr{x};

\draw (2.5,-1.25) \mysqr{x};
\draw (2,-0.75) \mysqr{*};
\draw (2.5,-0.75) \mysqr{y};

\draw[-latex] (0.6, 0) -- (1.9, 0.75) node[midway, above, sloped] {\small $x \geq y$};
\draw[-latex] (0.6, 0) -- (1.9, -0.75) node[midway, below, sloped] {\small $x<y$};

\draw (0,-1.05) node {(a)};
\end{tikzpicture}

\begin{tikzpicture}
\draw (0,-0.5) \mysqr{y};
\draw (-0.5,0) \mysqr{x};
\draw (-0.5,-0.5) \mysqr{*};

\draw (2.5,0.25) \mysqr{*};
\draw (2,0.75) \mysqr{x};
\draw (2,0.25) \mysqr{y};

\draw (2.5,-1.25) \mysqr{y};
\draw (2,-0.75) \mysqr{*};
\draw (2,-1.25) \mysqr{x};

\draw[-latex] (0.6, 0) -- (1.9, 0.75) node[midway, above, sloped] {\small $x > y$};
\draw[-latex] (0.6, 0) -- (1.9, -0.75) node[midway, below, sloped] {\small $x \leq y$};

\draw (0,-1.05) node {(b)};
\end{tikzpicture}
\end{multicols}
\caption{Incoming step (a) and out-going step (b) in jeu de taquin\label{fig:jeu-de-taquin}} 
\end{figure}

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

\begin{lem} \label{lem:skew-bijection}
For a partition $\lambda \vdash n$ and an integer $k > 0$, jeu de taquin gives a bijection between the following two sets:

\begin{itemize}
\item the set of tuples $(T, a_1, \ldots, a_k)$, where $T$ is a standard tableau of shape $\lambda$, and the $a_i$'s are distinct integers between $1$ and $n$;
\item the set of tuples $(\mu, T_0, T_1, a_1, \ldots, a_k)$, where $\mu$ is a partition of $k$, $T_0$ a skew tableau of shape $\lambda / \mu$ with entries from $1$ to $n-k$, $T_1$ a standard tableau of shape $\mu$ with entries from $1$ to $k$, and the $a_i$'s are distinct integers between $1$ and $n$.
\end{itemize}
\end{lem}
\begin{proof}
We apply the incoming slide to $a_1, \ldots, a_k$ successively in $T$. In this way, we obtain a skew tableau $T_0'$ of shape $\lambda / \mu$ for a certain partition $\mu \vdash k$ and a standard tableau $T_1$ of shape $\mu$ 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, \ldots, a_k), T_0, T_1$, we can reconstruct $T$. We conclude that this defines indeed a bijection. Figure~\ref{fig:skew-bijection} gives an example with $\lambda = (5,3,3,2) $ and $ \mu=(2)$.
\end{proof}

\begin{figure}
\centering
\begin{tikzpicture}
\begin{scope}
\draw (0,0) \mysqr{1};
\draw (0.5,0) \mysqr{2};
\draw (1,0) \mysqr{5};
\draw (1.5,0) \mysqr{9};
\draw (2,0) \mysqr{11};
\draw (0,0.5) \mysqr{3};
\draw (0.5,0.5) \mysqr{7};
\draw (1,0.5) \mysqr{10};
\draw (0,1) \mysqr{4};
\draw (0.5,1) \mysqr{8};
\draw (1,1) \mysqr{13};
\draw (0,1.5) \mysqr{6};
\draw (0.5,1.5) \mysqr{\textbf{12}};
\draw (2, 1.75) node {(12,5)};
\draw (1.4, -0.4) node {$T$};
\end{scope}

\begin{scope}[xshift=3.4cm]
\draw[very thick, ->] (0.9, 1.6) -- (0.9, 1.1); 
\draw[very thick, ->] (0.9, 1.1) -- (0.9, 0.6);
\draw[very thick, ->] (0.9, 0.6) -- (0.4, 0.6);
\draw[very thick, ->] (0.4, 0.6) -- (0.4, 0.1);

\draw (0.2,0.25) node{\textit{12}};
\draw (0.5,0) \mysqr{2};
\draw (1,0) \mysqr{\textbf{5}};
\draw (1.5,0) \mysqr{9};
\draw (2,0) \mysqr{11};
\draw (0,0.5) \mysqr{1};
\draw (0.5,0.5) \mysqr{3};
\draw (1,0.5) \mysqr{10};
\draw (0,1) \mysqr{4};
\draw (0.5,1) \mysqr{7};
\draw (1,1) \mysqr{13};
\draw (0,1.5) \mysqr{6};
\draw (0.5,1.5) \mysqr{8};
\draw (2, 1.75) node {(\textbf{12},5)};
\end{scope}

\begin{scope}[xshift=6.8cm]
\draw[very thick, ->] (1.4,0.1) -- (0.9, 0.1);

\draw (0.25,0.25) node{\textit{12}};
\draw (0.75,0.25) node{\textit{5}};

\draw (1,0) \mysqr{2};
\draw (1.5,0) \mysqr{9};
\draw (2,0) \mysqr{11};
\draw (0,0.5) \mysqr{1};
\draw (0.5,0.5) \mysqr{3};
\draw (1,0.5) \mysqr{10};
\draw (0,1) \mysqr{4};
\draw (0.5,1) \mysqr{7};
\draw (1,1) \mysqr{13};
\draw (0,1.5) \mysqr{6};
\draw (0.5,1.5) \mysqr{8};
\draw (2, 1.75) node {(12,\textbf{5})};
\end{scope}

\begin{scope}[xshift=10.2cm]
\draw (-0.1,-0.1) \mysqr{1};
\draw (0.4,-0.1) \mysqr{2};

\draw (1,0) \mysqr{2};
\draw (1.5,0) \mysqr{8};
\draw (2,0) \mysqr{10};
\draw (0,0.5) \mysqr{1};
\draw (0.5,0.5) \mysqr{3};
\draw (1,0.5) \mysqr{9};
\draw (0,1) \mysqr{4};
\draw (0.5,1) \mysqr{6};
\draw (1,1) \mysqr{11};
\draw (0,1.5) \mysqr{5};
\draw (0.5,1.5) \mysqr{7};
\draw (2, 1.75) node {(12,5)};

\draw (0.2, -0.4) node{$T_1$};
\draw (1.7, -0.4) node{$T_0$};
\end{scope}

\draw[thick,<->,shorten >=2pt,shorten <=2pt,>=stealth] (2.65, 1) -- (3.25,1);
\draw[thick,<->,shorten >=2pt,shorten <=2pt,>=stealth] (6.05, 1) -- (6.65,1);
\draw[thick,<->,shorten >=2pt,shorten <=2pt,>=stealth] (9.45, 1) -- (10.05,1);
\end{tikzpicture}
\caption{Example of the bijective relation between standard tableaux and skew tableaux via jeu de taquin\label{fig:skew-bijection}} 
\end{figure}

From the proof above, we conclude that, to compute a certain $f^{\lambda / \mu}$ for $\mu \vdash k$, it suffices to count the number of tuples $(T, (a_1, \ldots, a_k))$, with $T$ a standard tableau of shape $\lambda$, that are associated to any tuple of the form $(\mu, T_0, T_1, (a_1, \ldots, a_k))$. To accomplish this task, we need to know more about the fine structure of jeu de taquin.

\section{Trace forest of jeu de taquin} \label{sec:jdt}

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 \emph{right child of $c$}, and the cell immediately above the \emph{upper child of $c$}. We write $c_<$ and $c_\vee$ for these cells, respectively. 

\begin{defi}
Given a skew tableau $T$, its \emph{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. 
\end{defi}

\begin{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.
\end{remark}

Figure~\ref{fig:trace-forest} 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 \in 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 \in 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_\vee$ the subtree of $F$ rooted in $c_<$ and $c_\vee$ respectively.

\begin{figure}
\centering
\begin{tikzpicture}
\begin{scope}
\draw (0,0) \mysqr{1};
\draw (0.5,0) \mysqr{2};
\draw (1,0) \mysqr{5};
\draw (1.5,0) \mysqr{9};
\draw (2,0) \mysqr{11};
\draw (0,0.5) \mysqr{3};
\draw (0.5,0.5) \mysqr{7};
\draw (1,0.5) \mysqr{10};
\draw (0,1) \mysqr{4};
\draw (0.5,1) \mysqr{8};
\draw (1,1) \mysqr{13};
\draw (0,1.5) \mysqr{6};
\draw (0.5,1.5) \mysqr{12};
\end{scope}

\begin{scope}[xshift=3cm]
\draw (0,0) \mysqr{};
\draw (0.5,0) \mysqr{};
\draw (1,0) \mysqr{};
\draw (1.5,0) \mysqr{};
\draw (2,0) \mysqr{};
\draw (0,0.5) \mysqr{};
\draw (0.5,0.5) \mysqr{};
\draw (1,0.5) \mysqr{};
\draw (0,1) \mysqr{};
\draw (0.5,1) \mysqr{};
\draw (1,1) \mysqr{};
\draw (0,1.5) \mysqr{};
\draw (0.5,1.5) \mysqr{};

\draw[very thick] (0.25, 1.75) -- (0.25,0.25);
\draw[very thick] (2.25,0.25) -- (0.25,0.25);
\draw[very thick] (0.75,1.75) -- (0.75,0.75) -- (0.25, 0.75);
\draw[very thick] (1.25, 1.25) -- (1.25, 0.75) -- (0.75, 0.75);
\end{scope}

\begin{scope}[xshift=6cm]
\draw (1,0) \mysqr{4};
\draw (1.5,0) \mysqr{9};
\draw (2,0) \mysqr{10};
\draw (0.5,0.5) \mysqr{3};
\draw (1,0.5) \mysqr{5};
\draw (0,1) \mysqr{1};
\draw (0.5,1) \mysqr{6};
\draw (1,1) \mysqr{7};
\draw (0,1.5) \mysqr{2};
\draw (0.5,1.5) \mysqr{8};
\end{scope}

\begin{scope}[xshift=9cm]
\draw (1,0) \mysqr{};
\draw (1.5,0) \mysqr{};
\draw (2,0) \mysqr{};
\draw (0.5,0.5) \mysqr{};
\draw (1,0.5) \mysqr{};
\draw (0,1) \mysqr{};
\draw (0.5,1) \mysqr{};
\draw (1,1) \mysqr{};
\draw (0,1.5) \mysqr{};
\draw (0.5,1.5) \mysqr{};

\draw[very thick] (0.25, 1.75) -- (0.25, 1.25);
\draw[very thick] (0.75, 1.75) -- (0.75, 0.75);
\draw[very thick] (1.25, 1.25) -- (0.75, 1.25);
\draw[very thick] (2.25, 0.25) -- (1.25, 0.25) -- (1.25, 0.75);
\end{scope}
\end{tikzpicture}
\caption{Examples of skew tableaux and their trace forests\label{fig:trace-forest}} 
\end{figure}

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 \in S$, we write $T^{c}$ for the tableau obtained by applying an incoming slide to the entry contained in $c$, and $F^{c}$ its trace forest. The cells in $S \setminus \{ r \}$ are partitioned into the following categories, as in Figure~\ref{fig:fine-structures}:

\begin{itemize}
\item $D_<(c)$ (respectively $D_\vee(c)$), the subtree rooted at the right child (respectively the upper child) of $c$;
\item $P_h(c)$ (respectively $P_v(c)$), the set of cells among $c$ and its ancestors with a horizontal (respectively vertical) out-going arc;
\item $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$.
\end{itemize}

We define $C_<(c,S) = D_<(c) \cup P_h(c) \cup R(c)$ and $C_\vee(c,S) = D_\vee(c) \cup P_v(c) \cup 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_\vee(c,S)$ divide cells in $S \setminus \{ r \}$ into two groups. In the following lemma, we see that this grouping of cells is related to the structure of $F^{c}$.

\begin{figure}
\centering
\begin{tikzpicture}

\begin{scope}
\draw[very thick] (-0.1, 2.6) -- (-0.1, 0.1) -- (0.1, 0.1) -- (0.1,-0.1) -- (4.6, -0.1) -- (4.6, 1) -- (3.8, 1) -- (3.8, 1.9) -- (1.6, 1.9) -- (1.6, 2.6) -- cycle;
\draw[very thick] (-0.1,0.1) -- (-0.1,-0.1) -- (0.1,-0.1);
\draw[thick, blue] (0,0) -- (0,0.4);
\draw[thick, red, densely dashed, line width = 0.5mm] (0,0.4) -- node[above, midway]{\small \color{red} $P_h$} (1,0.4);
\draw[thick, blue] (1,0.4) -- (1, 0.7) node[right, very near start]{\small \color{blue} $P_v$};
\draw[thick, red, densely dashed, line width = 0.5mm] (1,0.7) -- (1.8, 0.7);
\draw[thick, black] (1.8, 0.84) -- (1.8, 0.7) -- (1.94, 0.7);
\draw[dashed] (1.8, 0.7) -- (2, 0.9) -- (2.3, 0.9) -- (2.3, 1.1) -- (3.2, 1.1) -- (3.2, 1.5) -- (3.8, 1.5);
\draw (1.8, 0.84) -- (1.8, 1.2) -- (2, 1.2) -- (2, 1.9);
\draw (1.94, 0.7) -- node[above, very near end]{\small $D_<$} (3.6, 0.7) -- (3.6, 1.2) -- (3.8, 1.2);

\filldraw[black] (-0.04,-0.04) rectangle +(0.08, 0.08);
\filldraw[blue] (-0.04,0.36) rectangle +(0.08, 0.08);
\filldraw[red] (0.96,0.36) rectangle +(0.08, 0.08);
\filldraw[blue] (0.96,0.66) rectangle +(0.08, 0.08);
\filldraw[red] (1.76,0.66) rectangle +(0.08, 0.08) node[below]{\small $c$};
\filldraw[black] (1.9,0.66) rectangle +(0.08, 0.08);
\filldraw[black] (1.76,0.8) rectangle +(0.08, 0.08);
\draw (3, 0.3) node{\small $R$};
\draw (0.9, 1.7) node{\small $A$};
\draw (2.7, 1.5) node{\small $D_\vee$};
\draw (-0.3, -0.3) node{$r$};
\end{scope}

\begin{scope}[xshift=7cm, yshift=1cm]
\draw (0,0) \mysqr{$y$};
\draw (0,0.5) \mysqr{$*$};
\draw (0.5,0) \mysqr{$z$};
\draw (0.5,0.5) \mysqr{$*$};
\draw[-latex, thick] (0.4,0.6) -- (0.4,0.1);
\draw (0.5,-0.4) node{$T$};
\draw (1.2, 1) node{$d$};
\draw (1.2, 0) node{$d_2$};
\draw (-0.3,0) node{$d_0$};
\draw (-0.3,1) node{$d_1$};

\draw (3,0) \mysqr{$*$};
\draw (3,0.5) \mysqr{$y$};
\draw (3.5,0) \mysqr{$z$};
\draw (3.5,0.5) \mysqr{$*$};
\draw[-latex, thick] (3.9,0.6) -- (3.9,0.1);
\draw (3.5,-0.4) node{$T^c$};
\draw (4.2, 1) node{$d$};
\draw (4.2, 0) node{$d_2$};
\draw (2.7, 0) node{$d_0$};
\draw (2.7, 1) node{$d_1$};

\draw[-latex, thick] (1.7,0.5) -- node[below, midway]{\tiny $z>y$} (2.3,0.5);
\end{scope}
\end{tikzpicture}
\caption{Fine structure of the trace forest\label{fig:fine-structures}} 
\end{figure}

\begin{lem} \label{lem:trace-forest-separation}
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_\vee(c,S)$ are in disjoint sets of trees in the trace forest of $T^{c}$.
\end{lem}
\begin{proof}
We only need to show that there is no no arc between elements in $C_<(c,S)$ and $C_\vee(c,S)$ in the trace forest of $T^{c}$. We will first prove that there is no arc from $C_<(c,S)$ to $C_\vee(c,S)$ in the trace forest of $T^{c}$. Let $d \in 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 \in P_h(c)$, $d \in D_<(c)$, and $d \in R(c)$. 

For $d \in P_h(c)$ and $d \in R(c)$, the only possible way that $d_1 \in C_\vee(c,S)$ is the case where $d_1 \in P_v(c)$. For $d \in D_<(c)$, it suffices to look at the root $d=r_1$ of $D_<(c)$. The only possibility that $d_1 \in C_\vee(c,S)$ is that we still have $d_1 \in 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~\ref{fig:fine-structures} illustrates this argument.

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

We have the following corollary when $T$ is a standard tableau.
\begin{coro} \label{coro:trace-forest-separation}
For a standard tableau $T$ of shape $\lambda$, 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 $\lambda / (1)$. Let $F_<$ and $F_\vee$ be the two trees of the trace forest of $T^c$ rooted at $r_<$ and $r_\vee$, respectively. The set of cells in $F_<$ (respectively $F_\vee$) is exactly $C_<(c,S)$ (respectively $C_\vee(c,S)$), and, when we perform an incoming slide for the entry in one of the cells in $C_<(c,S)$ (respectively $C_\vee(c,S)$, it must end in $r_<$ (respectively $r_\vee$).
\end{coro}
\begin{proof}
Since the trace forest of $T^c$ has only two trees, and $C_<(c,S), C_\vee(c,S)$ partition cells in $T^c$, we know that $C_<(c,S), C_\vee(c,S)$ must each consist of all the cells in the tree $F_<$ or the tree $F_\vee$. Since $a_<$ is both in $F_<$ and $C_<(c,S)$, the claim follows.
\end{proof}

Lemma~\ref{lem:trace-forest-separation} can be seen as a clarification of an argument in Lemma~$\mathrm{HC}^{*}$ in \cite{krattenthaler1999another}. Using Lemma~\ref{lem:trace-forest-separation}, we have the following simple bijective proof of a well-known character formula (cf.\ \cite{ingram1950some, corteel2004content, lassalle2008explicit}). To the author's knowledge, no purely bijective proof was known before for this simple formula.

\begin{thm} \label{thm:mu-2}
For a partition $\lambda \vdash n$, we have
\[ n(n-1)\chi^{\lambda}_{2,1^{n-2}} = 2 f^{\lambda} \sum_{w \in \lambda} c(w). \]
\end{thm}
\begin{proof}
Since, from Lemma~\ref{lem:character-as-skew-tableau}, it follows that $\chi^{\lambda}_{2,1^{n-2}} = f^{\lambda / (2)} - f^{\lambda / (1,1)}$, we want to count the difference between the number of skew tableaux of shape $\lambda / (2)$ and those of shape $\lambda / (1,1)$.

Let $(T,e_1,e_2)$ be a tuple with $T$ a standard tableau of shape $\lambda$ and $e_1 \neq e_2$ two \emph{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 $(\mu, T_0, T_1,e_1,e_2)$ in the bijection in Lemma~\ref{lem:skew-bijection}, in which $\mu$ can only be either $(2)$ or $(1,1)$, and $T_1$ is fixed by $\mu$ 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 $\lambda / (2)$ or $\lambda / (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\break $ST(T,e_2,e_1)$ to $f^{\lambda / (2)} - f^{\lambda / (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 non-zero 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_\vee$, 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) \subset C_\vee(c_1,F)$, and, in $T^{e_2}$, the cell $c_1$ still contains $e_1$ and is in $R(c_2) \subset C_<(c_2,F)$. From Corollary~\ref{coro:trace-forest-separation}, we know that $ST(T,e_1,e_2)$ is of shape $\lambda / (1,1)$, while $ST(T,e_2,e_1)$ is of shape $\lambda / (2)$. Thus this case does not contribute to $f^{\lambda / (2)} - f^{\lambda / (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 \in D_<(c_1) \subset C_<(c_1,F)$ in $T^{e_1}$ and $c_{1,<} \in P_1(c_2) \subset C_<(c_2,F)$ in $T^{e_2}$. From Corollary~\ref{coro:trace-forest-separation}, we infer that $ST(T,e_1,e_2)$ and $ST(T,e_2,e_1)$ are both of shape $\lambda / (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 $\lambda / (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 $\lambda / (2)$ and $2j$ tableaux of shape $\lambda / (1,1)$. This yields a contribution of $2c(c_2)$ to $f^{\lambda / (2)} - f^{\lambda / (1,1)}$, which is independent of $T$.

In the end, we conclude the proof by observing that 
$$n(n-1)(f^{\lambda / (2)} - f^{\lambda / (1,1)}) = 2 f^{\lambda} \sum_{w \in \lambda} c(w).\qedhere
$$
\end{proof}

\section{Character evaluation using the trace forest} \label{sec:chara-eval}

We will now use the notion of trace forest to calculate $f^{\lambda / \mu}$ with fixed small $\mu$. In \cite{corteel2004content} and \cite{lassalle2008explicit} (see also \cite{kerov1994polynomial}), it was proved that $\chi^{\lambda}_{\mu}$ can be expressed using so-called ``content evaluation''. By Lemma~\ref{lem:character-as-skew-tableau}, we know that $f^{\lambda / \mu}$ 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^{\lambda / \mu}$ for general $\lambda$ and small $\mu$ in terms of content evaluation. This provides counting proofs of various character evaluation formulae.

\subsection{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 \emph{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(\cdot)$ stands for the usual content. For any partition $\alpha=(\alpha_1, \ldots, \alpha_l)$, we define the \emph{content power sum} of $S$, denoted by $cp^{\alpha}_r(S)$, as follows, with the convention that $0^0=1$:
\[ cp^{\alpha}_r(S) = \prod_{i=1}^{l} \sum_{c \in S} c_r(c)^{\alpha_i - 1}. \]
When $r$ is also the root of $S$, we omit the $r$ in $cp^{\alpha}_r(S)$ and denote the function by $cp^{\alpha}(S)$.

We can also define the function $cp^{\alpha}$ on a partition $\lambda$ by identifying $\lambda$ with the set of all cells in the Ferrers diagram of $\lambda$, 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 $\lambda$ and $F_T$ its only tree in its trace forest, we have $cp^{\alpha}(\lambda) = cp^{\alpha}(F_T)$.

We make the choice of using $\alpha_i - 1$ in the exponent of the power sum because we want to include the size $n$ of the partition $\lambda$ as $cp^{1}(\lambda)$. In this way, we can express any polynomial in $n$ and power sums of contents as a linear combination of $cp^{\alpha}(\lambda)$'s for various partitions $\alpha$.

By abuse of notation, given a subset $C$ of cells in $T$, we define $cp^{\alpha}_r(C)$ as the sum $\sum_i cp^{\alpha}_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^{\alpha}_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^{\alpha}_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_\vee$ the cell above. We define two linear operators $\Gamma_+$ and $\Gamma_-$ as follows:
\[ \Gamma_+ cp^{(k)}_r = cp^{(k)}_{r_<}, \quad \Gamma_- cp^{(k)}_r = cp^{(k)}_{r_\vee}. \]
By requiring $\Gamma_+$ and $\Gamma_-$ to be compatible with multiplication, i.e., $\Gamma_+ (fg) = (\Gamma_+ f)(\Gamma_+ g)$ and the same for $\Gamma_-$, these two operators are thus defined on the algebra generated by the $cp^{\alpha}_r(S)$'s.

\begin{lem}\label{lem:operator-gamma}
For any integer $k \geq 1$, the result of application of $\Gamma_+$ and $\Gamma_-$ is given by
\[
\Gamma_+ cp^{(k)}_r = \sum_{i=1}^{k} (-1)^{k-i} \binom{k-1}{i-1} cp^{(i)}_r, \quad \Gamma_- cp^{(k)}_r = \sum_{i=1}^{k} \binom{k-1}{i-1} cp^{(i)}_r.
\]
Therefore the algebra spanned by the $cp^{\alpha}_r$'s is invariant under application of $\Gamma_+$ and $\Gamma_-$. Moreover, $\Gamma_+ \Gamma_- = \Gamma_- \Gamma_+ = \mathrm{id}$.
\end{lem}
\begin{proof}
It is a simple observation that, for any cell $c$ and $r$, we have $c_{r_<}(c) + 1 = c_r(c) = c_{r_\vee}(c) - 1$. This is simply due to the change of origin.

Now, for any subtree $S$, we have
\[ (\Gamma_+ cp^{(k)}_r)(S) = \sum_{c \in S} c_{r_<}^{k-1}(c) = \sum_{c \in S} (c_{r}(c)-1)^{k-1} = \sum_{i=1}^{k} (-1)^{k-i} \binom{k-1}{i-1} cp^{(i)}_r(S) \]
and
\[ (\Gamma_- cp^{(k)}_r)(S) = \sum_{c \in S} c_{r_\vee}^{k-1}(c) = \sum_{c \in C} (c_{r}(c)+1)^{k-1} = \sum_{i=1}^{k} \binom{k-1}{i-1} cp^{(i)}_r(S) .\]

For establishing $\Gamma_+ \Gamma_- = \Gamma_- \Gamma_+ = \mathrm{id}$, we only need to notice that $c_{(r_<)_\vee}(c) = c_r(c) = c_{(r_\vee)_<}(c)$ for any cell $c$.
\end{proof}

Therefore, for any choice of $r$, the algebra spanned by the $cp^{\alpha}_r$'s is the same. We denote this algebra formed by real-valued functions over subtrees in the trace forests of skew tableaux by $\Lambda$. We notice that, when restricted to a partition $\lambda$, a function $f \in \Lambda$ is a shifted symmetric function (cf.\ \cite{corteel2004content, kerov1994polynomial}) evaluated at the parts $\lambda_i$ of $\lambda$.
Conversely, for any shifted symmetric function $s^*_\mu$, there is a function $f \in \Lambda$ such that $s^*_\mu(\lambda_1, \lambda_2, \ldots) = f(\lambda)$ for any partition $\lambda$. Therefore, the algebra $\Lambda$ is isomorphic to the algebra of shifted symmetric functions.

\subsection{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_\vee$ for the subtrees rooted at $r_<$ and $r_\vee$, respectively (if they exist, otherwise they are defined to be the empty tree). For a partition $\alpha \vdash k$, we introduce the notations $\mycpr{\alpha}(S)$ (respectively $\mycpa{\alpha}(S)$) by
\[ \mycpr{\alpha}(S) = cp^{\alpha}_r(S_<), \quad \mycpa{\alpha}(S) = cp^{\alpha}_r(S_\vee) .\]

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

\begin{lem} \label{lem:inductive-identify}
Let $f$ and $ g$ be two functions on subtrees of trace forests. If $f(\varnothing) = g(\varnothing)$ and $\Delta f = \Delta g$, then we have $f=g$.
\end{lem}
\begin{proof}
Since $\Delta$ is linear, for any $S$, we have $(f-g)(S) = (f-g)(S_<) + (f-g)(S_\vee)$. The proof is then completed by an induction on the size of the tree~$S$.
\end{proof}

We now prove that the inductive form of $cp^{\alpha}$ can be explicitly expressed as a polynomial of $\mycpr{k}$ and $\mycpa{k}$. These expressions, combined with Lemma~\ref{lem:inductive-identify}, will be used to recover content power sums from their inductive form.

\begin{prop} \label{prop:cp-inductive-form}
For any non-empty subtree $S$ in a trace forest and any integer $k>1$, we have
\begin{alignat}2
\label{eq1}
cp^{(1)}(S) &= 1 + \mycpr{1}\!\!(S) + \mycpa{1}(S); &\quad  cp^{(k)}(S) &= \mycpr{k}\!\!(S) + \mycpa{k}(S) ;\\
\label{eq2}
cp^{(k)}(S_<) &= \sum_{i=0}^{k-1} (-1)^{i} \binom{k-1}{i} \mycpr{k-i}\!\!(S); &\quad cp^{(k)}(S_\vee) &= \sum_{i=0}^{k-1} \binom{k-1}{i} \mycpa{k-i}(S).
\end{alignat}
Furthermore, for any partition $\alpha$, $\Delta cp^{\alpha}$ can be expressed as a polynomial in $\mycpr{k}$ and $\mycpa{k}$.
\end{prop}
\begin{proof}
The equalities in \eqref{eq1} come directly from the definition of $cp^{(k)}$. For establishing those in \eqref{eq2}, we notice that $cp^{(k)}(S_<)$ is rooted at $r_<$, thus we have $cp^{(k)}(S_<) = (\Gamma_+ cp^{(k)}_r)(S_<)$, and we conclude by Lemma~\ref{lem:operator-gamma}. For $cp^{(k)}(S_\vee)$ we similarly have $cp^{(k)}(S_\vee) = (\Gamma_- cp^{(k)}_r)(S_\vee)$.

By \eqref{eq1} and \eqref{eq2}, for any subtree $S$ of a trace forest, we can express $cp^{\alpha}(S)$, $cp^{\alpha}(S_<)$, and $cp^{\alpha}(S_\vee)$ as polynomials in $\mycpr{k}\!\!\!(S)$ and $\mycpa{k}(S)$. The fact that $(\Delta cp^{\alpha})(S) = cp^{\alpha}(S) - cp^{\alpha}(S_<) - cp^{\alpha}(S_\vee)$ then completes the proof.
\end{proof}

Here are some examples of the inductive form of some $cp^{\alpha}$'s; for simplicity, we consider $cp^{\alpha}, \mycpr{\alpha}, \mycpa{\alpha}$ as functions and omit their arguments:
\begin{align*}
\Delta cp^{(1)} &= 1; \quad \Delta cp^{(2)} = \mycpr{1} - \mycpa{1}; \quad \Delta cp^{(1,1)} = 2 \mycpr{1} \mycpa{1} + 2 \mycpr{1} + 2 \mycpa{1} + 1; \\
\Delta cp^{(3)} &= 2 \mycpr{2} - 2 \mycpa{2} - \mycpr{1} - \mycpa{1} ;\\
\Delta cp^{(2,1)} &= \mycpr{2} \mycpa{1} + \mycpr{1} \mycpa{2} + \mycpr{2} + \mycpa{2} + \mycpr{1,1} - \mycpa{1,1} ;\\
\Delta cp^{(1,1,1)} &= 3 \mycpr{1,1} \mycpa{1} + 3 \mycpr{1} \mycpa{1,1} + 3 \mycpr{1,1} + 6 \mycpr{1} \mycpa{1} + 3 \mycpa{1,1} + 3 \mycpr{1} + 3 \mycpa{1} + 1. %\\
%\Delta cp^{(4)} &= 3 \mycpr{3} - 3 \mycpa{3} - 3 \mycpr{2} - 3 \mycpa{2} + \mycpr{1} - \mycpr{1} \\
%\Delta cp^{(3,1)} &= \mycpr{3} \mycpa{1} + \mycpr{1} \mycpa{3} + \mycpr{3} + \mycpa{3} + 2 \mycpr{2,1} - 2 \mycpa{2,1} - \mycpr{1,1} - \mycpr{1,1} \\
%\Delta cp^{(2,2)} &= 2 \mycpr{2} \mycpa{2} + 2 \mycpr{2, 1} - 2 \mycpa{2,1} - \mycpr{1,1} - \mycpa{1,1} 
\end{align*}

\subsection{Inductive counting of skew tableaux}

It is now natural to try to count skew tableaux of different shapes using 
induction. For integers $n,k \geq 0$, we define the \emph{falling factorial} $(n)_k = n(n-1) \cdots (n-k+1)$. Evidently, the number of $k$-tuples of distinct elements from $\{1,2,\dots,n\}$ is exactly $(n)_k$. Given a standard tableau of shape $\lambda$ and a small partition $\mu$, we now try to inductively count the number of tuples that lead to a skew tableau of shape $\lambda / \mu$ using the bijection in Lemma~\ref{lem:skew-bijection}. 

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^{\lambda / (k)}$. The definition of $G_{(k)}(S)$ for a subtree $S$ is essentially a sum over all cells $c \in 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 \in S$ splits into three cases: $c=r$, $c \in S_<$, and $c \in S_\vee$. The first case is readily expressed as content evaluation for $S_<$ and $S_\vee$, 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_\vee$. We thus obtain the inductive form, and by comparing those of $cp^{\alpha}$, we can identify the sum as a linear combination of content evaluations of $S$, thus proving that $G_{(k)}$ is in fact in $\Lambda$, and that $f^{\lambda / (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 \emph{conjugate} of a partition $\lambda$, denoted by $\lambda^{\dagger}$, is the partition whose Ferrers diagram is that of $\lambda$ flipped alongside the line $y=x$.

\begin{lem} \label{lem:induction-case}
For a skew tableau $T$, a subtree $S$ in its trace forest rooted in $r$, and $c \in S$, we have the following three cases:
\begin{itemize}
\item $c=r$. In this case, $C_<(r,S)=S_<$ and $C_\vee(r,S)=S_\vee$.
\item $c \in S_<$. In this case, $C_<(c,S)=C_<(c,S_<) \cup \{ r_< \}$ and $C_\vee(c,S)=C_\vee(c,S_<) \cup S_\vee$.
\item $c \in S_\vee$. In this case, $C_<(c,S)=C_<(c,S_\vee) \cup S_<$ and $C_\vee(c,S)=C_\vee(c,S_\vee) \cup \{ r_\vee \}$.
\end{itemize}
\end{lem}
\begin{proof}
The case $c=r$ is trivial. We now analyse the case where $c \in S_<$. The case where $c \in S_\vee$ can be treated similarly.

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

Since we will evaluate functions in $\Lambda$ on disjoint union of sets, we need the following proposition to ``decompose'' the evaluation.

\begin{prop}\label{prop:union-eval}
For a partition $\alpha = (\alpha_1, \ldots, \alpha_l)$, two disjoint subsets $A, B$ of cells in a tableau $T$, and $r$ an arbitrary cell in $T$, we have
\[ cp^{\alpha}_r(A \uplus B) = \sum_{\alpha^{(1)} \uplus \alpha^{(2)} = \alpha} \left( \prod_{i \geq 1} \binom{m(\alpha, i)}{m(\alpha^{(1)},i)} \right) cp^{\alpha^{(1)}}_r(A) cp^{\alpha^{(2)}}_r(B).  \]
Here, $\uplus$ stands for the union of multisets, and $m(\alpha, i)$ (respectively $m(\alpha^{(1)},1)$) is the multiplicity of $i$ in $\alpha$ (respectively $\alpha^{(1)}$).
\end{prop}
\begin{proof}
It follows from the definition of $cp^{(k)}_r$ that
\begin{align*}
cp^{\alpha}_r(A \uplus B) &= \prod_{i=1}^{l} \left( cp^{(\alpha_i)}_r(A) + cp^{(\alpha_i)}_r(B) \right) \\
&= \sum_{\alpha^{(1)} \uplus \alpha^{(2)} = \alpha} \left( \prod_{i \geq 1} \binom{m(\alpha, i)}{m(\alpha^{(1)},i)} \right) cp^{\alpha^{(1)}}_r(A) cp^{\alpha^{(2)}}_r(B). \qedhere
\end{align*}
\end{proof}

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

\begin{prop} \label{prop:young-lattice}
For a partition $\mu$, let $P(\mu)$ be the set of partitions whose Ferrers diagram can be obtained by adding a cell to that of $\mu$. For any partition $\lambda$, we have $f^{\lambda / \mu} = \sum_{\mu' \in P(\mu)} f^{\lambda / \mu'}$.
\end{prop}
\begin{proof}
This follows from the classification of all skew tableaux of shape $\lambda / \mu$ by the cell containing $1$.
\end{proof}

\begin{prop} \label{prop:conjugate-mu}
For a partition $\mu$ and its conjugate $\mu^{\dagger}$, let $F$ be a function such that, for any $\lambda$, we have 
$$(|\lambda |)_{(|\mu|)} f^{\lambda / \mu} / f^{\lambda} = F(cp^{(1)}(\lambda), cp^{(2)}(\lambda), \ldots, cp^{(i)}(\lambda), \ldots).$$ 
Then we have 
$$(|\lambda |)_{(|\mu^\dagger |)} f^{\lambda / \mu^{\dagger}} / f^{\lambda} = F(cp^{(1)}(\lambda), -cp^{(2)}(\lambda), \ldots, (-1)^{i-1}cp^{(i)}(\lambda), \ldots).$$
\end{prop}
\begin{proof}
By flipping skew tableaux alongside $y=x$, we see that $f^{\lambda / \mu^{\dagger}} = f^{\lambda^{\dagger} / \mu}$. The claim then follows by observing that $cp^{(k)}(\lambda) = (-1)^{k-1} cp^{(k)}(\lambda^{\dagger})$.
\end{proof}

We now recursively define a family of functions $G_{(k)}$ on sets of cells that will be related to $f^{\lambda / (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 \uplus 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^{(1)}_d(S) = |S|, \quad G_{(k)}(S,d) = \sum_{c \in S}G_{(k-1)}(C_<(c,S), d_<) \mbox{ for } k \geq 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 $\Lambda$ and does not really depend on $T$.

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

\begin{prop} \label{prop:recursive-function}
For a partition $\lambda$, a standard tableau $T$ of shape $\lambda$ 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, \ldots, 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 $\lambda / (k)$.
\end{prop}
\begin{proof}
We proceed by direct counting of the tuples satisfying our conditions. For such a tuple $(e_1, e_2, \ldots, e_k)$, for $1 \leq i \leq k$, let $T_i$ be the tableau obtained by performing the incoming steps for $e_1, e_2, \ldots, e_i$, and let $T_0 = T$. $T_i$ is a skew tableau of shape $\lambda / (i)$. We should note that each $T_i$ depends on the entries $e_1, e_2, \ldots, 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_{\vee, 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 $\lambda / (i-1)$, into the skew tableau $T_i$ of shape $\lambda / (i)$, we have $c_i \in S_{<,i-1}$. It is clear that $S_{\vee,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~\ref{coro:trace-forest-separation} to the cell containing $e_1$ in $T_*$. By Lemma~\ref{lem:trace-forest-separation}, $C_<(c_i, S_{<,i-1})$ is disconnected from $C_\vee(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_\vee(c_i, S_{<,i-1})$ does not intersect $S_{<,i}$ either. Since $S_{\vee,i-1}$, $C_<(c_i, S_{<,i-1})$, and $C_\vee(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, \ldots, e_i$. Let $H_{(k,i)}(T,e_1,e_2, \ldots, e_i)$ be the number of possible choices of $e_{i+1}, \ldots, e_k$ when $e_1, e_2, \ldots, e_i$ is fixed. It is clear that $H_{k,k-1}(T,e_1, \ldots, 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, \ldots, e_{k-a}) = G_{(a)}(S_{<,k-a}, r_{k-a})$, we have
\begin{align*}
H_{k,k-a-1}(T,e_1, \ldots, e_{k-a-1}) &= \sum_{c_{k-a} \in S_{<,k-a-1}} H_{k,k-a}(e_1, \ldots, e_{k-a}) \\
&= \sum_{c_{k-a} \in S_{<,k-a-1}} G_{(a)}(S_{<,k-a}, r_{k-a}) \\
&= \sum_{c_{k-a} \in 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}).
\end{align*}
The proof is completed by an induction on $a$ to obtain $H_{(k,0)}(T) = G_{(k)}(S,r)$.
\end{proof}

With the help of the family $G_{(k)}$, we can now proceed to examples of computing $f^{\lambda / (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_\vee$ the cell above $r$.

\begin{prop} \label{prop:tableau-2}
For a partition $\lambda \vdash n$, we have
\[ (n)_2 f^{\lambda / (2)} / f^{\lambda} = \frac{1}{2} cp^{(1,1)}(\lambda) + cp^{(2)}(\lambda) - \frac{1}{2} cp^{(1)}(\lambda) = n(n-1)/2 + \sum_{w \in \lambda} c(w). \]
\end{prop}
\begin{proof}
The number $(n)_{2} f^{\lambda / (2)}$ equals the number of tuples $((2), T', T'' ,e_1 , e_2)$, where $T'$ is of shape $\lambda / (2)$. Therefore, by taking the correspondence in Lemma~\ref{lem:skew-bijection}, and by Proposition~\ref{prop:recursive-function}, writing $F_T$ for the trace forest (consisting of one single tree) of the standard tableau $T$, we have
\[ (n)_{2} f^{\lambda / (2)} = \sum_{T \mathrm{\; of \; shape \;} \lambda} G_{(2)}(F_T). \]

We now compute $G_{(2)}(S)$ for $S$ rooted at $r$. We notice that $G_{(1)}$ is in $\Lambda$, and that
\[G_{(2)}(S) = \sum_{c \in S} G_{(1)}(C_<(c,S), r_<) = \sum_{c \in S} (\Gamma_+ cp^{(1)}_{r})(C_<(c,S)) = \sum_{c \in S} cp^{(1)}_{r}(C_<(c,S)). \]

We now compute the inductive form of $G_{(2)}(S)$ using Lemma~\ref{lem:induction-case} and Proposition~\ref{prop:union-eval}:
\begin{align*}
(\Delta G_{(2)})(S) &= G_{(2)}(S) - G_{(2)}(S_<) - G_{(2)}(S_\vee) \\
&= \sum_{c \in S = \{r \} \cup S_< \cup S_\vee} cp^{(1)}_r(C_<(c,S)) - \sum_{c \in S_<} (\Gamma_+ cp^{(1)}_r)(C_<(c,S_<)) \\
&\kern2cm
- \sum_{c \in S_\vee} (\Gamma_- cp^{(1)}_r)(C_<(c,S_\vee)) \\
&= cp^{(1)}_{r}(C_<(r,S)) + \sum_{c \in S_<} \left( cp^{(1)}_{r}(C_<(c,S)) - cp^{(1)}_{r}(C_<(c,S_<)) \right) \\
&\kern2cm 
+ \sum_{c \in S_\vee} \left( cp^{(1)}_{r}(C_<(c,S)) - cp^{(1)}_{r}(C_<(c,S_\vee)) \right).
\end{align*}

By the use of Lemma~\ref{lem:induction-case}, the differences in the summand can be computed:
\begin{align*}
(\Delta G_{(2)})(S) &= cp^{(1)}_{r}(C_<(r,S)) + \sum_{c \in S_<} cp^{(1)}_{r}(\{ r_< \}) + \sum_{c \in S_\vee} cp^{(1)}_{r}(S_<) \\
&= \mycpr{1}\!\!(S) + \sum_{c \in S_<} 1 + \sum_{c \in S_\vee} \mycpr{1}\!\!(S) \\
&= 2\mycpr{1}\!\!(S) + \mycpr{1}\!\!(S)\mycpa{1}\!\!(S) \\
&= \left( \Delta \left( \frac{1}{2} cp^{(1,1)} + cp^{(2)} - \frac{1}{2} cp^{(1)} \right) \right)(S).
\end{align*}

By Lemma~\ref{lem:inductive-identify}, we have $G_{(2)} = \frac{1}{2} cp^{(1,1)} + cp^{(2)} - \frac{1}{2} cp^{(1)} \in \Lambda$. We notice that, since $G_{(2)} \in \Lambda$, for any standard tableau $T$ of shape $\lambda$, we have $G_{(2)}(F_T) = G_{(2)}(\lambda)$, which does not depend on $T$. We thus may finish the proof by combining $G_{(2)}(F_T) = G_{(2)}(\lambda)$ with the sum formula at the beginning of the proof, noticing that there are $f^\lambda$ standard tableaux of shape $\lambda$.
\end{proof}

A formula for $f^{\lambda / (1,1)}$ can be found either by the same approach, or by using Proposition~\ref{prop:young-lattice} applied to $\mu=(1)$, or by using Proposition~\ref{prop:conjugate-mu}. Proposition~\ref{prop:tableau-2} implies Theorem~\ref{thm:mu-2}, thus can be viewed as an alternative proof. We have the first evidence that our scheme may work.

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

\begin{prop} \label{prop:tableau-3}
For a partition $\lambda \vdash n$, we have
\[
(n)_{3} f^{\lambda / (3)} / f^{\lambda} = \frac{1}{6} cp^{(1,1,1)}(\lambda) + cp^{(2,1)}(\lambda) + cp^{(3)}(\lambda) - cp^{(1,1)}(\lambda) - 2cp^{(2)}(\lambda) + \frac{5}{6} cp^{(1)}(\lambda).
\]
\end{prop}
\begin{proof}
The number $(n)_{3} f^{\lambda / (3)}$ equals the number of tuples $((3), T', T'' ,e_1 , e_2,e_3)$, where $T'$ is of shape $\lambda / (3)$. Therefore, by using the correspondence in Lemma~\ref{lem:skew-bijection}, and by Proposition~\ref{prop:recursive-function}, writing $F_T$ for the trace forest (consisting of one single tree) of the standard tableau $T$, we have
\[ (n)_{3} f^{\lambda / (3)} = \sum_{T \mathrm{\; of \; shape \;} \lambda} G_{(3)}(F_T). \]

We now compute $G_{(3)}(S)$ for $S$ rooted at $r$. By the proof of Proposition~\ref{prop:tableau-2}, we see that $G_{(2)}$ is in $\Lambda$. Furthermore,
by the definition of $G_{(3)}(S)$, we have
\begin{align*} 
G_{(3)}(S) &= \sum_{c \in S} G_{(2)}(C_<(c,S), r_<) = \sum_{c \in S} \left(\Gamma_+ \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{1}{2} cp_r^{(1)} \right) \right) (C_<(c,S)) \\
&= \sum_{c \in S} \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{3}{2} cp_r^{(1)} \right) (C_<(c,S)).
\end{align*}

We now compute the inductive form of $G_{(3)}$ using Lemma~\ref{lem:induction-case} and Proposition~\ref{prop:union-eval}:
\begin{align*}
(\Delta G_{(3)})(S) &= \sum_{c \in S} \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{3}{2} cp_r^{(1)} \right) (C_<(c,S)) \\
&\kern2cm
- \sum_{c \in S_<} \left( \Gamma_+ \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{3}{2} cp_r^{(1)} \right) \right) (C_<(c,S_<)) \\
&\kern2cm
 - \sum_{c \in S_\vee} \left( \Gamma_- \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{3}{2} cp_r^{(1)} \right) \right) (C_<(c,S_\vee)) \\
&= \sum_{c \in S} \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{3}{2} cp_r^{(1)} \right) (C_<(c,S)) \\
&\kern2cm
- \sum_{c \in S_<} \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{5}{2} cp_r^{(1)} \right) (C_<(c,S_<)) \\
&\kern2cm
 - \sum_{c \in S_\vee} \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{1}{2} cp_r^{(1)} \right) (C_<(c,S_\vee)).
\end{align*}
By Lemma~\ref{lem:induction-case}, the differences can be simplified by splitting the first sum into three parts: $c=r$, $c \in S_<$, and $c \in S_\vee$. We notice that, by Proposition~\ref{prop:union-eval}, for two disjoint sets of cells $A$ and $B$, we have $cp^{(1,1)}_r(A \uplus B) = cp^{(1,1)}_r(A) + 2cp^{(1)}_r(A) + cp^{(1,1)}_r(B)$. Hence,
\begin{align*}
(\Delta G_{(3)})(S) &= \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{3}{2} cp_r^{(1)} \right) (S_<) 
 + \sum_{c \in S_<} \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{3}{2} cp_r^{(1)} \right) (\{ r_< \})\\
&\kern1cm
 + (cp_r^{(1)}(\{ r_< \}) + 1) \sum_{c \in S_<} cp_r^{(1)} (C_<(c,S_<)) \\
&\kern1cm
+ \sum_{c \in S_\vee} \left( \frac{1}{2} cp_r^{(1,1)} + cp_r^{(2)} - \frac{3}{2} cp_r^{(1)} \right) (S_<)\\
&\kern1cm
 +(cp_r^{(1)}(S_<) - 1) \sum_{c \in S_\vee} cp_r^{(1)}(C_<(c,S_\vee)) .
\end{align*}
We know from the definition of $G_{(2)}$ that $G_{(2)}(S) = \sum_{c \in S} cp^{(1)}_r(C_<(c,S))$, and from the definition of $cp^{(1)}_r$ and Lemma~\ref{lem:operator-gamma} that $cp^{(1)}_r(S) = cp^{(1)}_{r_<}(S) = cp^{(1)}_{r_\vee}(S) = |S|$. These facts, combined with the expression of $G_{(2)}(S)$ in Proposition~\ref{prop:tableau-2}, yield
\begin{multline*}
(\Delta G_{(3)})(S) = \frac{1}{2} \mycpr{1,1}\!\!(S) + \mycpr{2}\!\!(S) - \frac{3}{2} \mycpr{1}\!\!(S) + 2G_{(2)}(S_<) \\
 + \mycpa{1}\!(S) \left( \frac{1}{2} \mycpr{1,1}\!\!(S) + \mycpr{2}\!\!(S) - \frac{3}{2} \mycpr{1}\!\!(S) \right) + (\mycpr{1}\!\!(S) - 1) G_{(2)}(S_\vee) .
\end{multline*}

We now compute $G_{(2)}(S_<)$ and $G_{(2)}(S_\vee)$. Since the root of $S_<$ is $r_<$, we have
\begin{align*} 
G_{(2)}(S_<) &= \left( \frac{1}{2} cp^{(1,1)}_{r_<} + cp^{(2)}_{r_<} - \frac{1}{2} cp^{(1)}_{r_<} \right) (S_<) = \left( \Gamma_+ \left( \frac{1}{2} cp^{(1,1)}_{r} + cp^{(2)}_{r} - \frac{1}{2} cp^{(1)}_{r} \right) \right) (S_<) \\
&= \left( \frac{1}{2} cp^{(1,1)}_{r} + cp^{(2)}_{r} - \frac{3}{2} cp^{(1)}_{r} \right) (S_<) = \frac{1}{2} \mycpr{1,1}\!\!(S) + \mycpr{2}\!\!(S) - \frac{3}{2} \mycpr{1}\!\!(S).
\end{align*}
Similarly, we have $G_{(2)}(S_\vee) = \frac{1}{2} \mycpa{1,1}\!(S) + \mycpa{2}\!(S) + \frac{1}{2} \mycpa{1}\!(S)$. By substituting both expression back into the computation of $(\Delta G_{(3)})(S)$, we obtain
\begin{align*}
 (\Delta G_{(3)})(S) 
&= \frac{1}{2} \mycpr{1,1}\!\!(S) \mycpa{1}\!\!(S) + \frac{1}{2} \mycpr{1}\!\!(S) \mycpa{1,1}\!\!(S) + \mycpr{2}\!\!(S) \mycpa{1}\!\!(S) + \mycpr{1}\!\!(S) \mycpa{2}\!\!(S) \\
&\quad - \mycpr{1}\!\!(S) \mycpa{1}\!\!(S) + 3 \mycpr{2}\!\!(S) - \mycpa{2}\!\!(S) + \frac{3}{2} \mycpr{1,1}\!\!(S) - \frac{1}{2} \mycpa{1,1}\!\!(S) - \frac{9}{2} \mycpr{1}\!\!(S) \\
&\quad - \frac{1}{2} \mycpa{1}\!\!(S) \\
&= \left( \Delta \left( \frac{1}{6} cp^{(1,1,1)} + cp^{(2,1)} + cp^{(3)} - cp^{(1,1)} - 2 cp^{(2)} + \frac{5}{6} cp^{(1)} \right) \right)(S)
\end{align*}
By Lemma~\ref{lem:inductive-identify}, we have $G_{(3)} = \frac{1}{6} cp^{(1,1,1)} + cp^{(2,1)} + cp^{(3)} - cp^{(1,1)} - 2 cp^{(2)} + \frac{5}{6} cp^{(1)} \in \Lambda$. Therefore, for any standard tableau $T$ of shape $\lambda$, we have $G_{(3)}(F_T) = G_{(3)}(\lambda)$, which is independent of $T$. We then apply this fact and the expression of $G_{(3)}$ in $cp^{\alpha}$ to the sum formula of $(n)_3 f^{\lambda/(3)}$ at the beginning of the proof to complete the proof.
\end{proof}

Combining this proposition with Propositions~\ref{prop:young-lattice} and~\ref{prop:tableau-2}, we are also able to compute $f^{\lambda / (2,1)}$ and $f^{\lambda / (1,1,1)}$, and we obtain the character evaluated at a $3$-cycle for $\lambda \vdash n$: 
\[
\frac {(n)_3} {f^{\lambda}} \chi^{\lambda}_{(3,1^{n-3})}  = 3cp^{(3)}(\lambda) - \frac{3}{2} cp^{(1,1)}(\lambda) + \frac{3}{2} cp^{(1)}(\lambda) = 3\sum_{w \in \lambda} (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^{\lambda / (4)}$. 

\begin{prop} \label{prop:tableau-4}
For a partition $\lambda \vdash n$,
\begin{multline*}
(n)_{4} f^{\lambda / (4)} / f^{\lambda} = \frac{1}{24} cp^{(1,1,1,1)}(\lambda) + \frac{1}{2} cp^{(2,1,1)}(\lambda) + \frac{1}{2} cp^{(2,2)}(\lambda) + cp^{(3,1)}(\lambda) + cp^{(4)}(\lambda) \\
 - \frac{3}{4} cp^{(1,1,1)}(\lambda) - \frac{9}{2} cp^{(2,1)}(\lambda) - \frac{9}{2} cp^{(3)}(\lambda) + \frac{71}{24} cp^{(1,1)}(\lambda) + 6 cp^{(2)}(\lambda) - \frac{9}{4} cp^{(1)}(\lambda).
\end{multline*}
\end{prop}

Here we omit the proof, which is essentially a long (but automatic) computation of the inductive form of $G_{(4)}$. Using Proposition~\ref{prop:conjugate-mu}, we also obtain an expression for $f^{\lambda / (1,1,1,1)}$, and, by Proposition~\ref{prop:young-lattice} applied to $\mu = (3)$ and $\mu = (1,1,1)$, we obtain expressions for $f^{\lambda / (3,1)}$ and $f^{\lambda / (2,1,1)}$. We can thus compute $\chi^{\lambda}_{(4,1^{n-4})}$ using Lemma~\ref{lem:character-as-skew-tableau}. The corresponding formula reads
\[
(n)_4 \chi^{\lambda}_{(4,1^{n-4})} / f^{\lambda} = 4 \sum_{w \in \lambda} (c(w))^3 + 4(2n-3) \sum_{w \in \lambda} 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^{\lambda / (2,2)}$ using Proposition~\ref{prop:young-lattice}, we can also obtain a counting proof for the character $\chi^{\lambda}_{(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.

\section{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~\ref{thm:mu-2} 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^{\lambda / \mu}$ for $\mu$ a hook. We conjecture that, in that case, our scheme will indeed always give a combinatorial proof for formulae for $f^{\lambda / \mu}$ of the type discussed in this article.

One of the difficulties of extension is that, for a general partition $\mu$, the corresponding function $G_{\mu}$ cannot always be so easily defined as in the case $\mu = (k)$ we treated here. However, for $\mu$ a hook, it seems to be possible to define $G_{\mu}$ by supposing that, in the successive incoming slides, the arm of $\mu$ is formed before the leg. However, for general $\mu$, the precise definition of $G_{\mu}$ 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~\ref{lem:skew-bijection}. Xiaomei Chen observed that, even for the hook $\mu = (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_{\mu}$ is important.

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

When passing from $f^{\lambda / \mu}$ to $\chi^{\lambda}_{\mu, 1^{n-k}}$, we notice that $\chi^{\lambda}_{\mu, 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.

\section*{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$.

\bibliographystyle{alpha}

\begin{thebibliography}{CGS04}

\bibitem[CGS04]{corteel2004content}
Sylvie Corteel, Alain Goupil, and Gilles Schaeffer.
\newblock Content evaluation and class symmetric functions.
\newblock {\em Adv. Math.}, 188(2):315--336, 2004.

\bibitem[DG89]{diaconis1989applications}
Persi Diaconis and Curtis Greene.
\newblock Applications of {M}urphy's elements.
\newblock Technical report, Department of statistics, Stanford University,
  1989.

\bibitem[Fro01]{frobenius1900charaktere}
Georg Frobenius.
\newblock {\em {\"U}ber die Charaktere der symmetrischen Gruppe}.
\newblock Berliner Berichte, 1901.

\bibitem[GJ08]{goulden2008kp}
Ian~P. Goulden and David~M. Jackson.
\newblock The {KP} hierarchy, branched covers, and triangulations.
\newblock {\em Adv. Math.}, 219(3):932--951, 2008.

\bibitem[Ing50]{ingram1950some}
Richard~E. Ingram.
\newblock Some characters of the symmetric group.
\newblock {\em Proc. Amer. Math. Soc.}, 1:358--369, 1950.

\bibitem[KO94]{kerov1994polynomial}
Sergey Kerov and Grigori~I. Olshanski.
\newblock Polynomial functions on the set of {Y}oung diagrams.
\newblock {\em C. R. Acad. Sci. Paris S\'er. I Math.}, 319(2):121--126, 1994.

\bibitem[Kra99]{krattenthaler1999another}
Christian Krattenthaler.
\newblock Another involution principle-free bijective proof of {S}tanley's
  hook-content formula.
\newblock {\em J. Combin. Theory Ser.~A}, 88(1):66--92, 1999.

\bibitem[Las08]{lassalle2008explicit}
Michel Lassalle.
\newblock An explicit formula for the characters of the symmetric group.
\newblock {\em Math. Ann.}, 340(2):383--405, 2008.

\bibitem[OO97]{okounkov1997shifted}
Andrei~Yu. Okounkov and Grigori~I. Olshanskii.
\newblock Shifted {S}chur functions.
\newblock {\em Algebra i Analiz}, 9(2):73--146, 1997.

\bibitem[Sag01]{sagan2001symmetric}
Bruce~E. Sagan.
\newblock {\em The symmetric group}, volume 203 of {\em Graduate Texts in
  Mathematics}.
\newblock Springer-Verlag, New York, second edition, 2001.

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

\bibitem[Sta99]{stanley2001enumerative}
Richard~P. Stanley.
\newblock {\em Enumerative combinatorics. {V}ol.~2}, volume~62 of {\em
  Cambridge Studies in Advanced Mathematics}.
\newblock Cambridge University Press, Cambridge, 1999.
\newblock With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

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

\end{thebibliography}

\end{document}
