\documentclass[numbers=enddot,14pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=true]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{color}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{ytableau}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Saturday, March 29, 2025 21:27:20}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newcommand{\arinj}{\ar@{_{(}->}}
\newcommand{\arinjrev}{\ar@{^{(}->}}
\newcommand{\arsurj}{\ar@{->>}}
\newcommand{\arelem}{\ar@{|->}}
\newcommand{\arback}{\ar@{<-}}
\newcommand{\id}{\operatorname{id}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\DeclareMathOperator{\osc}{OSC}
\DeclareMathOperator{\rtb}{R2B}
\DeclareMathOperator{\uosc}{UOSC}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\green}[1]{\textcolor{green!50!black}{#1}}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{\node[shape=circle,fill,inner sep=2pt] (char) {\textcolor{white}{#1}};}}
\newcommand{\px}{\phantom{x}}
\newcommand{\icast}{\circled{$\ast$}}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{25cm}
\setlength\textwidth{15.5cm}
\newenvironment{noncompile}{}{}
\excludecomment{noncompile}
\ihead{The hook length formula (talk)}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{The hook length formula [talk slides]}
\date{Drexel University, 2025-01-09}
\author{Darij Grinberg}
\maketitle

\begin{abstract}
{\small We discuss the hook length formula and some related results.}

\end{abstract}

\section{The hook length formula}

\subsection{Recalling definitions}

\begin{itemize}
\item We follow the notations in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{the notes}.

\item Each partition $\lambda=\left(  \lambda_{1},\lambda_{2},\ldots
,\lambda_{k}\right)  $ has a Young diagram $Y\left(  \lambda\right)  $
associated to it:
\[%
\begin{tabular}
[c]{ccccccc}\cline{2-6}%
$\lambda_{1}$ cells: & \multicolumn{1}{|c}{\phantom{w}} &
\multicolumn{1}{|c}{\phantom{w}} & \multicolumn{1}{|c}{\phantom{w}} &
\multicolumn{1}{|c}{\phantom{w}} & \multicolumn{1}{|c}{\phantom{w}} &
\multicolumn{1}{|c}{\phantom{w}}\\\cline{2-6}%
$\lambda_{2}$ cells: & \multicolumn{1}{|c}{} & \multicolumn{1}{|c}{} &
\multicolumn{1}{|c}{} & \multicolumn{1}{|c}{} &  & \\\cline{2-4}%
$\lambda_{3}$ cells: & \multicolumn{1}{|c}{} & \multicolumn{1}{|c}{} &
\multicolumn{1}{|c}{} &  &  & \\\cline{2-3}%
$\vdots$ &  &  &  &  &  & \\\cline{2-2}%
$\lambda_{k}$ cells: & \multicolumn{1}{|c}{} & \multicolumn{1}{|c}{} &  &  &
& \\\cline{2-2}%
\end{tabular}
\
\]
If two partitions $\lambda$ and $\mu$ satisfy $Y\left(  \mu\right)  \subseteq
Y\left(  \lambda\right)  $ (or, short: $\mu\subseteq\lambda$), then the skew
Young diagram $Y\left(  \lambda/\mu\right)  $ is defined to be $Y\left(
\lambda\right)  \setminus Y\left(  \mu\right)  $.

\item Let $D$ be a diagram. A \emph{standard tableau} of shape $D$ is a
bijective filling of $D$ with the numbers $1,2,\ldots,n$ such that the entries
increase left-to-right along rows and top-to-bottom along columns.

\textbf{Examples:}%
\[%
\begin{tabular}
[c]{ccc}%
straight-shaped &  & skew-shaped\\
$\ytableaushort{137,24,56}$ &  & $\ytableaushort{\none \none356,\none24,17}$%
\end{tabular}
\ \
\]


\item We will only consider straight shapes $Y\left(  \lambda\right)  $ and
skew shapes $Y\left(  \lambda/\mu\right)  $ in this talk.

\item We say \textquotedblleft tableau of shape $\lambda$\textquotedblright%
\ instead of \textquotedblleft tableau of shape $Y\left(  \lambda\right)
$\textquotedblright.

Likewise for $\lambda/\mu$.

\item If $c$ is a cell of $Y\left(  \lambda\right)  $, then we define the
\emph{hook} $H_{\lambda}\left(  c\right)  $ of this cell in $\lambda$ to be
\begin{align*}
H_{\lambda}\left(  c\right)   &  :=\left\{  c\right\}  \cup\left\{  \text{all
cells of }Y\left(  \lambda\right)  \text{ due east of }c\right\} \\
&  \ \ \ \ \ \ \ \ \ \ \cup\left\{  \text{all cells of }Y\left(
\lambda\right)  \text{ due south of }c\right\}  .
\end{align*}
For example, if $\lambda=\left(  7,6,4,3\right)  $ and $c=\left(  2,3\right)
$, then $H_{\lambda}\left(  c\right)  $ is the set of all green cells here:%
\[
\ytableaushort{{\phantom{1}}{\phantom{1}}{\phantom{1}}{\phantom{1}}{\phantom{1}}{\phantom{1}}{\phantom{1}},
{\phantom{1}}{\phantom{1}}{*(green!60!black){\phantom{1}}}{*(green!60!black){\phantom{1}}}{*(green!60!black){\phantom{1}}}{*(green!60!black){\phantom{1}}},
{\phantom{1}}{\phantom{1}}{*(green!60!black){\phantom{1}}}{\phantom{1}},
{\phantom{1}}{\phantom{1}}{*(green!60!black){\phantom{1}}}}\ \ .
\]

\end{itemize}

\subsection{The hook length formula}

\begin{itemize}
\item \textbf{The hook length formula:} For any partition $\lambda$ of $n$, we
have%
\[
\left(  \text{\# of standard tableaux of shape }\lambda\right)  =\dfrac
{n!}{\prod_{c\in Y\left(  \lambda\right)  }\left\vert H_{\lambda}\left(
c\right)  \right\vert }.
\]


\item \textbf{Example:} If $\lambda=(3,2)$, then this becomes
\[
\left(  \text{\# of standard tableaux of shape }\left(  3,2\right)  \right)
=\frac{5!}{4\cdot3\cdot1\cdot2\cdot1}=5.
\]
{Here are the hooks of all five cells:
\[
\begin{ytableau}
*(green!60!black){\phantom{x}} & *(green!60!black){\phantom{x}} & *(green!60!black){\phantom{x}} \\
*(green!60!black){\phantom{x}} &
\end{ytableau}\quad\begin{ytableau}
\phantom{x} & *(green!60!black){\phantom{x}} & *(green!60!black){\phantom{x}}\\
\phantom{x} & *(green!60!black){\phantom{x}}
\end{ytableau}\quad\begin{ytableau}
\phantom{x} & & *(green!60!black){\phantom{x}} \\
\phantom{x} &
\end{ytableau}\quad\begin{ytableau}
\phantom{x} & & \\
*(green!60!black){\phantom{x}} & *(green!60!black){\phantom{x}}
\end{ytableau}\quad\begin{ytableau}
\phantom{x} & & \\
\phantom{x} & *(green!60!black){\phantom{x}}
\end{ytableau}
\]
} and here are the five standard tableaux:{
\[
\begin{ytableau} 1 & 2 & 3\\ 4 & 5 \end{ytableau}\quad
\begin{ytableau} 1 & 2 & 4\\ 3 & 5 \end{ytableau}\quad
\begin{ytableau} 1 & 2 & 5\\ 3 & 4 \end{ytableau}\quad
\begin{ytableau} 1 & 3 & 4\\ 2 & 5 \end{ytableau}\quad
\begin{ytableau} 1 & 3 & 5\\ 2 & 4 \end{ytableau}\ .
\]
}

\item \textbf{Example:} Let $\lambda=\left(  m,m\right)  $ (so that $n=2m$).
Then, the hook length formula becomes%
\begin{align*}
&  \left(  \text{\# of standard tableaux of shape }\left(  m,m\right)  \right)
\\
&  =\dfrac{\left(  2m\right)  !}{\left(  \left(  m+1\right)  m\left(
m-1\right)  \cdots2\right)  \cdot\left(  m\left(  m-1\right)  \left(
m-2\right)  \cdots1\right)  }\\
&  =\dfrac{1}{m+1}\dbinom{2m}{m}.
\end{align*}
Looks familiar? This is the $m$-th Catalan number $C_{m}$. And indeed, there
is a bijection to Dyck paths:%
\[
\begin{tikzpicture}[scale=0.8]
\draw(0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);
\fill
[green!60!black] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 0) -- (5, 1) -- (6, 0);
\filldraw(0, 0) circle [fill=red, radius=0.1];
\filldraw(1, 1) circle [fill=red, radius=0.1];
\filldraw(2, 2) circle [fill=red, radius=0.1];
\filldraw(3, 1) circle [fill=red, radius=0.1];
\filldraw(4, 0) circle [fill=red, radius=0.1];
\filldraw(5, 1) circle [fill=red, radius=0.1];
\filldraw(6, 0) circle [fill=red, radius=0.1];
\end{tikzpicture}\quad\longleftrightarrow\quad\ytableaushort{125,346}.
\]
%

\[
\begin{tikzpicture}[scale=0.8]
\draw(0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);
\fill
[green!60!black] (0, 0) -- (1, 1) -- (2, 2) -- (3, 1) -- (4, 2) -- (5, 1) -- (6, 0);
\filldraw(0, 0) circle [fill=red, radius=0.1];
\filldraw(1, 1) circle [fill=red, radius=0.1];
\filldraw(2, 2) circle [fill=red, radius=0.1];
\filldraw(3, 1) circle [fill=red, radius=0.1];
\filldraw(4, 2) circle [fill=red, radius=0.1];
\filldraw(5, 1) circle [fill=red, radius=0.1];
\filldraw(6, 0) circle [fill=red, radius=0.1];
\end{tikzpicture}\quad\longleftrightarrow\quad\ytableaushort{124,356}.
\]

\end{itemize}

\subsection{How not to prove the hook length formula}

\begin{itemize}
\item \textbf{The hook length formula:} For any partition $\lambda$ of $n$, we
have%
\[
\left(  \text{\# of standard tableaux of shape }\lambda\right)  =\dfrac
{n!}{\prod_{c\in Y\left(  \lambda\right)  }\left\vert H_{\lambda}\left(
c\right)  \right\vert }.
\]


\item Isn't this easy?

\begin{itemize}
\item There are $n!$ bijective fillings of $Y\left(  \lambda\right)  $ with
the numbers $1,2,\ldots,n$.

\item Such a filling is a standard tableau if and only if for each cell $c\in
Y\left(  \lambda\right)  $, the entry in cell $c$ is smaller than all other
entries in its hook $H_{\lambda}\left(  c\right)  $.%
\[
\text{e.g.:}%
\ \ \ \ \ \ \ \ \ \ \ytableaushort{{\phantom{1}}{\phantom{1}}{\phantom{1}}{\phantom{1}}{\phantom{1}}{\phantom{1}}{\phantom{1}},
{\phantom{1}}{\phantom{1}}a{b_1}{b_2}{b_3},
{\phantom{1}}{\phantom{1}}{b_4}{\phantom{1}},
{\phantom{1}}{\phantom{1}}{b_5}}\ \ \ \ \ \ \ a<b_{1},b_{2},b_{3},b_{4}%
,b_{5}.
\]
The probability for this is $\dfrac{1}{\left\vert H_{\lambda}\left(  c\right)
\right\vert }$.

\item Multiplying these probabilities over all cells $c$, we get $\dfrac
{1}{\prod_{c\in Y\left(  \lambda\right)  }\left\vert H_{\lambda}\left(
c\right)  \right\vert }$, thus the formula.
\end{itemize}

\item Alas, it is not this easy: The events are not independent, so we cannot
just multiply their probabilities. That we got the right result is a surprise
and needs proof!
\end{itemize}

\subsection{Some context}

\begin{itemize}
\item \textbf{Standard basis theorem} (Theorem 5.9.1 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{the notes}%
)\textbf{:} The Specht module $\mathcal{S}^{\lambda}:=\mathcal{S}^{Y\left(
\lambda\right)  }$ has a basis indexed by the standard tableaux of shape
$\lambda$.

\item Thus, the hook length formula gives the rank (= dimension) of this
Specht module.

\item Actually, the standard basis theorem holds for skew Young diagrams as
well, but the hook length formula does not apply to them.

\item This all is unnecessary to understand and prove the hook length formula.
But it is the very context in which tableaux were originally defined by Alfred
Young ca. 1902.
\end{itemize}

\subsection{Some history}

\begin{itemize}
\item Young never stated the hook length formula in its present form. What he
found was the following (1928):

\item \textbf{Young's quotient formula:} Let $\lambda=\left(  \lambda
_{1},\lambda_{2},\ldots,\lambda_{k}\right)  $ be any partition with
$\left\vert \lambda\right\vert =n$. Let $\ell_{i}:=\lambda_{i}+k-i$ for each
$i\in\left[  k\right]  $. Then, the \# of standard tableaux of shape $Y\left(
\lambda\right)  $ is%
\[
\dfrac{n!}{\ell_{1}!\cdot\ell_{2}!\cdot\cdots\cdot\ell_{k}!}\prod_{1\leq
i<j\leq k}\left(  \ell_{i}-\ell_{j}\right)  .
\]


\item He gave essentially two proofs.

\item One proof (1901--1928) is quite intricate, using Specht modules and long
computations with Young symmetrizers. The main idea is to expand the squared
Young symmetrizer $\mathbf{E}_{T}^{2}$ in two ways: once using the Young
symmetrizer theorem $\mathbf{E}_{T}^{2}=\dfrac{n!}{f^{\lambda}}\mathbf{E}_{T}$
(Theorem 5.11.3 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{the notes}), and
again by writing%
\[
\mathbf{E}_{T}^{2}=\nabla_{\operatorname*{Col}T}^{-}\nabla
_{\operatorname*{Row}T}\nabla_{\operatorname*{Col}T}^{-}\nabla
_{\operatorname*{Row}T}%
\]
and gradually \textquotedblleft dissolving\textquotedblright\ the inner
$\nabla_{\operatorname*{Col}T}^{-}$ factor by factoring it and cancelling
pieces of it against the adjacent $\nabla_{\operatorname*{Row}T}$ factors.

Note that Young knew the standard basis theorem and even some of the Garnir
relations, though his proof of the former was much more complicated.

A variant of this proof appears in \S 5.21 (last section of Chapter 5, in case
the numbering shifts) of
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{the notes}.

\item The other proof (1928) is pretty elementary, and I will sketch it.

\item The modern form of the hook length formula was found in 1953:

\begin{statement}
One Thursday in May of 1953,
\href{https://en.wikipedia.org/wiki/Gilbert_de_Beauregard_Robinson}{[Gilbert
de Beauregard] Robinson} was visiting
\href{http://sections.maa.org/michigan/newsletters/Fall97Newsletter/frame.html}{[James
Sutherland] Frame} at Michigan State University. Discussing the work of Staal
(a student of Robinson), Frame was led to conjecture the hook formula. At
first Robinson could not believe that such a simple formula existed, but after
trying some examples he became convinced, and together they proved the
identity. On Saturday they went to the University of Michigan, where Frame
presented their new result after a lecture by Robinson. This surprised
\href{https://en.wikipedia.org/wiki/Robert_M._Thrall}{[Robert McDowell]
Thrall}, who was in the audience, because he had just proved the same result
on the same day!

\textit{(Bruce Sagan)}
\end{statement}

\item This is perhaps less surprising once you realize that Young's quotient
formula was known by then, and the leap to the hook length formula was not
that large: you just need to show that%
\[
\dfrac{1}{\prod_{c\in Y\left(  \lambda\right)  }\left\vert H_{\lambda}\left(
c\right)  \right\vert }=\dfrac{1}{\ell_{1}!\cdot\ell_{2}!\cdot\cdots\cdot
\ell_{k}!}\prod_{1\leq i<j\leq k}\left(  \ell_{i}-\ell_{j}\right)  ,
\]
which can be done by induction on $k$ (removing the first row of $Y\left(
\lambda\right)  $).
\end{itemize}

\subsection{Proofs galore}

\begin{itemize}
\item The hook length formula is the quadratic reciprocity of algebraic
combinatorics: every text gives a proof. Quite a few of them are different: e.g.

\begin{itemize}
\item Young 1901--1928 using Young symmetrizers;

\item Young 1928 using rational functions (sketched below);

\item
\href{https://www-users.cse.umn.edu/~webb/oldteaching/Year2010-11/the-representation-theory-of-the-symmetric-groups-SLN.pdf}{James
1978} using determinants;

\item
\href{https://www2.math.upenn.edu/~wilf/website/Probabilistic proof.pdf}{Greene,
Nijenhuis, Wilf 1979} using discrete probability;

\item \href{https://www.math.ucla.edu/~pak/papers/bij.pdf}{Novelli, Pak,
Stojanovskii 1997} by an intricate (multi)bijection;

\item ...
\end{itemize}

See \S 11.2 in \href{https://arxiv.org/abs/2209.06142v1}{Igor Pak's
arXiv:2209.06142v1} for a partial taxonomy.
\end{itemize}

\subsection{Young's rational functions proof}

\begin{itemize}
\item Let me sketch Young's second proof, from his 1928 paper \textit{On
Quantitative Substitutional Analysis (Third Paper)}.

We shall prove Young's quotient formula; as we mentioned, the hook length
formula follows easily.

\item We let%
\begin{align*}
f^{\lambda}  &  :=\left(  \text{\# of standard tableaux of shape }%
\lambda\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
g^{\lambda}  &  :=\dfrac{n!}{\ell_{1}!\cdot\ell_{2}!\cdot\cdots\cdot\ell_{k}%
!}\prod_{1\leq i<j\leq k}\left(  \ell_{i}-\ell_{j}\right)  ,
\end{align*}
where $\lambda=\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)  $ is
a partition with $\left\vert \lambda\right\vert =n$, and where $\ell
_{i}:=\lambda_{i}+k-i$ for each $i\in\left[  k\right]  $.

Our goal is to show that $f^{\lambda}=g^{\lambda}$.

\item Assume at first that all rows of $Y\left(  \lambda\right)  $ have
distinct lengths, i.e., that%
\[
\lambda_{1}>\lambda_{2}>\cdots>\lambda_{k}.
\]


A standard tableau of shape $\lambda$ must have its entry $n$ in some cell
that is at the end of one of its rows, say the $i$-th row. Removing that cell
leaves us with a standard tableau of shape%
\[
\lambda-e_{i}:=\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{i-1}%
,\lambda_{i}-1,\lambda_{i+1},\lambda_{i+2},\ldots,\lambda_{k}\right)  .
\]%
\[%
\begin{array}
[c]{ccc}%
\lambda &  & \lambda-e_{i}\\
\begin{ytableau} \phantom{x} & \phantom{x} & \phantom{x} & \phantom{x} \\ \phantom{x} & \phantom{x} & n \\ \phantom{x} & \end{ytableau} &
\mapsto &
\begin{ytableau} \phantom{x} & \phantom{x} & \phantom{x} & \phantom{x} \\ \phantom{x} & \phantom{x} \\ \phantom{x} & \end{ytableau}
\end{array}
\]
This is a bijection. Thus,%
\[
f^{\lambda}=f^{\lambda-e_{1}}+f^{\lambda-e_{2}}+\cdots+f^{\lambda-e_{k}},
\]
which is a recursion for $f^{\lambda}$.

\item This is also true without the \textquotedblleft distinct
lengths\textquotedblright\ assumption, as long as we understand $f^{\lambda
-e_{i}}$ to be $0$ when $\lambda-e_{i}$ is not a partition (i.e., when
$\lambda_{i}=\lambda_{i+1}$). This makes perfect sense: The entry $n$ cannot
lie at the end of the $i$-th row in this case.%
\[%
\begin{array}
[c]{ccc}%
\lambda &  & \lambda-e_{i}\\%
\begin{array}
[c]{c}%
\begin{ytableau} \phantom{x} & \phantom{x} & \phantom{x} & \phantom{x} \\ \phantom{x} & \phantom{x} & n \\ \phantom{x} & \phantom{x} & \phantom{x} \end{ytableau}\\
\text{cannot happen}%
\end{array}
& \mapsto &
\begin{array}
[c]{c}%
\begin{ytableau} \phantom{x} & \phantom{x} & \phantom{x} & \phantom{x} \\ \phantom{x} & \phantom{x} \\ \phantom{x} & \phantom{x} & \phantom{x} \end{ytableau}\\
\text{not a partition}%
\end{array}
\end{array}
\]


\item If we can prove the same recursion for $g^{\lambda}$, that is,%
\[
g^{\lambda}\overset{?}{=}g^{\lambda-e_{1}}+g^{\lambda-e_{2}}+\cdots
+g^{\lambda-e_{k}},
\]
then we will be done by induction. So this recursion is our new goal. Note
that we keep trailing zeroes in our partition (e.g., we don't simplify
$\left(  3,2,0\right)  $ to $\left(  3,2\right)  $), so that $k$ remains fixed.

\item Expanding both sides of%
\[
g^{\lambda}\overset{?}{=}g^{\lambda-e_{1}}+g^{\lambda-e_{2}}+\cdots
+g^{\lambda-e_{k}}%
\]
using
\begin{align*}
g^{\lambda}  &  =\dfrac{n!}{\ell_{1}!\cdot\ell_{2}!\cdot\cdots\cdot\ell_{k}%
!}\prod_{1\leq i<j\leq k}\left(  \ell_{i}-\ell_{j}\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by definition}\right)  ;\\
g^{\lambda-e_{p}}  &  =\dfrac{\left(  n-1\right)  !}{\ell_{1}!\cdot\ell
_{2}!\cdot\cdots\cdot\ell_{p-1}!\cdot\left(  \ell_{p}-1\right)  !\cdot
\ell_{p+1}!\cdot\cdots\cdot\ell_{k}!}\\
&  \ \ \ \ \ \ \ \ \ \ \prod_{1\leq i<j\leq k}%
\begin{cases}
\ell_{i}-\ell_{j}, & \text{if }i,j\neq p;\\
\left(  \ell_{p}-1\right)  -\ell_{j}, & \text{if }i=p;\\
\ell_{i}-\left(  \ell_{p}-1\right)  , & \text{if }j=p,
\end{cases}
\ \ \ \ \ \ \ \ \ \ \left(  \text{likewise}\right)  ,
\end{align*}
we see that most factors cancel, and we are left with proving that%
\[
n\overset{?}{=}\sum_{p=1}^{k}\ell_{p}\left(  \prod_{j=p+1}^{k}\dfrac{\left(
\ell_{p}-1\right)  -\ell_{j}}{\ell_{p}-\ell_{j}}\right)  \left(  \prod
_{i=1}^{p-1}\dfrac{\ell_{i}-\left(  \ell_{p}-1\right)  }{\ell_{i}-\ell_{p}%
}\right)  .
\]
In view of $n=\sum_{p=1}^{k}\lambda_{p}=\sum_{p=1}^{k}\ell_{p}-\dbinom{k}{2}$,
this rewrites as%
\[
\sum_{p=1}^{k}\ell_{p}-\dbinom{k}{2}\overset{?}{=}\sum_{p=1}^{k}\ell
_{p}\left(  \prod_{j=p+1}^{k}\dfrac{\left(  \ell_{p}-1\right)  -\ell_{j}}%
{\ell_{p}-\ell_{j}}\right)  \left(  \prod_{i=1}^{p-1}\dfrac{\ell_{i}-\left(
\ell_{p}-1\right)  }{\ell_{i}-\ell_{p}}\right)  .
\]


\item This is an identity between rational functions in $\ell_{1},\ell
_{2},\ldots,\ell_{k}$. Thus, if it is to be true for all positive integers
$\ell_{1}>\ell_{2}>\cdots>\ell_{k}$, then it must be true for all $\ell
_{1},\ell_{2},\ldots,\ell_{k}\in\mathbb{C}$. This means that we can forget
what our $\ell_{1},\ell_{2},\ldots,\ell_{k}$ are and just focus on this
identity as an algebraic identity!

\item There are several ways to prove this identity. Here is Young's:

\item First combine the two products on the RHS:%
\[
\left(  \prod_{j=p+1}^{k}\dfrac{\left(  \ell_{p}-1\right)  -\ell_{j}}{\ell
_{p}-\ell_{j}}\right)  \left(  \prod_{i=1}^{p-1}\dfrac{\ell_{i}-\left(
\ell_{p}-1\right)  }{\ell_{i}-\ell_{p}}\right)  =\prod_{\substack{i\in\left[
k\right]  ;\\i\neq p}}\dfrac{\left(  \ell_{p}-1\right)  -\ell_{i}}{\ell
_{p}-\ell_{i}}.
\]
So we need to show that
\[
\sum_{p=1}^{k}\ell_{p}-\dbinom{k}{2}\overset{?}{=}\sum_{p=1}^{k}\ell_{p}%
\prod_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\dfrac{\left(  \ell
_{p}-1\right)  -\ell_{i}}{\ell_{p}-\ell_{i}}.
\]


\item Using the polynomial%
\[
f\left(  x\right)  :=\left(  x-\ell_{1}\right)  \left(  x-\ell_{2}\right)
\cdots\left(  x-\ell_{k}\right)  ,
\]
we can write
\[
\prod_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\dfrac{\left(  \ell
_{p}-1\right)  -\ell_{i}}{\ell_{p}-\ell_{i}}=-\dfrac{f\left(  \ell
_{p}-1\right)  }{\prod\limits_{\substack{i\in\left[  k\right]  ;\\i\neq
p}}\left(  \ell_{p}-\ell_{i}\right)  }.
\]
So we need to show that%
\[
\sum_{p=1}^{k}\ell_{p}-\dbinom{k}{2}\overset{?}{=}-\sum_{p=1}^{k}\ell
_{p}\dfrac{f\left(  \ell_{p}-1\right)  }{\prod\limits_{\substack{i\in\left[
k\right]  ;\\i\neq p}}\left(  \ell_{p}-\ell_{i}\right)  }.
\]


\item \href{https://arxiv.org/abs/2212.13624v2}{\textbf{Sylvester's identity}}
says that

\begin{itemize}
\item every polynomial $\Phi\in\mathbb{C}\left[  x\right]  $ of degree $<k-1$
satisfies%
\[
\sum_{p=1}^{k}\dfrac{\Phi\left(  \ell_{p}\right)  }{\prod
\limits_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\left(  \ell_{p}-\ell
_{i}\right)  }=0.
\]


\item slightly more generally: if $\Phi\in\mathbb{C}\left[  x\right]  $ is a
polynomial of degree $\leq k-1$, and if $\varphi_{k-1}$ is its $x^{k-1}%
$-coefficient, then%
\[
\sum_{p=1}^{k}\dfrac{\Phi\left(  \ell_{p}\right)  }{\prod
\limits_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\left(  \ell_{p}-\ell
_{i}\right)  }=\varphi_{k-1}.
\]


[\textit{Proof:} Lagrange interpolation says that%
\[
\sum_{p=1}^{k}\Phi\left(  \ell_{p}\right)  \dfrac{\prod\limits_{\substack{i\in
\left[  k\right]  ;\\i\neq p}}\left(  x-\ell_{i}\right)  }{\prod
\limits_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\left(  \ell_{p}-\ell
_{i}\right)  }=\Phi\left(  x\right)  .
\]
Compare coefficients before $x^{k-1}$.]
\end{itemize}

\item We cannot apply this to the polynomial
\begin{align*}
\Phi &  =xf\left(  x-1\right) \\
&  =x\left(  x-1-\ell_{1}\right)  \left(  x-1-\ell_{2}\right)  \cdots\left(
x-1-\ell_{k}\right)
\end{align*}
directly, since its degree is too large ($k+1$ rather than $\leq k-1$). But we
can instead apply it to the \textquotedblleft second-order
approximation\textquotedblright%
\[
\Phi:=x\left(  f\left(  x-1\right)  -f\left(  x\right)  +f^{\prime}\left(
x\right)  \right)  ,
\]
which is a polynomial of degree $\leq k-1$ because subtracting $f\left(
x\right)  -f^{\prime}\left(  x\right)  $ has cancelled the two highest terms
(cf. Taylor series: $f\left(  x-1\right)  =f\left(  x\right)  -f^{\prime
}\left(  x\right)  +\dfrac{1}{2}f^{\prime\prime}\left(  x\right)  -\dfrac
{1}{6}f^{\prime\prime\prime}\left(  x\right)  \pm\cdots$). Thus we get%
\[
\sum_{p=1}^{k}\dfrac{\ell_{p}\left(  f\left(  \ell_{p}-1\right)  -f\left(
\ell_{p}\right)  +f^{\prime}\left(  \ell_{p}\right)  \right)  }{\prod
\limits_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\left(  \ell_{p}-\ell
_{i}\right)  }=\varphi_{k-1}=\dfrac{k\left(  k-1\right)  }{2},
\]
since%
\[
f\left(  x-1\right)  -f\left(  x\right)  +f^{\prime}\left(  x\right)
=\dfrac{1}{2}f^{\prime\prime}\left(  x\right)  -\dfrac{1}{6}f^{\prime
\prime\prime}\left(  x\right)  \pm\cdots.
\]
Subtracting%
\begin{align*}
\sum_{p=1}^{k}\dfrac{-\ell_{p}f\left(  \ell_{p}\right)  }{\prod
\limits_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\left(  \ell_{p}-\ell
_{i}\right)  }  &  =0\ \ \ \ \ \ \ \ \ \ \left(  \text{since }f\left(
\ell_{p}\right)  =0\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\\
\sum_{p=1}^{k}\dfrac{\ell_{p}f^{\prime}\left(  \ell_{p}\right)  }%
{\prod\limits_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\left(  \ell
_{p}-\ell_{i}\right)  }  &  =\sum_{p=1}^{k}\ell_{p}\ \ \ \ \ \ \ \ \ \ \left(
\text{since }f^{\prime}\left(  \ell_{p}\right)  =\prod\limits_{\substack{i\in
\left[  k\right]  ;\\i\neq p}}\left(  \ell_{p}-\ell_{i}\right)  \right)  ,
\end{align*}
we obtain
\begin{align*}
\sum_{p=1}^{k}\ell_{p}\dfrac{f\left(  \ell_{p}-1\right)  }{\prod
\limits_{\substack{i\in\left[  k\right]  ;\\i\neq p}}\left(  \ell_{p}-\ell
_{i}\right)  }  &  =\dfrac{k\left(  k-1\right)  }{2}-0-\sum_{p=1}^{k}\ell
_{p}\\
&  =\dbinom{k}{2}-\sum_{p=1}^{k}\ell_{p}%
\end{align*}
and thus
\[
\sum_{p=1}^{k}\ell_{p}-\dbinom{k}{2}=-\sum_{p=1}^{k}\ell_{p}\dfrac{f\left(
\ell_{p}-1\right)  }{\prod\limits_{\substack{i\in\left[  k\right]  ;\\i\neq
p}}\left(  \ell_{p}-\ell_{i}\right)  },
\]
as desired.

\item We are almost done. We need to show that $f^{\lambda-e_{p}}%
=g^{\lambda-e_{p}}$ holds when $\lambda-e_{p}$ is not a partition. (This is
essentially the base case of our recursion, along with the easy case
$\lambda=\left(  0,0,\ldots,0\right)  $.)

This is easy: $f^{\lambda-e_{p}}=0$ by definition, whereas
\begin{align*}
g^{\lambda-e_{p}}  &  =\dfrac{\left(  n-1\right)  !}{\ell_{1}!\cdot\ell
_{2}!\cdot\cdots\cdot\ell_{p-1}!\cdot\left(  \ell_{p}-1\right)  !\cdot
\ell_{p+1}!\cdot\cdots\cdot\ell_{k}!}\\
&  \ \ \ \ \ \ \ \ \ \ \prod_{1\leq i<j\leq k}%
\begin{cases}
\ell_{i}-\ell_{j}, & \text{if }i,j\neq p;\\
\left(  \ell_{p}-1\right)  -\ell_{j}, & \text{if }i=p;\\
\ell_{i}-\left(  \ell_{p}-1\right)  , & \text{if }j=p,
\end{cases}
\\
&  =0
\end{align*}
since the factor for $\left(  i,j\right)  =\left(  p,p+1\right)  $ is $0$
(check it!).

\item Thus the proof of the hook length formula is complete.

\item This proof still keeps getting rediscovered: e.g.,
\href{https://web.archive.org/web/20231014121836/http://pds21.egloos.com/pds/201412/17/93/glass.ng.2004.pdf}{Glass
and Ng, \textit{A Simple Proof of the Hook Length Formula}, The American
Mathematical Monthly \textbf{111} (2004), pp. 700--704}. (With minor
variations: e.g., they use the residue theorem instead of Lagrange interpolation.)
\end{itemize}

\section{Naruse's skew hook length formula}

\subsection{The Young--Frobenius--Aitken determinant formula}

\begin{itemize}
\item Now what about skew shapes?%
\[
\left(  \text{\# of standard tableaux of shape }\lambda/\mu\right)  =\ ???
\]


\item \textbf{Example:} Let $\lambda/\mu=\left(  3,2\right)  /\left(
1\right)  $, so that%
\[
Y\left(  \lambda/\mu\right)  =\ydiagram{1+2,0+2}\ \ .
\]
Then,%
\[
\left(  \text{\# of standard tableaux of shape }\lambda/\mu\right)  =5.
\]
This is not $\dfrac{4!}{\text{an integer}}$, so don't expect any $\dfrac
{n!}{\prod}$-type formula any more.

\item For a long time, the best formula known was the
\textbf{Young--Frobenius--Aitken determinantal formula}%
\begin{align*}
&  \left(  \text{\# of standard tableaux of shape }\lambda/\mu\right) \\
&  =n!\cdot\det\left(  \dfrac{1}{\left(  \lambda_{i}-\mu_{j}-i+j\right)
!}\right)  _{i,j\in\left[  k\right]  },
\end{align*}
where $\lambda=\left(  \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)  $
and $\mu=\left(  \mu_{1},\mu_{2},\ldots,\mu_{k}\right)  $ and where we set
$\dfrac{1}{m!}:=0$ for $m<0$.

This goes back to Frobenius (1900) as a formula for $\dim\left(
\mathcal{S}^{\lambda/\mu}\right)  $ (at least for $\mu=\varnothing$), then
made combinatorial by Young (1935?) as he realized that $\mathcal{S}%
^{\lambda/\mu}$ has a standard tableau basis.

For a modern proof, see e.g. Theorem 5.6 in
\href{https://arxiv.org/abs/1408.4497v2}{Adin/Roichman, \textit{Enumeration of
Standard Young Tableaux}, arXiv:1408.4497v2} (also a lot more there).

Alternatively, if you know the Jacobi--Trudi formula for the Schur function
$s_{\lambda/\mu}$, you can evaluate it at $\underbrace{1,1,\ldots,1}_{k\text{
ones}},0,0,\ldots,0$ and consider the leading term as $k\rightarrow\infty$.
(The larger $k$ gets, the less likely is a semistandard tableau with entries
in $\left\{  1,2,\ldots,k\right\}  $ to have two equal entries!)

\item Recently, two formulas generalizing the hook length formula came into
existence. I will introduce the \textbf{Naruse hook length formula} (Naruse 2014).
\end{itemize}

\subsection{Excited diagrams}

\begin{itemize}
\item Let $D$ be any diagram.

\item An \emph{excited move} for a cell $c=(i,j)\in D$ means moving this cell
from $(i,j)$ to $(i+1,j+1)$.

This is allowed \textbf{only} if the three cells marked $\times$ in the
picture below (that is, $\left(  i+1,j\right)  ,\ \left(  i,j+1\right)
,\ \left(  i+1,j+1\right)  $) are not in $D$.
\[%
\begin{tabular}
[c]{cc}\cline{1-1}%
\multicolumn{1}{|c|}{$c$} & \multicolumn{1}{|c}{$\times$}\\\cline{1-1}%
$\times$ & $\times$%
\end{tabular}
\ \rightarrow%
\begin{tabular}
[c]{cc}%
$\times$ & $\times$\\\cline{2-2}%
$\times$ & \multicolumn{1}{|c|}{$c$}\\\cline{2-2}%
\end{tabular}
\
\]


\item \textbf{Examples:}%
\begin{align*}
\begin{ytableau} \phantom{x} & \phantom{x} &\phantom{x} \\ \phantom{x}& c \\ \phantom{x} \end{ytableau}
&  \longmapsto
\begin{ytableau} \phantom{x} & \phantom{x} &\phantom{x} \\ \phantom{x}\\ \phantom{x}&\none& c \end{ytableau}\ \ \ \ \ \ \ \ \ \ \text{allowed.}%
\\
&
\end{align*}%
\begin{align*}
\begin{ytableau} \phantom{x} & \phantom{x} &\phantom{x} \\ \phantom{x}& c &\phantom{x}\\ \phantom{x} \end{ytableau}
&  \not \longmapsto
\begin{ytableau} \phantom{x} & \phantom{x} &\phantom{x} \\ \phantom{x}&\none&\phantom{x}\\ \phantom{x}&\none& c \end{ytableau}\ \ \ \ \ \ \ \ \ \ \text{forbidden.}%
\\
&
\end{align*}%
\begin{align*}
\begin{ytableau} \phantom{x} & \phantom{x} &\phantom{x} \\ \phantom{x}& c \\ \phantom{x}&\phantom{x} \end{ytableau}
&  \not \longmapsto
\begin{ytableau} \phantom{x} & \phantom{x} &\phantom{x} \\ \phantom{x}&\none\\ \phantom{x}&\phantom{x}& c \end{ytableau}\ \ \ \ \ \ \ \ \ \ \text{forbidden.}%
\\
&
\end{align*}%
\[
\begin{ytableau}
\px & \px &\px \\ \px& c\\ \px&\none&\px
\end{ytableau}\not \longmapsto \begin{ytableau}
\px & \px &\px \\ \px&\none\\ \px&\none& c
\end{ytableau}\ \ \ \ \ \ \ \ \ \ \text{forbidden.}%
\]


\item An {\emph{excitation}} of a diagram $D$ is a diagram obtained from $D$
by a sequence of excited moves. (This sequence can be empty, so $D$ itself is
an excitation of $D$.)

\item \textbf{Example:} Start with $Y\left(  2,2,1\right)  $ and make some
excited moves:{%
\begin{align*}
\begin{ytableau} \phantom{x} & \phantom{x} \\ \phantom{x} & \phantom{x} \\ *(green!60!black)\phantom{x} & \none & \none & \none \end{ytableau}
&  \longmapsto
\begin{ytableau} \phantom{x} & \phantom{x} \\ \phantom{x} & *(green!60!black)\phantom{x} \\ \none \\ \none & \phantom{x} & \none & \none \end{ytableau}\longmapsto
\begin{ytableau} \phantom{x} & *(green!60!black)\phantom{x} \\ \phantom{x} \\ \none & \none & \phantom{x} \\ \none & \phantom{x} & \none & \none \end{ytableau}\\
& \\
& \\
&  \longmapsto
\begin{ytableau} \phantom{x} \\ \phantom{x} & \none & \phantom{x} \\ \none & \none & *(green!60!black)\phantom{x} \\ \none & \phantom{x} & \none & \none \end{ytableau}\longmapsto
\begin{ytableau} \phantom{x} \\ \phantom{x} & \none & \phantom{x} \\ \none \\ \none & \phantom{x} & \none & \phantom{x} \end{ytableau}\ \ ,
\end{align*}
so each of these five diagrams is an excitation of the first.}
\end{itemize}

\subsection{Naruse's skew hook length formula}

\begin{itemize}
\item \textbf{Naruse's skew hook length formula:} Let $\lambda$ and $\mu$ be
two partitions with $\mu\subseteq\lambda$ and $\left\vert Y\left(  \lambda
/\mu\right)  \right\vert =n$. Then,
\begin{align*}
&  \left(  \text{\# of standard tableaux of shape }\lambda/\mu\right) \\
&  =n!\sum_{\substack{E\text{ is an excitation of }Y\left(  \mu\right)
;\\E\subseteq Y\left(  \lambda\right)  }}\ \ \prod_{c\in Y\left(
\lambda\right)  \setminus E}\dfrac{1}{\left\vert H_{\lambda}\left(  c\right)
\right\vert }.
\end{align*}


\item \textbf{Example:} If $\lambda=(2,2,2)$ and $\mu=(1,1)$, then the $E$'s
in the sum are{%
\[
\begin{ytableau}
\ast &\\
\ast &\\
\phantom{x} & \\
\end{ytableau}\ ,\quad\begin{ytableau}
\ast &\\
\phantom{x} &\\
\phantom{x} & \ast\\
\end{ytableau}\ ,\quad\begin{ytableau}
\phantom{x} &\\
\phantom{x} & \ast\\
\phantom{x} & \ast\\
\end{ytableau}
\]
(where the cells in }$E$ are now marked with $\ast$s). {Thus,
\begin{align*}
&  \left(  \text{\# of standard tableaux of shape }\lambda/\mu\right) \\
&  =4!\cdot\left(  \frac{1}{3\cdot2\cdot1\cdot2}+\frac{1}{3\cdot2\cdot3\cdot
2}+\frac{1}{3\cdot2\cdot3\cdot4}\right) \\
&  =\dfrac{4!}{12}+\dfrac{4!}{36}+\dfrac{4!}{72}=2+\dfrac{2}{3}+\dfrac{1}%
{3}=3.
\end{align*}
}

\item Note that we are adding non-integers to get an integer. A strong sign
that this is a hard theorem!

\item History:

\begin{enumerate}
\item[\textbf{2014:}] Naruse states his formula in
\href{https://www.emis.de/journals/SLC/wpapers/s73vortrag/naruse.pdf}{a talk},
omitting the proof. Supposedly his proof uses algebraic geometry, which is
where the notion of excited diagrams originated.

\item[\textbf{2015--21:}] Morales, Pak and Panova write a series of four
papers (\href{https://arxiv.org/abs/1512.08348v5}{\#1},
\href{https://arxiv.org/abs/1610.04744}{\#2},
\href{https://arxiv.org/abs/1707.00931}{\#3},
\href{https://arxiv.org/abs/2108.10140}{\#4}) giving several proofs, which are
more combinatorial but still intricate and advanced.

\item[\textbf{2023:}] Grinberg, Korniichuk, Molokanov, Khomych (the latter
three are high school students at the time of writing) find a proof that is
completely elementary but very long
(\href{https://arxiv.org/abs/2310.18275}{arXiv:2310.18275}). This also proves
a \textquotedblleft weighted\textquotedblright\ generalization of the formula.

\item[\textbf{2024:}] Panova and Petrov publish two simpler proofs
(\href{https://arxiv.org/abs/2409.17842}{arXiv:2409.17842}) using a bit of
complex analysis and lattice methods.
\end{enumerate}

\item Excited diagrams are hard to work with. Each proof (I think) starts out
by re-encoding them as semistandard tableaux of shape $\mu$ satisfying certain conditions.
\end{itemize}

\section{More about counting standard tableaux}

\subsection{Classical formulas}

\begin{itemize}
\item Now we return to straight shapes $Y\left(  \lambda\right)  $.

\item For any partition $\lambda$, let $f^{\lambda}$ be the \# of standard
tableaux of shape $\lambda$.

\item \textquotedblleft$\lambda\vdash n$\textquotedblright\ is shorthand for
\textquotedblleft$\lambda$ is a partition of $n$\textquotedblright.

\item \textbf{Classical theorems (Young 1928 and Littlewood?):} Let
$n\in\mathbb{N}$. Then:

\textbf{(a)} We have%
\[
\sum_{\lambda\vdash n}\left(  f^{\lambda}\right)  ^{2}=n!=\left(  \text{\# of
all permutations }w\in S_{n}\right)  .
\]


\textbf{(b)} We have
\[
\sum_{\lambda\vdash n}f^{\lambda}=\sum_{k=0}^{n}\dfrac{\dbinom{n}{2k}%
\dbinom{2k}{k}k!}{2^{k}}=\left(  \text{\# of all involutions }w\in
S_{n}\right)  .
\]


\item Part \textbf{(a)} is Corollary 5.12.18 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{the notes}, where it
is proved using Young symmetrizers and the center of $\mathbf{k}\left[
S_{n}\right]  $.

Part \textbf{(b)} is Corollary 5.21.11 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{the notes}, where it
is proved using a bespoke basis of $\mathbf{k}\left[  S_{n}\right]  $.

\item But these are combinatorial identities, so can't we just prove them combinatorially?

\item Yes! Two ways:

\begin{itemize}
\item explicitly bijective via
\href{https://en.wikipedia.org/wiki/Robinson-Schensted-Knuth_correspondence}{the
\emph{Robinson--Schensted--Knuth correspondence}};

\item recursive via \textquotedblleft one-step bijections\textquotedblright.
\end{itemize}

Both are explained in
\href{http://wwwmathlabo.univ-poitiers.fr/~maavl/pdf/foata-fest.pdf}{Marc A.
A. van Leeuwen, \textit{The Robinson-Schensted and Sch\"{u}tzenberger
algorithms, an elementary approach}, 1996}. In a deeper sense, they are
equivalent, since the Robinson--Schensted--Knuth correspondence can be
assembled from the \textquotedblleft one-step bijections\textquotedblright.
\end{itemize}

\subsection{A proof sketch}

\begin{itemize}
\item Let me outline the second proof (\S 1 of
\href{http://wwwmathlabo.univ-poitiers.fr/~maavl/pdf/foata-fest.pdf}{van
Leeuwen's paper}).

\item If $\mu$ and $\lambda$ are two partitions, then the notation
\textquotedblleft$\mu\lessdot\lambda$\textquotedblright\ will mean
\textquotedblleft$Y\left(  \lambda\right)  =Y\left(  \mu\right)  \cup\left\{
\text{a single box not in }Y\left(  \mu\right)  \right\}  $\textquotedblright,
or equivalently \textquotedblleft$\mu\subseteq\lambda$ and $\left\vert
\lambda\right\vert =\left\vert \mu\right\vert +1$\textquotedblright.

\item \textbf{Example:}%
\[
\ydiagram{0+3,0+2}\ \lessdot\ \ydiagram{0+3,0+2,0+1}\ \lessdot
\ \ydiagram{0+4,0+2,0+1}\ \lessdot\ \ydiagram{0+4,0+2,0+2}\ \ .
\]


\item \textbf{Lemma A:} For any partition $\lambda$, we have%
\begin{align*}
&  \left(  \text{\# of partitions }\mu\text{ such that }\lambda\lessdot
\mu\right) \\
&  =\left(  \text{\# of partitions }\mu\text{ such that }\mu\lessdot
\lambda\right)  +1.
\end{align*}


\textbf{Proof idea:} We must prove that
\begin{align*}
&  \left(  \text{\# of ways to add a cell to }Y\left(  \lambda\right)  \text{
and get a partition}\right) \\
&  =\left(  \text{\# of ways to remove a cell from }Y\left(  \lambda\right)
\text{ and get a partition}\right)  -1.
\end{align*}
But the former and the latter ways \textquotedblleft
alternate\textquotedblright\ as you scan $Y\left(  \lambda\right)  $ from top
to bottom:%
\[%
%TCIMACRO{\TeXButton{tikz tableau}{\begin{tikzpicture}%
%[scale=0.7, rotate=+90, xscale=-1]
%\fill[green!60!black] (0,-10) -- (0,-11) -- (1,-11) -- (1,-10) -- cycle;
%\fill[red] (3,-10) -- (3,-9) -- (2,-9) -- (2,-10) -- cycle;
%\fill[green!60!black] (3,-6) -- (3,-7) -- (4,-7) -- (4,-6) -- cycle;
%\fill[red] (5,-6) -- (5,-5) -- (4,-5) -- (4,-6) -- cycle;
%\fill[green!60!black] (5,-3) -- (5,-4) -- (6,-4) -- (6,-3) -- cycle;
%\fill[red] (8,-3) -- (7,-3) -- (7,-2) -- (8,-2) -- cycle;
%\fill[green!60!black] (8,2) -- (9,2) -- (9,1) -- (8,1) -- cycle;
%\draw
%[thick] (0,2) -- (8,2) -- (8,-3) -- (5,-3) -- (5,-6) -- (3,-6) -- (3,-10) -- (0,-10) -- cycle;
%\end{tikzpicture}
%}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.7, rotate=+90, xscale=-1]
\fill[green!60!black] (0,-10) -- (0,-11) -- (1,-11) -- (1,-10) -- cycle;
\fill[red] (3,-10) -- (3,-9) -- (2,-9) -- (2,-10) -- cycle;
\fill[green!60!black] (3,-6) -- (3,-7) -- (4,-7) -- (4,-6) -- cycle;
\fill[red] (5,-6) -- (5,-5) -- (4,-5) -- (4,-6) -- cycle;
\fill[green!60!black] (5,-3) -- (5,-4) -- (6,-4) -- (6,-3) -- cycle;
\fill[red] (8,-3) -- (7,-3) -- (7,-2) -- (8,-2) -- cycle;
\fill[green!60!black] (8,2) -- (9,2) -- (9,1) -- (8,1) -- cycle;
\draw
[thick] (0,2) -- (8,2) -- (8,-3) -- (5,-3) -- (5,-6) -- (3,-6) -- (3,-10) -- (0,-10) -- cycle;
\end{tikzpicture}
%EndExpansion
\]
(green = addable cells;\qquad red = removable cells).

\item \textbf{Lemma B:} Given two partitions $\lambda\neq\nu$, we have%
\begin{align*}
&  \left(  \text{\# of partitions }\mu\text{ such that }\lambda\lessdot
\mu\text{ and }\nu\lessdot\mu\right) \\
&  =\left(  \text{\# of partitions }\mu\text{ such that }\mu\lessdot
\lambda\text{ and }\mu\lessdot\nu\right)  .
\end{align*}


\textbf{Proof idea:} If $\lambda$ and $\nu$ have the same size and differ in
only two boxes, then this is saying $1=1$. Otherwise, it is saying $0=0$.

\item \textbf{Lemma C:} For any nonempty partition $\lambda$, we have%
\[
\sum_{\mu\lessdot\lambda}f^{\mu}=f^{\lambda}.
\]


\textbf{Proof idea:} This is our old friend%
\[
f^{\lambda}=f^{\lambda-e_{1}}+f^{\lambda-e_{2}}+\cdots+f^{\lambda-e_{k}}.
\]


\item \textbf{Lemma D:} For any partition $\lambda$, we have%
\[
\sum_{\lambda\lessdot\mu}f^{\mu}=\left(  \left\vert \lambda\right\vert
+1\right)  f^{\lambda}.
\]


\textbf{Proof idea:} Combine Lemmas A, B and C and induct on $\left\vert
\lambda\right\vert $. The induction step in a bit more detail:%
\begin{align*}
\sum_{\lambda\lessdot\mu}f^{\mu}  & =\sum_{\lambda\lessdot\mu}\ \ \sum
_{\nu\lessdot\mu}f^{\nu}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma C}\right)
\\
& =f^{\lambda}+\sum_{\mu\lessdot\lambda}\ \ \sum_{\mu\lessdot\nu}f^{\nu
}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by comparing coefficients}\\
\text{in front of each }f^{\nu}\text{,}\\
\text{using Lemma A and Lemma B}%
\end{array}
\right)  \\
& =f^{\lambda}+\sum_{\mu\lessdot\lambda}\left(  \left\vert \mu\right\vert
+1\right)  f^{\mu}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by induction hypothesis for }\mu\text{,}\\
\text{since }\left\vert \mu\right\vert =\left\vert \lambda\right\vert -1
\end{array}
\right)  \\
& =f^{\lambda}+\sum_{\mu\lessdot\lambda}\left\vert \lambda\right\vert f^{\mu
}=f^{\lambda}+\left\vert \lambda\right\vert \sum_{\mu\lessdot\lambda}f^{\mu
}\\
& =f^{\lambda}+\left\vert \lambda\right\vert f^{\lambda}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma C}\right)  \\
& =\left(  \left\vert \lambda\right\vert +1\right)  f^{\lambda}.
\end{align*}


\item Now, setting%
\[
\sigma_{2}\left(  n\right)  =\sum_{\lambda\vdash n}\left(  f^{\lambda}\right)
^{2}\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \sigma_{1}\left(
n\right)  =\sum_{\lambda\vdash n}f^{\lambda},
\]
we easily find the recursions%
\begin{align*}
\sigma_{2}\left(  n\right)   &  =n\sigma_{2}\left(  n-1\right)
\ \ \ \ \ \ \ \ \ \ \text{and}\\
\sigma_{1}\left(  n\right)   &  =\sigma_{1}\left(  n-1\right)  +\left(
n-1\right)  \sigma_{1}\left(  n-2\right)  ,
\end{align*}
which lead to the explicit formulas $\sigma_{2}\left(  n\right)  =n!$ and
$\sigma_{1}\left(  n\right)  =\left(  \text{\# of all involutions }w\in
S_{n}\right)  $, qed.

\item The idea of this proof goes back to Rutherford, \textit{Substitutional
Analysis}, Edinburgh 1948, \S 15.
\end{itemize}


\end{document}