\documentclass[twoside,12pt]{article}
\setlength{\textwidth}{16.5cm} \setlength{\textheight}{21.5cm}


\usepackage[all, 2cell, dvips]{xy}
\usepackage{latexsym,amsmath, amsfonts, graphics, epsf, epic}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsopn}
\usepackage{amscd}
%\usepackage[vcentermath,enableskew]{youngtab}
\usepackage{color}


\topmargin -1cm \oddsidemargin -.2cm \evensidemargin -.2cm
\pagestyle{empty}


\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{mlem}[thm]{Main Lemma}
\newtheorem{vnlem}[thm]{Von-Neumann's Lemma}
\newtheorem{defcor}[thm]{Definition/Corollary}
%
\theoremstyle{definition}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem{example}[thm]{Example}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exc}{Exercise}
\newtheorem{conjecture}[thm]{Conjecture}



%11111111111111111
\font\sym=msam10
\def\Vdash{\hbox{\sym\char'015}}






\parindent=0pt % paragraph indentation
\usepackage{amssymb}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\NN}{\mathbb N}
\def\QQ{\mathbb{Q}}
\def\FF{\mathbb{F}}
\def\CC{\mathbb{C}}
\def\Om{\Omega}


\def\om{\omega}
\def\tr{\mbox{\rm tr}}
\def\sg{\sigma}
\def\LL{\cal L}
\def\BB{\cal B}
\def\AA{\cal A}
\def\D{{\cal D}}
\def\lm{\lambda}
\def\lam{\lambda}
\def\KK{\cal K}
\def\dim{\mbox{\rm dim }}
\def\ins{\mbox{\rm ins}}
\def\al{\alpha}
\def\tl{T_{\lambda}}
\def\gm{\gamma}
\def\tm{T_{\mu}}
\def\l.l.o.{\it l.l.o}
\def\E{\eta}
\def\ep{\epsilon}
\def\eps{\varepsilon}
\def\f{\varphi}
\def\p{\psi}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\K{{\cal K}}
\def\BE{{\cal E}}
\def\C{{\cal C}}
\def\O{{\cal O}}
\def\R{{\cal R}}

\def \SST{{semi-standard tableau~}}%99999999999999999


\def\ctr#1{\hfill{#1}\hfill}
\def\hten{\hskip 10pt}
\def\medno{\medskip\noindent}
\def\sksix{\noalign{\vskip 6pt}}
\def\sstyle{\scriptstyle}
\def\half{{1\over 2}}
\def\quart{{1\over 4}}
\def\ol{\overline}
\def\wtil{\widetilde}
\def\gam{\gamma}
\def\pr{^{\prime}}
\def\ofmu{(\mu)}
\def\ofnu{(\nu)}
\def\sig{\sigma}
\def\ofsig{(\sig)}
\font\amsy=msbm10
\def\rline{\hbox{\amsy\char'122}}
\def\zline{\hbox{\amsy\char'132}}
\font\diff=msbm10
\def\leneq{\hbox{\diff\char'010}}
\def\geneq{\hbox{\diff\char'011}}
\font\sdiff=msbm5
\def\sleneq{\hbox{\sdiff\char'010}}
\font\goth=eufm10
\def\gothA{\hbox{\goth A}}
\def\notexists{\hbox{$\exists$\hskip -5pt / }}
\def\rslash{\delimiter"26E30F }
\def\lan{\langle}
\def\ran{\rangle}
\def\chiup{\raise 2pt\hbox{$\chi$}}
\def\rmpar{\hbox{par}}
\def\card{\hbox{card}}


%Math Abbreviation


\DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\End}{End}
\DeclareMathOperator{\sgn}{sgn}
%\DeclareMathOperator{\D}{Det}
\DeclareMathOperator{\Char}{char}
\DeclareMathOperator{\M}{\textsf{M}}
\DeclareMathOperator{\PW}{P^+(n,r)}
\DeclareMathOperator{\LW}{\Lambda^+}
\DeclareMathOperator{\W}{P^+(n,r)}


\def\GL{\mbox{\rm GL}}


\newcommand{\To}{\longrightarrow}
\newcommand{\id}{\rm{id}}
\DeclareMathOperator{\he}{\hat{e}}
\DeclareMathOperator{\hv}{\hat{v}}




\newcommand{\di}{\underline{i}}
\newcommand{\kk}{\underline{k}}
\newcommand{\db}{\underline{b}}
\newcommand{\da}{\underline{a}}
\newcommand{\jj}{\underline{j}}
\newcommand{\dk}{\underline{k}}
\newcommand{\dl}{\underline{l}}
\newcommand{\un}{\underline}
\newcommand{\ov}{\overline}
\newcommand{\ka}{{\kappa}}


\pagestyle{myheadings}


\newenvironment{pf}{\noindent \textit{Proof.}\,}{\hfill$\square$ \vskip5pt}




\title{Bijections for an identity of SYT}





\begin{document}


\centerline{\bf Bijections for an identity of Young Tableaux}

\medskip
\centerline{A. Regev and D. Zeilberger}

\bigskip
Recall that  {\it partition} $\lambda=(\lambda_1, \dots, \lambda_k)$ is a weakly-decreasing sequence 
of positive integers, and if $n=\lambda_1+ \dots + \lambda_k$ we say that $\lambda$ is a partition
of $n$ and write $\lm\vdash n$ and $l(\lambda)=k$.  For example $\lambda(3,3,2,2)$ is a partition
of $10$ and $l(\lambda)=4$.
\medskip
A convenient way to represent a partition $\lambda$ is via its {\it Ferrers} diagram, that consists
of $l(\lambda)$ left-justified lines of dots, such that the $i$-th row has $\lambda_i$
dots. If you replace the dots by empty boxes, you would get what is called a
{\it Young} diagram.
\medskip
Finally recall that a {\it standard Young Tableau} (SYT)  of shape $\lambda \vdash n$ 
is any way of placing the integers $\{1,2, \dots, n\}$ into the empty boxes of
the Young diagram in such a way that all the rows and all the columns are increasing.
For example $[[1,2,4,6],[3,5,7],[8,9]]$ is a SYT of shape $(4,3,2)$.
\medskip
Let $H(k,\ell;n)=\{\lm\vdash n\mid \lm_{k+1}\le \ell\}$ denote the
partitions of $n$ in the $(k,\ell)$ hook. For example, $H(k,0;n)$
are the partitions of $\lm\vdash n$ with $\ell(\lm)\le k$. Let
$f^\lm$ denote the number of standard Young tableaux (SYT) of
shape $\lm$. One then observes the following intriguing identity:
\[
\sum_{\mu\in H(1,1;n+1)} (f^\mu)^2=\sum_{\lm\in H(2,0;2n)}
f^\lambda.
\]
We give this identity a bijective proof by showing that both
\begin{eqnarray}\qquad\sum_{\mu\in H(1,1;n+1)} (f^\mu)^2,\end{eqnarray}
   \begin{eqnarray}\qquad\sum_{\lm\in H(2,0;2n)} f^\lambda,\end{eqnarray}
can be mapped {\it bijectively} to the set of row-increasing
matrices of shape $(n,n)$, and hence, by composing, to each other.
We describe these bijections.

\medskip
 The input for both (1)
 and (2)  is
a $2\times n$ matrix of integers

$a_1 \ldots a_n$

$b_1 \ldots b_n$

\medskip
such that $\{a_1,\ldots,a_n\} \cup \{b_1, \ldots
b_n\}=\{1,2,\ldots, 2n\}$,

\medskip
$a_1<a_2<...<a_n$ and

$b_1<b_2<...<b_n$.

\bigskip
{\bf Description of the bijection for} (1)

\medskip
Here the output is: Two  standard tableaux of the same
$(1,1)$-hook shape. Let

$|\{a_1, \ldots, a_n\}\cap \{1, \ldots, n\}|=k,$ so $\{a_1,
\ldots, a_n\}\cap \{1, \ldots, n\}=\{a_{i_1}<\cdots < a_{i_k}\}.$
%
%Denote by $k$ the cardinality
%\[|\{a_1, \ldots, a_n\}\cap \{1, \ldots, n\}|=k,\]
%so \[\{a_1, \ldots, a_n\}\cap \{1, \ldots, n\}=\{a_{i_1}<\cdots <
%a_{i_k}\}.\]
%
Form now a SYT in the $(1,1)$ hook as follows:

Its (first) row is \[~~1,~~a_{i_1}+1,~\cdots ~,a_{i_k}+1;\] its
(first) column is made of the remaining integers
\[
\{1,\ldots n+1\}\setminus \{~1,~a_{i_1}+1,~\cdots ~,a_{i_k}+1\}
=\{a'_{j_1},\ldots ,a'_{j_{n-k}}\} \]
%(\{a_1, \ldots, a_n\}\cap \{1, \ldots, n\})=\{a'_{j_1},\ldots
%,a'_{j_{n-k}} \}
 in increasing order. This gives the first SYT -- of $(1,1)$-hook shape
$(k+1,1^{n-k})$.




\bigskip

%Add one to each and put them in increasing order in the row of the
%$(1,1)$ hook (of course the corner has a 1 in it). Put all the
%other integers, in increasing order in the column.

It follows that
\[
|\{a_1,\ldots, a_n\} \cap \{n+1, \ldots, 2n\}|= n-k,
\]
so denote
\[
\{a_1,\ldots, a_n\} \cap \{n+1, \ldots, 2n\}=
\{b_{t_1}<\cdots<b_{t_{n-k}}\}.
\]
Since $n+1\le b_{t_1}$, hence $2\le b_{t_1}-(n-1)$. Form the
numbers \[1<b_{t_1}-(n-1)<\cdots<b_{t_{n-k}}-(n-1)\] and place
them, in that (increasing) order, in the column of the second
(1,1)-hook shape tableau, and the complement integers
\[\{1,\ldots,n+1\}\setminus
\{1,b_{t_1}-(n-1),\ldots,b_{t_{n-k}}-(n-1)\}
\]
 in
increasing order, in the row (after the corner 1). This gives the
second SYT -- again of shape $(k+1,1^{n-k})$. This map is clearly
a bijection.

\bigskip
{\bf Description of the bijection for} (2)

\medskip
Here the output is a SYT whose shape is a $\leq 2$-rowed partition
of $2n$ If for all $i~ a_i<b_i$, then it is a SYT, and do nothing
(the output is the input).

\medskip
Otherwise, let $i$ be the smallest index such that $a_i>b_i.$
Replace the above array by

\medskip
$b_1 ~\ldots~b_{i-1} ~~b_i~~~\,a_i ~~~~a_{i+1}~~~\ldots~~~~a_n$

$a_1~\ldots \,~a_{i-1} ~b_{i+1}~b_{i+2}~b_{i+3}~\ldots~b_n$




\medskip




If this is a SYT, then stop. Otherwise continue: Typically we
arrive at a two rows array

\medskip
$c_1,~\ldots~c_s~\ldots~c_r$

$d_1~\ldots~~d_s$

\medskip
with $s\le r,~~r+s=2n$, with $~c_1<\cdots<c_r$ and with
$d_1<\cdots<d_s$. If $c_j<d_j,$ $~j=1,\ldots,s$ ~~then this array
is SYT and we are done. Otherwise let $i$ be the smallest index
such that $c_i>d_i$, then replace the above array by

\medskip
$d_1~\ldots~d_{i-1}~~d_i~~~\;c_i~~~~c_{i+1}~\ldots
c_{s-1}~~\ldots~~~c_r$

$c_1~\ldots~c_{i-1}~~d_{i+1}~\;d_{i+2}~d_{i+3}~\ldots~d_s$

\medskip
Continue until a SYT is reached: thus the process stops at a SYT
of shape $\lm\in H(k,0;2n)$.

\medskip {\bf Remark.}
Let $\lm=(\lm_1,\lm_2,\ldots )$ be a partition,~~$\lm_1\ge
\lm_2\ge\ldots$ and denote

$\lm^{+1}=(\lm_1+1,\lm_2,\lm_3\ldots)$. The same bijections can be
applied to similar arrays of shape $(n+1,n)$, yielding a bijective
proof for the SYT identity
\[
\sum_{\mu\in H(2,0;2n+1)}f^\mu=\sum_{\lm\in H(1,1;n+2)}f^\lm\cdot
f^{\lm^{+1}}.
\]
%Then, first, we get the binomial identity
%\[
%\sum_{k=0}^{n+1}{n+2\choose k}{n+1\choose k}={2n+3\choose n+1}
%\]

\medskip {\bf Amitai Regev}, Department of Mathematics, The
Weizmann Institute of Science, Rehovot, Israel.
amitai.regev~at~weizmann.ac.il


\medskip

{\bf Doron Zeilberger}, Mathematics Department, Rutgers University
(New Brunswick), Piscataway, NJ, USA.
zeilberg~at~math.rutgers.edu .







\end{document}
