%A LaTeX2e file for 5 pages.
%Hook lengths in a skew Young diagram
%by Svante Janson
%file: sj122.tex
%Format: LaTeX
%Typeset with LaTeX2e and amsmath 

%Preamble
%Style section
\documentclass[11pt,reqno]{article}
\usepackage{amsmath,amsthm,latexsym}
\date{}
\textwidth 6in  %EJC  (152mm)
%\textheight 9in %EJC  (229mm)
%\addtolength{\headheight}{1.15pt}  % 12pt only
\hoffset=-0.5in

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 4 (1997), \#R24\hfill}

%Declaration section
%\theoremstyle{plain}
\newtheorem*{Th}{Theorem}

%Command section
\newcommand{\refF}[1]{Figure~\ref{#1}}
\def\rompar(#1){\textup(#1\textup)}    % usage: \rompar(...)
\renewcommand{\theenumi}{(\roman{enumi})}     % ger (i), (ii) osv.
\renewcommand{\labelenumi}{\theenumi}         % ger (i), (ii) osv.
\newcommand\RV{Regev and Vershik}
\newcommand\hl{hook length}
\newcommand\hls{\hl s}
\newcommand\Yd{Young diagram}
\newcommand\nmx{\ensuremath{n_1,\dots,n_m}}
\newcommand\nm{(\nmx)}
\newcommand\nmn{(\nmx;n)}
\newcommand\Dx{\ensuremath{D^*}}
\newcommand\ij{(i,j)}
\newcommand\set[1]{\{#1\}}
\newcommand\x{\times}

\begin{document}

\title{Hook lengths in a skew Young diagram}
\author{Svante Janson\\
{\small Department of Mathematics, Uppsala University}\\
{\small PO Box 480, S-751 06 Uppsala, Sweden}\\
{\small\texttt{svante.janson}@\texttt{math.uu.se}}}

\maketitle

\thispagestyle{empty}


\begin{center}
{\small Submitted: October 15, 1997; Accepted: October 20, 1997}
\end{center}

\vspace{15pt}

\begin{abstract}
\noindent\RV\ 
(Electronic J. Combinatorics {\bf4} (1997), \#R22)
have obtained some properties of the set of \hls\ for
certain skew \Yd{s},
using asymptotic calculations of character degrees.
They also conjectured a stronger form of one of their results.

\noindent We give a simple inductive proof of this conjecture.

\noindent Very recently, Regev and Zeilberger
(Annals of Combinatorics, to appear)
have independently proved this conjecture.
\end{abstract}


\section{Introduction}
\RV\ \cite{RV} have recently obtained some properties of the set of \hls\ for
certain skew \Yd{s}.
They prove the results using asymptotic calculations of the degrees of
certain sequences of characters of the symmetric group, and note that they
do not know a direct ``finite'' proof of their results.

The purpose of the present note is to present such a proof for one of their
results, viz.\ their Theorem 1.2.2.
Moreover, \RV's Theorem 1.2.2 states that two different sets
of \hls\ have the same product, and the authors conjecture that in fact
these two sets are equal.
(More precisely, the sets in question should be regarded as multisets,
i.e.\ the elements may have multiplicities.)
We prove this conjecture.

Very recently, Regev and Zeilberger \cite{RZ} have independently
proved this conjecture.

\section{Notation}
If $n_1\ge n_2 \ge\dots\ge n_m\ge0$ are integers, with $m\ge1$, let
$D=D\nm$ be the \Yd\ with rows of lengths \nmx.
Following (and slightly extending) \RV\ \cite{RV}, we introduce the following
definitions, see the examples in Figures \ref{fsq1} and ~\ref{fhl}.

$R=R(m,n)$ is an $m\times n$ rectangle, i.e.\ a \Yd\ with $m$ rows of equal
length $n$.

We assume that $n\ge n_1$ and that $R$ and $D$ are positioned such that their
top left corners coincide. Then $D\subseteq R$.
(\RV\ consider only the case when $R$ is the smallest rectangle containing
$D$, i.e.\ when $n=n_1$ and $n_m\ge1$. We find it convenient to treat a
slightly more general situation.)

\Dx\ is obtained by rotating $D$ a half turn about the center of $R$;
thus $\Dx\subseteq R$ and $R\setminus\Dx$ is a \Yd\ with rows of lengths
$n-n_m$, $n-n_{m-1}$,\dots, $n-n_{1}$.

$SQ=SQ\nmn$ is obtained from $R\setminus\Dx$ by adding two copies of $\Dx$,
one along the left edge and one along the top edge of $R$.


We will use a coordinate system with the $x$-axis directed upwards and the
$y$-axis directed to the left.
(Note that thus rows are numbered from the bottom to the top and columns from
the right to the left.)
We may then describe the skew diagrams as follows.
\begin{align*}
R(m,n)&=\set{\ij:1\le i\le m,\,1\le j\le n}\\
\Dx\nm&=\set{\ij:1\le i\le m,\,1\le j\le n_i}\\
SQ\nmn&=\set{\ij:1\le i\le m,\,n_i+1\le j\le n_i+n}\\
&\qquad\cup\set{\ij:m+1\le i\le 2m,\,1\le j\le n_{i-m}}.
\end{align*}

The \hl\ $h_A(x)$ of an element $x$ of a (skew) diagram $A$ is, as usual,
the number of elements of $A$ directly below or to the right of $x$,
including $x$ itself.
We define $H(A)$ to be the multiset $\set{h_A(x):x\in A}$.

\begin{figure}[hb]
\[
\begin{matrix}
 & & & & & & &\x\\
 & & & & & &\x&\x\\
 & & & &\x&\x&\x&\x\\
 & & &\x&\x&\x&\x&0\\
 & &\x&\x&\x&\x&0&0\\
\x&\x&\x&\x&0&0&0&0\\
\end{matrix}
\]
\caption{$\Dx(4,2,1)$ marked with 0; $SQ(4,2,1;4)$ marked with $\x$}
\label{fsq1}
\end{figure}

\begin{figure}
\[
\begin{array}[b]{cccccccc}
 & & & & & & &3\\
 & & & & & &4&2\\
 & & & &6&5&3&1\\
 & & &6&4&3&1& \\
 & &5&4&2&1& & \\
4&3&2&1& & & &
\end{array}
\qquad
\begin{array}[b]{cccc}
6&5&4&3\\
5&4&3&2\\
4&3&2&1
\end{array}
\qquad
\begin{array}[b]{cccc}
6&4&2&1\\
3&1& & \\
1& & &
\end{array}
\]
\caption{$SQ(4,2,1;4)$, $R(3,4)$ and $D(4,2,1)$ with \hls}\label{fhl}
\end{figure}

\section{Result}
\begin{Th}
Let $n\ge n_1\ge n_2\ge\dots\ge n_m\ge0$ \rompar($m\ge1$) be integers.
We then have the equality of multisets of \hls\
\begin{equation}\label{x}
H\bigl(SQ\nmn\bigr)=H\bigl(R(m,n)\bigr)\cup H\bigl(D\nm\bigr).
\end{equation}
\end{Th}

\begin{proof}
We say that $(n,n_1,\dots,n_m)$ is \emph{good} if \eqref{x} holds.
The result follows by double induction, in $m$ and $n_m$, from the
following three claims.
\begin{enumerate}
\item
If $n\ge n_1\ge0$, then $(n,n_1)$ is good.
\item
If $(n,n_1,\dots,n_m)$ is good, then $(n,n_1,\dots,n_m,0)$ is good.
\item
If $(n,n_1,\dots,n_m)$ is good and $n_{m-1}>n_m$,
then $(n,n_1,\dots,n_{m-1},n_m+1)$ is good.
\end{enumerate}

(i) is trivial: $SQ(n_1;n)$ consists of two rows with $n$ and $n_1$
elements, positioned such that their \hls\ are
%$(1,n_1+1),\dots,(1,n_1+n)$ and $(2,1),\dots,(2,n_1)$, with \hls\
$1,\dots,n$ and $1,\dots, n_1$, respectively, corresponding to the
\hls\ of $R(1,n)$ and $D(n_1)$.

For (ii), note that $SQ'=SQ(n_1,\dots,n_m,0;n)$ is obtained from
$SQ=SQ\nmn$ by inserting a new row $(m+1,1),\dots,(m+1,n)$, moving up
all elements $\ij$ with $i\ge m$; equivalently, $SQ'$ is obtained from $SQ$
by adding a new element on top of each column $1,\dots,n$.
Each of these new top elements has $m$ elements beneath it, and thus their
\hls\ are $m+1,\dots,m+n$.
Moreover, all elements in $SQ$ keep the same \hl\ in $SQ'$; consequently
$H(SQ')=H(SQ)\cup\set{m+1,\dots,m+n}$, see \refF{fii}.

\begin{figure}
\[
\begin{array}[b]{cccccccc}
 & & & & & & &4\\
 & & & & & &5&3\\
 & & & &7&6&4&2\\
 & & & &6&5&3&1\\
 & & &6&4&3&1& \\
 & &5&4&2&1& & \\
4&3&2&1& & & &
\end{array}
\qquad \qquad
\begin{array}[b]{cccc}
7&6&5&4\\
6&5&4&3\\
5&4&3&2\\
4&3&2&1
\end{array}
\]
\caption{Hook lengths in $SQ(4,2,1,0;4)$ and $R(4,4)$}\label{fii}
\end{figure}


For the right hand side of \eqref{x}, we observe that adding a new row of
length 0 does not change $D$, while $R=R(m,n)$ is changed to $R'=R(m+1,n)$,
which equals $R$ with an additional top row having \hls\ $m+1,\dots,m+n$.
Thus $H(R')=H(R)\cup\set{m+1,\dots,m+n}$.
Consequently, if $H(SQ)=H(R)\cup H(D)$, then $H(SQ')=H(R')\cup H(D)$ too,
which proves (ii).

For (iii) we let $SQ'=SQ(n_1,\dots,n_m+1;n)$
and $D'=D(n_1,\dots,n_m+1)$ (this time $R=R(m,n)$ stays the same),
and argue similarly.
$SQ'$ differs from $SQ$ in three places: the element $(m,n_m+1)$ is removed
while two new elements $(m,n_m+n+1)$ and $(2m,n_m+1)$ are added.
This affects only the \hls\ in row $m$ and in column $n_m+1$,
see \refF{fiii}.

\begin{figure}
\[
\begin{array}[b]{cccccccc}
 & & & & & &\ /4&3\\
 & & & & & &4/3&2\\
 & & & &6&5&3/2&1\\
 & &\ /6&6/5&4/3&3/2&1/\ & \\
 & &5&4&2&1& & \\
4&3&2&1& & & &
\end{array}
\qquad\qquad
\begin{array}[b]{cccc}
6&4/5&2&1\\
3&1/2& & \\
1/2&\ /1& &
\end{array}
\]
\caption{Hook lengths in $SQ(4,2,1;4)/SQ(4,2,2;4)$ and  $D(4,2,1)/D(4,2,2)$}
\label{fiii}
\end{figure}

The \hl\ $h_{SQ}(m,j)$ of an element in row $m$ in $SQ$ is
$j-n_m+m-k$ if $n_{k}<j\le n_{k-1}$ with $1<k\le m$, and
$j-n_m+m-1$ if $n_1<j\le n+n_m$; consequently
the \hls\ in row $m$ in $SQ$ are the numbers $1,\dots,n+m-1$
\emph{except} the $m-1$ numbers $n_k-n_m+m-k$, $k=1,\dots,m-1$.

The \hls\ in row $m$ in $SQ'$ are similarly
(by substituting $n_m+1$ for $n_m$)
the numbers $1,\dots,n+m-1$ except $n_k-n_m-1+m-k$, $k=1,\dots,m-1$.
The contributions from this row to the difference between $H(SQ)$ and
$H(SQ')$ is thus equivalent to adding the numbers $n_k-n_m+m-k$ and removing
the numbers $n_k-n_m+m-k-1$, $1\le k \le m-1$.

The \hls\ in column $n_m+1$ in $SQ$, not counting $(m,n_m+1)$ which is
already taken care of, are $n_m+2,\dots,n_m+m$, while the \hls\ in the same
column in $SQ'$ (which lies entirely above row $m$) are
$n_m+1,\dots,n_m+m$. The net effect of the changes in this column is thus
an addition of the number $n_m+1$.
Consequently, combining the effects in the row and the column,
\begin{equation}\label{sq3}
\begin{split}
H(SQ')=H(SQ)\cup\set{n_m+1}&\cup\set{n_k-n_m+m-k}_{k=1}^{m-1}\\
&\setminus\set{n_k-n_m+m-k-1}_{k=1}^{m-1}.
\end{split}
\end{equation}

For the right hand side of \eqref{x}, we observe that $D'$ differs from
$D$ in that a new element is added to the last row.
The \hls\ in this row in $D$ are $1,\dots,n_m$, while in $D'$ they are
$1,\dots,n_m+1$, a net addition of $n_m+1$.

The element above the new element in the $k$th row from top has \hl\ in $D$
$n_k-n_m+m-k-1$, while its \hl\ in $D'$ is increased by 1 to $n_k-n_m+m-k$.

No other \hls\ are affected, and consequently,
$$
H(D')=H(D)\cup\set{n_m+1}\cup\set{n_k-n_m+m-k}_{k=1}^{m-1}
\setminus\set{n_k-n_m+m-k-1}_{k=1}^{m-1}.
$$
Comparing this with \eqref{sq3}, we see
that if $H(SQ)=H(R)\cup H(D)$, then $H(SQ')=H(R)\cup H(D')$ too.
This completes the proof of (iii), and thus of the theorem.
\end{proof}

\begin{thebibliography}{9}

\bibitem{RV}
A. Regev and A. Vershik,
Asymptotics of Young diagrams and hook numbers.
\emph{Electron. J. Combin.}
{\bf4} (1997), \#R22, 12pp.

\bibitem{RZ}
A. Regev and D. Zeilberger,
Proof of a conjecture on multisets of hook numbers.
\emph{Ann. Combin.}, to appear.

\end{thebibliography}

\end{document}