%&latex
\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 (of shape
$\lambda)$.

\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 SYTs 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)$ whose set of entries is $\{1,2, \dots ,
2n\}$, and hence, by composing, to each other. We describe these
bijections. We leave it as pleasant exercises to the reader to
formally prove that these are indeed bijections, by proposing
inverse mappings, and proving that the compositions (in both
direction) yield the identity mapping in each case.

\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.

\medskip
{\bf Example of bijection (1).} Let $n=5$ and consider the
$2\times 5$ array
\begin{eqnarray*}
2,~4,~8,~9,~10\\ 1,~3,~5,~6,~7~
\end{eqnarray*}
Now $\{2,~4,~8,~9,~10\}\cap\{1,\ldots,5\}=\{2,4\}\to_{+1} \{3,5\}$
so the first row of the first tableau is $(1,3,5)$, hence
($n+1=6$) its first column is $(1,2,4,6)^T$.

\medskip
Also, $\{2,~4,~8,~9,~10\}\cap\{6,\ldots,10\}=\{8,9,10\}\to_{-4}
\{4,5,6\}$ so
 the first column of the second tableau is $(1,4,5,6)^T$, hence
 its first row is $(1,2,3)$. The pair of these two $(1,1)$-
 tableaux corresponds to the above array.

\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

\newpage
$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(2,0;2n)$.

\medskip
{\bf Example of bijection (2).} Again consider the same $2\times
5$ array as above, then the the bijection is as follows:

$\begin{array}{ccccccc}
2,4,8,9,10 &\rightarrow\  &1,2,4,8,9,10 &\rightarrow\  &3,5,6,7,8,9,10 & \rightarrow\ &1,3,5,6,7,8,9,10 \\
1,3,5,6,7~~ &  &3,5,6,7~~~~~~~   &  & 1,2,4~~~~~~~~~~~~~ &  & 2,4~~~~~~~~~~~~~~~~~~ \\
\end{array}$

\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}







Delete & Prev |  Delete & Next Move to: INBOX Drafts Sent Trash
sent-mail
