<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\usepackage{tikz, enumitem}

\definecolor{SealGray}{HTML}{54585A}
\newcommand{\Ferrers}[2]{\begin{tikzpicture}[scale = #1]
    \foreach \x [count = \xi] in #2 \draw [color=SealGray!50] (0,\xi-1) grid (\x,\xi);
    \draw [SealGray, thick] (0,0) \foreach \x [count = \xi] in #2 {-| (\x,\xi)} -| cycle;
  \end{tikzpicture}}

\DeclareMathOperator{\sign}{sign}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}

\begin{center}
\vskip 1cm{\LARGE\bf
Matrix Representations From Labeled Trees
}
\vskip 1cm
\large
Charlie Liou and Anthony Mendes \\
Mathematics Department \\
California Polytechnic State University \\
San Luis Obispo, CA 93407\\
USA \\
\href{mailto: cbliou@calpoly.edu}{\tt cbliou@calpoly.edu}\\
\href{mailto: aamendes@calpoly.edu}{\tt aamendes@calpoly.edu}
\end{center}

\vskip .4 in

\begin{abstract}
  Let $X$ be the matrix representation induced by the action of the symmetric group on
  labeled trees with $n$ vertices.  We show that the number of times that the irreducible
  representation of the symmetric group corresponding to the integer partition $(n-1,1)$
  appears within $X$ is the number of unlabeled trees with certain conditions.
\end{abstract}

\vskip .4in

\section{Introduction}

Let $T_n$ be an ordered list of all labeled trees with $n$ vertices (the order in which
the trees are listed is arbitrary but fixed).  The symmetric group $S_n$ acts on the set
of labeled trees by permuting vertex labels.  In this way, the list $T_n$ is permuted by
applying $\sigma \in S_n$ to each element in $T_n$.  We let $X(\sigma)$ be the permutation matrix for
the permutation found by applying $\sigma$ to $T_n$.

For example, if $n = 5$ and the $5^3$ labeled trees on $5$ vertices are listed in
lexicographic order according to their Pr\"ufer codes, then the matrix representation $X$
sends the transposition $(1~2)$ to the matrix depicted below, where black square indicates
a $1$ and a white square a $0$:

\begin{center}
  \begin{tikzpicture}[scale = .05, yscale = -1]
    \draw[black!25] (1,1) rectangle (126,126);
    \foreach \x\y in {1/32, 2/31, 3/33, 4/34, 5/35, 6/27, 7/26, 8/28, 9/29, 10/30,
      11/37, 12/36, 13/38, 14/39, 15/40, 16/42, 17/41, 18/43, 19/44, 20/45, 21/47,
      22/46, 23/48, 24/49, 25/50, 26/7, 27/6, 28/8, 29/9, 30/10, 31/2, 32/1, 33/3,
      34/4, 35/5, 36/12, 37/11, 38/13, 39/14, 40/15, 41/17, 42/16, 43/18, 44/19,
      45/20, 46/22, 47/21, 48/23, 49/24, 50/25, 51/57, 52/56, 53/58, 54/59, 55/60,
      56/52, 57/51, 58/53, 59/54, 60/55, 61/62, 62/61, 63/63, 64/64, 65/65, 66/67,
      67/66, 68/88, 69/89, 70/90, 71/72, 72/71, 73/113, 74/114, 75/115, 76/82,
      77/81, 78/83, 79/84, 80/85, 81/77, 82/76, 83/78, 84/79, 85/80, 86/87, 87/86,
      88/68, 89/69, 90/70, 91/92, 92/91, 93/93, 94/94, 95/95, 96/97, 97/96, 98/118,
      99/119, 100/120, 101/107, 102/106, 103/108, 104/109, 105/110, 106/102,
      107/101, 108/103, 109/104, 110/105, 111/112, 112/111, 113/73, 114/74, 115/75,
      116/117, 117/116, 118/98, 119/99, 120/100, 121/122, 122/121, 123/123, 124/124,
      125/125}
    \draw[fill, black!75] (\x,\y) rectangle ++(1,1);
  \end{tikzpicture}
\end{center}

A {\it matrix representation\/} of degree $k$ for a finite group $G$ is a group homomorphism from
$G$ to the set of $k \times k$ invertible matrices over $\mathbb{C}$.  Since there are
$n^{n-2}$ labeled trees (see sequence \seqnum{A000272} in the
{\it On-Line Encyclopedia of Integer Sequences}), the function $X$ is a matrix
representation of degree $n^{n-2}$ for the symmetric group $S_n$.

If $A_1$ and $A_2$ are matrix representations (of any degree) of $G$,
then their {\it direct sum\/}
$A_1(g) \oplus A_2(g)$ is the block matrix
\[ \begin{bmatrix}A_1(g) &amp; 0 \\ 0 &amp; A_2(g) \end{bmatrix}, \] which is also a matrix
representation.  A matrix representation $R(g)$ is {\it reducible\/} if there is a constant matrix
$P$ and two matrix representations $A_1$ and $A_2$ such that
$R(g) = P (A_1(g) \oplus A_2(g)) P^{-1}$ for all $g \in G$.  A representation that is not
reducible is {\it irreducible}.  Every matrix representation can be expressed in the form
\[ P (A_1(g) \oplus A_2(g) \oplus \cdots \oplus A_k(g)) P^{-1}\] for all $g \in G$ where
$A_1,\dots,A_k$ are irreducible representations and $P$ is a fixed matrix.

In this paper we count the number of times certain irreducible representations appear within
the representation $X$.  In particular, the irreducible representations for the symmetric
group are indexed by the integer partitions of $n$, and our main result (Theorem
\ref{thm:main}) says that the number of times that the irreducible representation indexed
by the integer partition $(n-1,1)$ appears in $X$ is equal to the number of unlabeled
trees with a marked edge such that the trees on each side of the marked edge are
different.  This is sequence \seqnum{A217420}, which starts with
\begin{center}
  0, 0, 0, 1, 2, 6, 14, 37, 92, 239, 613, 1607, 4215, \dots
\end{center}
Along the way we find formulas for the number of times the trivial representation (the
representation corresponding with the integer partition $(n)$) and the sign representation
(the representation corresponding with the integer partition $(1^n)$) appear within $X$.

Parking functions are tangentially related to the topic at hand.  A 
{\it parking function\/} of
length $n$ is a word $w$ of length $n$ with letters in $\{1, \dots, n\}$ such that the
$i^{\rm th}$ largest integer in $w$ is not greater than $i$.  There are $(n+1)^{n-1}$ parking
functions of length $n$, and so the parking functions of length $n-1$ are in bijection
with labeled trees \cite{parking}.

An action of $S_n$ can be defined on the set of parking functions of length $n$ by
permuting positions.  Using a bijection that can turn parking functions into labeled
trees, this provides an action on labeled trees.  There are some known results about how
the corresponding matrix representation breaks into irreducible components (for example,
there are a Catalan number of copies of the trivial representation) \cite{MR3157798,
  Stanley}.  However, to clarify for those readers familiar with the literature on parking
functions, our group action is different and our results here are new.

We conclude this introduction by briefly recalling key theorems and concepts.  Readers
unfamiliar with the topic are pointed to the references \cite{Sagan}.

The {\it character\/} of the matrix representation $A(g)$, denoted $\chi^{A}(g)$, is the matrix trace
of $A(g)$ for all $g \in G$.  The {\it inner product\/} of their characters $\chi^A$ and $\chi^B$ is
\begin{equation*}
  \left \langle \chi^A , \chi^B \right \rangle
  = \frac{1}{|G|} \sum_{g \in G} \chi^A(g) \overline{\chi^B(g)}.
\end{equation*}
If $B$ is irreducible, then $\left \langle \chi^A , \chi^B \right \rangle$ gives the number of times
$B$ appears in $A$.

The characters of the irreducible representations of $S_n$ have a combinatorial
interpretation that involves
filling Young diagrams of integer partitions with rim
hooks.  The {\it Young diagram\/} for an integer partition
$\lambda = (\lambda_1, \lambda_2, \dots )$ is a is a collection of left-justified rows of boxes where row
$i$ has $\lambda_i$ boxes reading from top to bottom.

A {\it rim hook\/} of length $k$ is a sequence of $k$ connected cells in the Young diagram for
$\lambda$ that begins in a cell on the southeast boundary and travels up along the southeast
edge such that its removal leaves the Young diagram of a smaller integer partition.  A rim
hook tableau of shape $\lambda$ and filling $\mu$ is a iterative filling of the Young diagram of
the integer partition $\lambda$ with rim hooks of lengths found in the parts in $\mu$.  Below we
show both rim hook tableaux of shape $(8,1)$ with filling $(3,3,2,1)$:
\begin{center}
  \hfill
  \begin{tikzpicture}[scale = .6, yscale = -1,
    label/.style = {circle, draw, inner sep = 0.5pt, fill=white}]
    \foreach \x in {1,...,7} \draw[black!25, thin] (\x,0) -- ++(0,1);
    \draw[black!25, thin] (0,1) -- ++(1,0);
    \draw (0,0) -| (8,1) -| (1,2) -| cycle;
    \draw[rounded corners=3pt] (.5,1.5) |- (1.5,.5);
    \draw (2.5,.5) |- (4.5,.5);
    \draw (5.5,.5) |- (6.5,.5);
    \draw[fill] (.5,1.5) circle (2pt);
    \draw[fill] (2.5,.5) circle (2pt);
    \draw[fill] (5.5,.5) circle (2pt);
    \node[label] at (1.5,.5) {\small 1};
    \node[label] at (4.5,.5) {\small 2};
    \node[label] at (6.5,.5) {\small 3};
    \node[label] at (7.5,.5) {\small 4};
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}[scale = .6, yscale = -1,
    label/.style = {circle, draw, inner sep = 0.5pt, fill=white}]
    \foreach \x in {1,...,7} \draw[black!25, thin] (\x,0) -- ++(0,1);
    \draw[black!25, thin] (0,1) -- ++(1,0);
    \draw (0,0) -| (8,1) -| (1,2) -| cycle;
    \draw (.5,.5) |- (2.5,.5);
    \draw (3.5,.5) |- (5.5,.5);
    \draw (6.5,.5) |- (7.5,.5);
    \draw[fill] (.5,.5) circle (2pt);
    \draw[fill] (3.5,.5) circle (2pt);
    \draw[fill] (6.5,.5) circle (2pt);
    \node[label] at (2.5,.5) {\small 1};
    \node[label] at (5.5,.5) {\small 2};
    \node[label] at (7.5,.5) {\small 3};
    \node[label] at (.5,1.5) {\small 4};
  \end{tikzpicture}
  \hfill
  \mbox{}
\end{center}
The sign of a rim hook tableau is $(-1)^v$ where $v$ is the number of times a rim hook in
the tableau has a vertical step.  The signs of the above rim hook tableaux are $-1$ and
$1$, respectively.

The irreducible representations of $S_n$ are indexed by integer partitions of $n$, and the
character $\chi^\lambda$ corresponding to the integer partition $\lambda$ can be found using the
Murnaghan-Nakayama rule: if $\sigma \in S_n$ has cycle type $\mu$ (the cycle type of
$\sigma$ is the integer partition found by listing the lengths of $\sigma$ in cycle notation), then
\begin{equation}
  \label{eq:character}
  \chi^\lambda( \sigma ) = \sum_R \sign(R)
\end{equation}
where the sum ranges over all rim hook tableaux $R$ of shape $\lambda$ and filling $\mu$.  For
example, if $\sigma$ is a permutation with cycle type $(3,3,2,1)$, the two above rim hook
tableaux show that $\chi^{(8,1)}(\sigma) = 0$.

The sum in \eqref{eq:character} is unchanged if the order that the rim hooks in $\mu$ are
inserted into the Young diagram for $\lambda$ is permuted \cite{Mendes, White}.  For example, if
the rim hooks in the above example are inserted in the order $(2,3,3,1)$, then we find the
two rim hook tableaux of shape $(8,1)$ with filling $(2,3,3,1)$ with signed sum still
equal to $0$:
\begin{center}
  \hfill
  \begin{tikzpicture}[scale = .6, yscale = -1,
    label/.style = {circle, draw, inner sep = 0.5pt, fill=white}]
    \foreach \x in {1,...,7} \draw[black!25, thin] (\x,0) -- ++(0,1);
    \draw[black!25, thin] (0,1) -- ++(1,0);
    \draw (0,0) -| (8,1) -| (1,2) -| cycle;
    \draw (.5,1.5) |- (.5,.5);
    \draw (1.5,.5) |- (3.5,.5);
    \draw (4.5,.5) |- (6.5,.5);
    \draw[fill] (.5,1.5) circle (2pt);
    \draw[fill] (1.5,.5) circle (2pt);
    \draw[fill] (4.5,.5) circle (2pt);
    \node[label] at (.5,.5) {\small 1};
    \node[label] at (3.5,.5) {\small 2};
    \node[label] at (6.5,.5) {\small 3};
    \node[label] at (7.5,.5) {\small 4};
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}[scale = .6, yscale = -1,
    label/.style = {circle, draw, inner sep = 0.5pt, fill=white}]
    \foreach \x in {1,...,7} \draw[black!25, thin] (\x,0) -- ++(0,1);
    \draw[black!25, thin] (0,1) -- ++(1,0);
    \draw (0,0) -| (8,1) -| (1,2) -| cycle;
    \draw (.5,.5) |- (1.5,.5);
    \draw (2.5,.5) |- (4.5,.5);
    \draw (5.5,.5) |- (7.5,.5);
    \draw[fill] (.5,.5) circle (2pt);
    \draw[fill] (2.5,.5) circle (2pt);
    \draw[fill] (5.5,.5) circle (2pt);
    \node[label] at (1.5,.5) {\small 1};
    \node[label] at (4.5,.5) {\small 2};
    \node[label] at (7.5,.5) {\small 3};
    \node[label] at (.5,1.5) {\small 4};
  \end{tikzpicture}
  \hfill
  \mbox{}
\end{center}
A calculation with fewer rim hook tableaux can be had if we place the rim hooks in the
order $(1,2,3,3)$, since then there are no possible rim hook tableaux of shape $(8,1)$
with filling $(1,2,3,3)$, giving a signed sum of $0$.

\section{Results}

We begin with two easy facts about the number of times the trivial and the sign
representations appear in $X$.  Even though the proofs are routine, we record the results
here because similar ideas are used in Theorem \ref{thm:main}.  Beyond trees, Theorems
\ref{thm:trivial} and \ref{thm:sign} can be generalized in a straightforward manner to any
matrix representation defined from a group action.

\begin{theorem}
  \label{thm:trivial}
  The number of times the trivial representation appears in $X$ is the number of unlabeled
  trees on $n$ vertices.
\end{theorem}

\begin{proof}
  The number of times the trivial representation appears in $X$ is
  \begin{equation}
    \label{eq:burnside}
    \langle \chi^X, 1 \rangle = \frac{1}{n!} \sum_{\sigma \in S_n} \chi^X(\sigma).
  \end{equation}
  The value of the character $\chi^X$ on a permutation $\sigma$ is the trace of
  $X(\sigma)$, which is equal to the number of labeled trees fixed by $\sigma$.  Burnside's lemma
  now tells us that \eqref{eq:burnside} is the number of orbits under the group action of
  $S_n$ on labeled trees; in other words, the number of unlabeled trees.
\end{proof}

\begin{theorem}
  \label{thm:sign}
  The number of times the sign representation appears in $X$ is the number of unlabeled
  trees on $n$ vertices with no odd automorphisms.
\end{theorem}

\begin{proof}
  Since $\chi^X(\sigma)$ enumerates trees fixed by $\sigma$, the number of times the sign
  representation appears in $X$ is
  \begin{equation*}
    \label{eq:half}
    \langle \chi^X, \sign \sigma \rangle = \frac{1}{n!} \sum_{\sigma \in S_n} \chi^X(\sigma) \sign \sigma
    = \frac{1}{n!} \sum_{T} \sum_{\sigma \in \text{aut}(T)}  \sign \sigma
  \end{equation*}
  where the first sum is over all labeled trees $T$ on $n$ vertices and $\text{aut(T)}$ is
  the automorphism group for $T$.  Every subgroup of $S_n$ either does not contain an odd
  automorphism or exactly half of the subgroup contains odd automorphisms.  If there are
  no odd automorphisms, then the proof is complete using the same idea as the proof of
  Theorem \ref{thm:trivial}.  If exactly half of the subgroup is odd, then sum in
  \eqref{eq:half} is $0$, as needed.
\end{proof}

\begin{theorem}
  \label{thm:main}
  Let $m$ be the number of unlabeled trees on $n$ vertices with a marked edge such that
  the trees on each side of the marked edge are different.  The number of copies of the
  irreducible representation indexed by the integer partition $(n-1,1)$ in $X$ is equal to
  $m$.
\end{theorem}

\begin{proof}
  The number of times that the irreducible representation corresponding to $(n-1,1)$
  appears in $X$ is
  \begin{equation*}
    \langle \chi^X, \chi^{(n-1,1)} \rangle
    = \frac{1}{n!} \sum_{\sigma \in S_n}\chi^X(\sigma) \overline{\chi^{(n-1,1)}(\sigma)}
    = \frac{1}{n!} \sum_{T} \sum_{\sigma \in \text{aut}(T)} \sum_{R} \sign (R)
  \end{equation*}
  where the first sum is over all labeled trees $T$ on $n$ vertices, $\text{aut(T)}$ is
  the automorphism group for $T$ (expressed as a subgroup of $S_n$), and $R$ is a rim hook
  tableau of shape $(n-1,1)$ with filling the cycle type of $\sigma$.  So
  it is enough to prove that
  \begin{equation*}
    n! m = \sum_{T} \sum_{\sigma \in \text{aut}(T)} \sum_{R} \sign (R).
  \end{equation*}
  For this we define a sign-reversing involution $\vartheta$ on the set of signed triples
  of the form $(T, \sigma, R)$ where $T$ is a labeled tree, $\sigma \in \text{aut}(T)$,
  $R$ is a rim hook tableau of shape $(n-1,1)$ with filling the cycle type of $\sigma$, and the
  sign is the sign of $R$.  The number of fixed points under $\vartheta$ is $n! m$.

  Given $(T, \sigma, R)$, draw $T$ in the plane in the following way:
  \begin{enumerate}
  \item The center of $T$ is subgraph containing the vertices $v$ that minimize
    $\max_{w \in T} d(v,w)$ where $d(v,w)$ is the distance from $v$ to $w$.  The center of a
    tree is either a single vertex or a pair of adjacent vertices \cite{Jordan}.  Draw the
    center above all other vertices in $T$.  If the center of the tree contains two
    vertices, place the vertex with the smaller label on the left.
  \item Draw the remaining vertices in $T$ below this center in levels according to their
    distance to the center.  Write the children of each vertex in increasing order from
    left to right.
  \end{enumerate}
  For example, the following tree with $n = 19$ vertices is drawn in this way:
  \begin{center}
    \begin{tikzpicture}[yscale = .66, xscale = 1.33,
      label/.style = {inner sep = 2.5pt}]
      \node[label] (1) at (-3, 2.5) {\small 1};
      \node[label] (2) at (-2.5, -0.5) {\small 2};
      \node[label] (3) at (1, 2.5) {\small 3};
      \node[label] (4) at (1, -0.5) {\small 4};
      \node[label] (5) at (-3.5, 1) {\small 5};
      \node[label] (6) at (-1.5, 1) {\small 6};
      \node[label] (7) at (-2, 2.5) {\small 7};
      \node[label] (8) at (2, 2.5) {\small 8};
      \node[label] (9) at (2, -0.5) {\small 9};
      \node[label] (10) at (2, 1) {\small 10};
      \node[label] (11) at (-2.5, 1) {\small 11};
      \node[label] (12) at (-2, 4) {\small 12};
      \node[label] (13) at (-1, 2.5) {\small 13};
      \node[label] (14) at (-0.5, 1) {\small 14};
      \node[label] (15) at (-1.5, -0.5) {\small 15};
      \node[label] (16) at (3, -0.5) {\small 16};
      \node[label] (17) at (3, 2.5) {\small 17};
      \node[label] (18) at (2, 4) {\small 18};
      \node[label] (19) at (-0.5, -0.5) {\small 19};
      \foreach \x\y in {1/11, 1/5, 6/15, 6/2, 8/10, 10/16, 10/4, 10/9, 13/14,
        13/6, 14/19, 12/1, 12/13, 12/18, 12/7, 18/17, 18/3, 18/8}
      \draw[black!75] (\x) to (\y);
    \end{tikzpicture}
  \end{center}

  We can choose the order in which the lengths of the rim hooks are placed into $R$
  without affecting \eqref{eq:character}.  Place the rim hooks with lengths given by the
  cycle lengths of $\sigma$ in increasing order into $R$.  For example, if we take
  $\sigma = (2~~15)(3~~17)(5~~11)(4~~9~~16)$ to be the permutation in $S_{19}$ that fixes the
  above tree, then rim hooks of lengths $1,1,1,1,1,1,1,1,1,2,2,2,3$ are placed into the
  Young diagram of the integer partition $(18,1)$.  One possible choice for such an $R$ is
  here:
  \begin{center}
    \begin{tikzpicture}[scale = .6, yscale = -1,
      label/.style = {circle, draw, inner sep = 0.5pt, fill=white}]
      \foreach \x in {1,...,17} \draw[black!25, thin] (\x,0) -- ++(0,1);
      \draw[black!25, thin] (0,1) -- ++(1,0);
      \draw (0,0) -| (18,1) -| (1,2) -| cycle;
      \draw (9.5,.5) -- (10.5,.5);
      \draw (11.5,.5) -- (12.5,.5);
      \draw (13.5,.5) -- (14.5,.5);
      \draw (15.5,.5) -- (17.5,.5);
      \draw[fill] (9.5,.5) circle (2pt);
      \draw[fill] (11.5,.5) circle (2pt);
      \draw[fill] (13.5,.5) circle (2pt);
      \draw[fill] (15.5,.5) circle (2pt);
      \node[label] at (0.5,.5) {\small 1};
      \node[label] at (1.5,.5) {\small 2};
      \node[label] at (2.5,.5) {\small 3};
      \node[label] at (3.5,.5) {\small 4};
      \node[label] at (4.5,.5) {\small 5};
      \node[label] at (5.5,.5) {\small 6};
      \node[label] at (6.5,.5) {\small 7};
      \node[label] at (.5,1.5) {\small 8};
      \node[label] at (7.5,.5) {\small 9};
      \node[label] at (8.5,.5) {\small 10};
      \node[label] at (10.5,.5) {\small 11};
      \node[label] at (12.5,.5) {\small 12};
      \node[label] at (14.5,.5) {\small 13};
      \node[label] at (17.5,.5) {\small 14};
    \end{tikzpicture}
  \end{center}

  Beginning with the leftmost center vertex, order the vertices in $T$ by when they are
  first visited in a depth first search.  For example, the above tree produces the order
  \begin{equation*}
    12~~1~~5~~11~~7~~13~~6~~2~~15~~14~~19~~18~~3~~8~~10~~4~~9~~16~~17.
  \end{equation*}
  Sort the fixed points of $\sigma$ in this depth first order.  Using the above example for
  $\sigma$, the fixed points in $\sigma$ are
  \begin{equation*}
    12~~1~~7~~13~~6~~14~~19~~18~~8~~10.
  \end{equation*}

  If $\sigma$ has a fixed point, a rim hook of length $1$ with label $1$ is placed first in
  $R$.  This forces another rim hook of length $1$ to occupy the single cell in the second
  row of $R$.  Suppose the rim hook of length $1$ in the second row of $R$ has label $k$.
  Underline the $k^{\text{th}}$ fixed point in $\sigma$ to create $\sigma'$.  It is possible that
  $\sigma$ does not have any fixed points, in which case nothing is underlined.  In the above
  example we have $k = 8$, and so we underline the eighth fixed point in the depth first
  search order, namely $18$.  This gives
  \begin{equation*}
    \sigma' = (2~~15)(3~~17)(5~~11)(4~~9~~16)\underline{(18)}
  \end{equation*}

  From $T$ and $\sigma'$ we can reconstruct the triple $(T,\sigma,R)$.  If a fixed point is
  underlined in $\sigma'$, then the underlined element can be used to determine which rim hook
  appears in the second row of $R$. If there is not an underlined fixed point in
  $\sigma'$, then $\sigma$ cannot contain any fixed points at all.  In this case and only in this
  case, the rim hook tableau $R$ has sign $-1$ because its first rim hook spans the first
  two rows.

  Now we can describe the involution $\vartheta$ on pairs of the form $(T,\sigma')$:
  \begin{description}[font=\normalfont\itshape]
  \item[Case 1:] \textit{$\sigma'$ does not have a fixed point.}

    The sign of $R$ is negative here, and this is the only case that there can be a
    negative sign.

    Since $\sigma$ does not have a fixed point, the center of $T$ is not a single vertex
    (because automorphisms preserve the center) and the two trees on either side of the
    center are isomorphic.  Indeed, $\sigma$ acts on $T$ by interchanging the two vertices in
    the center, and thus must also interchange the trees on either side.  So, if $i$ and
    $j$ are the elements in the center of $T$, then the transposition $(i~~j)$ must be a
    cycle in $\sigma$.

    Let $\alpha$ be the lexicographically least element in the automorphism group for $T$ that
    does not fix the center; that is, $\alpha$ is the lexicographically least element that
    contains $(i~~j)$ as a cycle.  Define $\vartheta((T,\sigma')) = (T, \tau')$ where
    $\tau'$ is $\alpha \sigma$ with the larger of the two vertices in the center of $T$ underlined.
    This output is an object accounted for in Case 2.

  \item[Case 2:] \textit{The center of $T$ is two adjacent vertices, the two trees on
      either side of the center are isomorphic, and the underlined element in $\sigma'$ is
      appears in the center of $T$.}

    Because rim hooks are placed into $R$ by placing cycles of length $1$ first and since
    these one cycles are ordered according to the depth first search, the first rim hook
    inserted into $R$ corresponds to the smaller of the two vertices in the center.
    Therefore if an element in the center of $T$ is underlined in $\sigma$, then it is the
    larger of the two elements in the center that is underlined.

    Define $\vartheta((T,\sigma'))$ to be the inverse operation as in Case 1.  In particular,
    if $\alpha$ is the lexicographically least element in the automorphism group for $T$ that
    does not fix the center, then $\vartheta((T, \sigma')) = (T, \alpha^{-1} \sigma')$ where the
    underline is erased in $\alpha^{-1} \sigma'$.

  \item[Case 3:] \textit{Not Case 1 or Case 2.}

    If we are not in Case 1 or Case 2, then $T$ is not a tree with a center containing two
    adjacent vertices such that the trees on either side of the center are isomorphic.
    Further, the permutation $\sigma'$ must have a marked fixed point.  In this case we define
    $\vartheta((T,\sigma')) = (T,\sigma')$.
  \end{description}

  We now show that fixed points under $\vartheta$ are counted by $n! m$.

  Given $(T,\sigma')$ is fixed under $\vartheta$, mark the edge in $T$ that is traversed
  immediately before the underlined vertex in $\sigma'$ is visited in the depth first search to
  create $T'$.  The trees on each side of the marked edge in $T'$ are different by
  construction.  Our running example has vertex $18$ underlined, so the edge connecting
  $12$ and $18$ would be marked.

  We are now counting pairs $(T',\sigma)$ where $T'$ is a labeled tree with $n$ vertices, a
  marked edge, distinct trees on either side marked edge, and $\sigma$ is a permutation that
  fixes $T'$.  Using similar reasoning as in the proof of Theorem \ref{thm:trivial},
  Burnside's lemma says that the number of such pairs is $n! m$, as needed.
\end{proof}

\begin{thebibliography}{9}

\bibitem{MR3157798}
A.~Berget and B.~Rhoades, Extending the parking space, {\em J. Combin. Theory
  Ser. A} {\bf 123} (2014), 43--56.

\bibitem{Jordan}
C.~Jordan, Sur les assemblages de lignes, {\em J. Reine Angew. Math.} {\bf 70}
  (1869), 185--190.

\bibitem{Mendes}
A.~Mendes, The combinatorics of rim hook tableaux, {\em Australas. J. Combin.}
  {\bf 73} (2019), 132--148.

\bibitem{Sagan}
B.~Sagan, {\em The Symmetric Group: Representations, Combinatorial Algorithms,
  and Symmetric Functions}, Springer, 2001.

\bibitem{parking}
M.~P. Sch\"{u}tzenberger, On an enumeration problem, {\em J. Combinatorial
  Theory} {\bf 4} (1968), 219--221.

\bibitem{Stanley}
R.~P. Stanley, Parking functions and noncrossing partitions, {\em Electron. J.
  Combin.} {\bf 4} (2) (1997), \#R20.

\bibitem{White}
D.~W. Stanton and D.~E. White, A {S}chensted algorithm for rim hook tableaux,
  {\em J. Combin. Theory Ser. A} {\bf 40} (1985), 211--247.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary 05E10, Secondary 20C30.

\noindent \emph{Keywords:} labeled tree, group action, permutation matrix,
representation of the symmetric group.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000272} and
\seqnum{A217420}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 18 2023;
revised version received August 14 2023.
Published in {\it Journal of Integer Sequences}, August 15 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}
</pre></body></html>