\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 $aa$, 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}