\documentclass[12pt,reqno]{article}
\usepackage{amssymb}
\usepackage
[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\usepackage{amsmath,amsthm,amssymb,color,epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newcommand\A{{\mathcal A}}
\newcommand\B{{\mathcal B}}
\newcommand\Y{{\mathcal Y}}
\newcommand\T{{\mathcal T}}
\title{{Y}oung tableaux and other mutually describing sequences}
\author{Zoran \v Suni\'k\\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small 810 Oldfather Hall, University of Nebraska\\[-0.8ex]
\small Lincoln, NE 68588-0323, USA\\[-0.8ex]
\small \texttt{zsunik@math.unl.edu}}
\date{\small Submitted: March 19, 2002; Accepted: June 3, 2002\\
\small MR Subject Classifications: 05A15, 11Y55}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
%\epsfxsize=4in
%\leavevmode\epsffile{logo0019.eps}
\vskip 1cm
{\LARGE\bf
Young tableaux and other mutually describing sequences}
\vskip 1cm
\large
Zoran \v Suni\'k\\
\vskip 0.5cm
Department of Mathematics and Statistics\\[-0.8ex]
810 Oldfather Hall, University of Nebraska\\[-0.8ex]
Lincoln, NE 68588-0323, USA\\[-0.8ex]
\vskip 0.5cm
{ \href{mailto:zsunik@math.unl.edu}{\tt zsunik@math.unl.edu} }
\vskip 1cm
\bf {Abstract}
\end{center}
{\em
We introduce a transformation on integer sequences for which the
set of images is in bijective correspondence with the set of Young
tableaux. We use this correspondence to show that the set of
images, known as ballot sequences, is also the set of double
points of our transformation.
In the second part, we introduce other transformations of integer
sequences and show that, starting from any sequence, repeated
applications of the transformations eventually produce a fixed
point (a self-describing sequence) or a double point (a pair of
mutually describing sequences).
}
\subsection*{Counting equal terms}
Let $\A^+$ be the set of finite integer sequences $a = a_1 a_2
\dots$ with $1 \leq a_i \leq i$, for all indices. Define a
transformation of sequences $\beta:\A^+ \to \A^+$ by
\[ \beta(a)_i = \# \{j \;|\; j\leq i,\; a_j=a_i\}. \]
Thus $\beta(a)_i$ counts the number of terms in the sequence $a$
that are equal to $a_i$ and appear in the initial segment of $a$
consisting of the first $i$ positions. Therefore, in some sense,
the sequence $\beta(a)$ describes the sequence $a$. It is easy to
see that the only fixed point of $\beta$ is the sequence $1$.
However, there are many double points, i.e., sequences $a$ for
which $\beta^2(a)=a$. If $a$ is a double point so is $b=\beta(a)$,
we have $a = \beta(b)$, and the sequences $a$ and $b$ mutually
describe each other.
\begin{theorem}\label{thm:young}
The set of double points of $\beta$ of length $n$ in $\A^+$
\begin{itemize}
\item[-]
corresponds bijectively to the set of Young tableaux of size $n$.
\item[-]
is the set of images of the sequences of length $n$ under $\beta$.
\item[-]
is the set of ballot sequences of length $n$, i.e., sequences $a$
of length $n$ such that, for every initial segment $a'$ of $a$ and
every positive integer $x$, the number of occurrences of the term
$x$ in $a'$ is no smaller than the number of occurrences of $x+1$.
\end{itemize}
\end{theorem}
By Young tableau of size $n$ we mean a standard Young tableau,
i.e., a left justified arrangement of the integers $1,2,\dots,n$ in
several rows of non-increasing length such that all rows and
columns have increasing terms (see \cite{sagan:ubiquitous}). For
example,
\begin{equation}\label{tableau}
\begin{matrix} 1 & 2 & 5 & 8 & 10 & 12\\
3 & 6 & 7 \\
4 & 9 & 11\\
13
\end{matrix}
\end{equation}
is a Young tableau of size $13$. Denote by $\Y_n$ the set of Young
tableaux of size $n$ and by $\B_n$ the set of ballot sequences of
length $n$.
We first remind the reader of a known bijective correspondence
between $\Y_n$ and $\B_n$ (see \cite[page 176]{sagan:symmetric}).
For a tableau $t$ in $\Y_n$ define a sequence $\sigma(t)$ of
length $n$ by
\[ \sigma(t)_i = \text{the number of the row in which }i\text{
appears in }t. \]
In other words, the entries in the first row of $t$ point to the
positions in the sequence $\sigma(t)$ whose value is $1$, the
entries in the second row point to the positions in $\sigma(t)$
whose value is $2$, etc. In the other direction, for a sequence $a
= a_1 a_2 \dots a_n$ in $\B_n$ define a tableau $\sigma'(a)$ by
\[ \sigma'(a)_{i,j} = \text{the position number of the }j\text{-th
occurrence of }i\text{ in }a . \]
Therefore, the first row of $\sigma'(a)$ consists of pointers, in
increasing order, to the positions in the sequence $a$ whose value
is $1$, the second row consists of pointers, in increasing order,
to the positions whose value is $2$, etc.
It is easy to see that, for every Young tableau $t$ in $\Y_n$ and
every ballot sequence $a$ in $\B_n$, $\sigma(t)$ is a ballot
sequence, $\sigma'(a)$ is a Young tableau, and $\sigma:\Y_n \to
\B_n$ and $\sigma':\B_n \to \Y_n$ are mutually inverse bijections.
For example, the table below gives the ballot sequence
$a=\sigma(t)$ that corresponds to the Young tableau $t$
in~(\ref{tableau}).
\[\begin{tabular}{c|ccccccccccccc}
$i$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\
\hline
$\sigma(t)_i$ & 1 & 1 & 2 & 3 & 1 & 2 & 2 & 1 & 3 & 1 & 3 & 1 & 4
\end{tabular}\]
\begin{lemma}
The restrictions of $\beta$ and $\sigma\tau\sigma'$ to the set
$\B_n$ of ballot sequences of length $n$ are equal, where $\tau$
is transposition of tableaux.
\end{lemma}
\begin{proof}
Let $a = a_1 a_2 \dots a_m \dots a_n$ be a sequence in $\B_n$ and
let $a_m=i$ be the $j$-th occurrence of $i$ in $a$. By definition,
\[ \beta(a)_m = j. \]
On the other hand, $\sigma'(a)_{i,j} = m$, the transposition then
gives $\tau\sigma'(a)_{j,i} = m$ and therefore
\[ \sigma\tau\sigma'(a)_m = j. \]
\end{proof}
Since $\tau$ acts as an involution on $\Y_n$, $\beta$ acts as an
involution on $\B_n$. Therefore, all ballot sequences are double
points of $\beta$. This also shows that all ballot sequences are
images under $\beta$. To prove Theorem~\ref{thm:young} it remains
to show that all images under $\beta$ are ballot sequences. This
is rather obvious. Indeed, the $x$-th occurrence of any term in
$a$ happens to the left of its $(x+1)$-th occurrence. Thus, in
every prefix of $b$ the number of occurrences of $x$ is no smaller
than the number of occurrences of $x+1$.
\subsection*{Other counts}
For the other transformations we have in mind it is more pleasant
to work with slightly different sequences than before. Let $\A$ be
the set of all finite integer sequences $a = a_0 a_1 a_2 \dots$
with $0 \leq a_i \leq i$, for all indices, and define $\A_n$ to be
the set of sequences $a = a_0 a_1 a_2 \dots a_n$ of length $n+1$
in $\A$.
\begin{theorem}
Consider the following six transformations of sequences in $\A$,
given by
\begin{align*}
\alpha_{eq}(a)_i &= \# \{j\;|\; j < i,\; a_j = a_i \},\\
\alpha_{neq}(a)_i &= \# \{j\;|\; j < i,\; a_j \neq a_i \},\\
\alpha_{geq}(a)_i &= \# \{j\;|\; j < i,\; a_j \geq a_i \},\\
\alpha_l(a)_i &= \# \{j\;|\; j < i,\; a_j < a_i \},\\
\alpha_{leq}(a)_i &= \# \{j\;|\; j < i,\; a_j \leq a_i \},\\
\alpha_g(a)_i &= \# \{j\;|\; j < i,\; a_j > a_i \}.
\end{align*}
Starting from any sequence in $\A$, each of these transformations
reaches a fixed or a double point after finitely many applications
of the transformation. The following table gives the type of
points that are reached, their number in $\A_n$ and a rough
estimate of the number of steps needed to reach such a point.
\[\begin{tabular}{c|ccc}
& type of points & number of points & steps needed\\
\hline
$\alpha_{eq}$ & double & $(n+1)$-th Young number & 1 \\
$\alpha_{neq}$ & fixed & $2^n$ & $O(n^2)$\\
$\alpha_{geq}$ & double & unknown, at least $2^n$ & $O(n^2)$\\
$\alpha_l$ & fixed & $(n+1)$-th Catalan number & $O(n^2)$ \\
$\alpha_{leq}$ & fixed & unique fixed point $012 \dots n$ & $O(n^2)$ \\
$\alpha_g $ & fixed & unique fixed point $000 \dots 0$ & $O(n)$ \\
\end{tabular}\]
The two transformations that have double points have the sequence
$0$ as their unique fixed point (which is counted as one double
point).
\end{theorem}
The proof is divided in six parts corresponding to the six
transformations.
\begin{proof}[Properties of $\alpha_{eq}$]
The assertions about $\alpha_{eq}$ follow from
Theorem~\ref{thm:young}. Indeed, the transformations $\alpha_{eq}$
and $\beta$ are conjugated by the bijection from $\A$ to $\A^+$
that adds 1 to each term of the sequences in $\A$.
\end{proof}
\begin{proof}[Properties of $\alpha_{neq}$]
We claim that the set of fixed points of $\alpha_{neq}$ in $\A_n$
is the set $\mathcal H_n$ that consist of the $2^n$ sequences $a =
a_0 a_1 \dots a_n$ with $a_i=i$ or $a_i=a_{i-1}$, for
$i=1,\dots,n$.
The set of sequences in $\A_n$ can be ordered lexicographically.
Namely, for $a= a_0 a_1 \dots a_n$ and $b=b_0 b_1 \dots b_n$, set
$a**a$, for sequences $a$ outside of $\mathcal H_n$.
The proof is done by induction on $n$.
The claims are easily verified for $n=0$ and $n=1$. Assume that
the claims are true for some $n \geq 1$.
Let
\[ a = a_0 a_1 \dots a_n x \]
be a sequence in $\mathcal H_{n+1}$. We consider two cases.
If $x=n+1$ then
\[ \# \{j\;|\; j < n+1,\; a_j \neq x \} =
\# \{j\;|\; j < n+1,\; a_j \neq n+1 \} = n+1 = x. \]
If $a_n = x$ then
\[ \# \{j\;|\; j < n+1,\; a_j \neq x \} =
\# \{j\;|\; j < n,\; a_j < a_n \} = a_n = x,\]
where the first equality comes from the fact that $a_n = x$ and
the second from the inductive assumption.
Thus all sequences in $\mathcal H_n$ are fixed under
$\alpha_{neq}$, for all $n$.
Now, let
\[ a = a_0 a_1 \dots a_n x \]
be a sequence in $\A_{n+1}$ that is not in $\mathcal H_{n+1}$. If
the proper initial segment
\[ a' = a_0 a_1 \dots a_n \]
is not fixed by $\alpha_{neq}$ we obtain the claim directly by the
inductive assumption. So let us assume that $a'$ is in $\mathcal
H_n$ but $a$ is not in $\mathcal H_{n+1}$.
We have
\[ \# \{j\;|\; j < n+1,\; a_j \neq x \} =
\# \{j\;|\; j < n,\; a_j \neq x \} + 1 \geq x + 1 ,\]
where the equality comes from the fact that $a_n \neq x$ and the
inequality follows from the inductive assumption. Note that we
could use the inductive assumption because $x \neq n+1$ and
therefore the sequence
\[ a''= a_0 a_1 \dots a_{n-1} x \]
is in $\A_n$.
Thus, for all $n$ and sequences $a$ in $\A_n$ but not in $\mathcal
H_n$, $\alpha_{neq}(a) > a$.
\end{proof}
\begin{proof}[Properties of $\alpha_{geq}$]
Define an \emph{extreme sequence} in $\A_n$ to be a sequence
$a=a_0a_1 \dots a_n$ such that, for all indices, $a_i=0$ or
$a_i=i$. There are $2^n$ extreme sequences in $\A_n$ and they are
all double points of $\alpha_{geq}$.
We prove by induction on $n$ that repeated applications of
$\alpha_{geq}$ to the sequences in $\A_n$ eventually produce
double points.
The statement is true for $n=0$ and $n=1$.
Assume that the statement is true for all sequences in $\A_n$.
Let
\[ a = a_0 a_1 \dots a_n x \]
be a sequence in $\A_{n+1}$. By the inductive hypothesis, we may
assume that the initial segment (prefix) $a_0 a_1 \dots a_n$ is
already a double point of $\alpha_{geq}$. Starting with the
sequence $a$, we apply $\alpha_{geq}$, $\alpha_{geq}^2$ and
$\alpha_{geq}^3$, etc., and obtain consecutively the sequences
\begin{gather*}
a_0 a_1 \dots a_n x \\
b_0 b_1 \dots b_n y \\
a_0 a_1 \dots a_n x' \\
b_0 b_1 \dots b_n y' \\
a_0 a_1 \dots a_n x'' \\
\dots
\end{gather*}
If $x' \geq x$ then
\[ \{j\;|\; j < n+1,\; a_j \geq x' \} \subseteq \{j < n+1 \;|\; a_j \geq x \}\]
and therefore
\[ y' = \# \{j\;|\; j < n+1,\; a_j \geq x' \} \leq
\# \{j\;|\; j < n+1,\; a_j \geq x\} = y. \]
By reversing the inequalities (including $\subseteq$) we also
obtain that
\[ x' \leq x \qquad \text{implies} \qquad y' \geq y. \]
Therefore, the infinite sequence $x,x',x'',\dots$ is either
non-increasing or non-decreasing and since it takes values in the
finite range between $0$ and $n+1$ it must stabilize after no more
than $n+1$ steps.
\end{proof}
\begin{proof}[Properties of $\alpha_l$]
This is proved in \cite{sunik:sds}. All fixed points of $\alpha_l$
can be organized in a certain rooted labelled tree (called Catalan
family tree) and the results follow from there.
\end{proof}
\begin{proof}[Properties of $\alpha_{leq}$]
If $012 \dots nx$ is a sequence with $x \neq n+1$ then
$\alpha_{leq}(012 \dots nx) = 012 \dots ny$, where $y=x+1$.
\end{proof}
\begin{proof}[Properties of $\alpha_g$]
If $0 \dots 0x$ is a sequence with $x \neq 0$ then $\alpha_g(0
\dots 0x) = 0 \dots 00$.
\end{proof}
As an example, we list the 10 double points of $\alpha_{geq}$ in
$\A_3$, namely the four extreme pairs
\[ 0000 \leftrightarrow 0123,\quad 0003 \leftrightarrow 0120,\quad
0020 \leftrightarrow 0103,\quad 0023 \leftrightarrow 0100\]
and the only additional pair
\[ 0021 \leftrightarrow 0101. \]
One can verify directly that the sequence that counts the number
of double points of $\alpha_{geq}$ in $\A_n$ starts as follows
\[ 1, 2, 4, 10, 26, 70, 216, \dots \]
This sequence (actually only the first several terms) was
submitted by the author to the On-Line Encyclopedia of Integer
Sequences \cite{sloane:online} on 06/24/2002 and it appears there
as the sequence
A071962.
It is a new sequence that could not be
found in the Encyclopedia before.
\subsection*{Concluding remarks}
We note that the six transformations we defined are actually three
pairs of transformations related by the \emph{mirror involution}
of $\A$, given by
\[ \mu(a)_i = i-a_i. \]
Indeed, $\alpha_{eq} = \mu \alpha_{neq}$, $\alpha_{geq} = \mu
\alpha_l$ and $\alpha_{leq} = \mu \alpha_g$. However, we did not
use this fact in our considerations. In particular, we did not
find a way to use it in order to count the double points of
$\alpha_{geq}$ by relating them somehow to the fixed points of
$\alpha_l$ counted by the Catalan numbers (see \cite{sunik:sds}).
It was observed by Louis Shapiro that the Catalan numbers, the
Young numbers and the powers of 2 count certain card shuffles in
the paper by Robbins and Boelker \cite{robbins-b:shuffle}, but the
author could not find a connection to the periodic points of the
sequence transformations introduced here.
One can easily define other sequence transformations that lead to
periodic points (one rather general way of producing such is by
using tree endomorphisms, as noted in \cite{sunik:sds}). Apart
from a precise description and enumeration of the periodic points,
one may also try to describe and enumerate the sequences on the
other side of the spectrum, namely the sequences that require
maximal number of steps before a periodic point is reached.
\subsection*{Acknowledgments}
Thanks to Richard Stanley and Louis Shapiro for their interest and
input. Thanks to the referee for the suggested improvements of the
text.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{amsalpha}
\begin{thebibliography}{{\v S}un02}
\bibitem[RB81]{robbins-b:shuffle}
D.~P. Robbins and E.~D. Bolker, The bias of three
pseudorandom shuffles, {\it Aequationes Math.} \textbf{22} (1981),
no.~2--3, 268--292.
\bibitem[Sag90]{sagan:ubiquitous}
Bruce~E. Sagan, The ubiquitous {Y}oung tableau, in {\it Invariant
Theory and Tableaux (Minneapolis, MN, 1988)}, Springer, New York,
1990, pp.~262--298.
\bibitem[Sag01]{sagan:symmetric}
Bruce~E. Sagan, {\it The Symmetric Group. Representations,
Combinatorial Algorithms, and Symmetric Functions}, second ed.,
Graduate Texts in Mathematics,
Vol.\ 203, Springer-Verlag, New York, 2001.
\bibitem[Slo]{sloane:online}
N.~J.~A. Sloane,
\texttt{http://www.research.att.com/\~{}njas/sequences/}.
\bibitem[SP95]{sloane-p:encyclopedia}
N.~J.~A. Sloane and Simon Plouffe, \emph{The Encyclopedia of
Integer Sequences}, Academic Press Inc., San Diego, CA, 1995.
\bibitem[{\v S}un02]{sunik:sds}
Zoran {\v S}uni{\'k}, Self-describing sequences and the
{C}atalan family tree, preprint, 2002.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: \ \
05A15, 05E10, 11Y55
\noindent \emph{Keywords: Young tableaux, periodic points}
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A071962}.)
\vspace*{+.1in}
\noindent
Received March 19, 2002;
revised version received June 28, 2002.
Published in Journal of Integer Sequences August 30, 2002.
\bigskip
\hrule
\bigskip
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\end{document}
**