Young tableaux and other mutually describing sequences

Zoran Šuniḱ

Department of Mathematics and Statistics 810 Oldfather Hall, University of Nebraska Lincoln, NE 68588-0323, USA

                     zsunik@math.unl.edu

Abstract

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

Counting equal terms

Let A^{+} be the set of finite integer sequences a = a_{1}a_{2} … with 1 ≤ a_{i} ≤ i, for all indices. Define a transformation of sequences β : A^{+} → A^{+} by

β(a)_{i} = #{j | j ≤ i, a_{j} = a_{i}}.

Thus β(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 β(a) describes the sequence a. It is easy to see that the only fixed point of β is the sequence 1. However, there are many double points, i.e., sequences a for which β^{2}(a) = a. If a is a double point so is b = β(a), we have a = β(b), and the sequences a and b mutually describe each other.

Theorem 1. The set of double points of β of length n in A^{+} - corresponds bijectively to the set of Young tableaux of size n.

- is the set of images of the sequences of length n under β.

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

By Young tableau of size n we mean a standard Young tableau, i.e., a left justified arrangement of the integers 1, 2, …, n in several rows of non-increasing length such that all rows and columns have increasing terms (see [Sag90]). For example,

1 2 5 8 10 12 3 6 7 4 9 11 13  (1)

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 [Sag01, page 176]). For a tableau t in Y_{n} define a sequence σ(t) of length n by

σ(t)_{i} = the number of the row in which i appears in t.

In other words, the entries in the first row of t point to the positions in the sequence σ(t) whose value is 1, the entries in the second row point to the positions in σ(t) whose value is 2, etc. In the other direction, for a sequence a = a_{1}a_{2} … a_{n} in B_{n} define a tableau σ′(a) by

σ′(a)_{i,j} = the position number of the j-th occurrence of i in a.

Therefore, the first row of σ′(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}, σ(t) is a ballot sequence, σ′(a) is a Young tableau, and σ : Y_{n} → B_{n} and σ′ : B_{n} → Y_{n} are mutually inverse bijections.

For example, the table below gives the ballot sequence a = σ(t) that corresponds to the Young tableau t in (1).

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ σ(t)_{i} & 1 & 1 & 2 & 3 & 1 & 2 & 2 & 1 & 3 & 1 & 3 & 1 & 4 \end{matrix}

Lemma 1. The restrictions of β and στσ′ to the set B_{n} of ballot sequences of length n are equal, where τ is transposition of tableaux.

Proof. Let a = a_{1}a_{2} … a_{m} … a_{n} be a sequence in B_{n} and let a_{m} = i be the j-th occurrence of i in a. By definition,

β(a)_{m} = j.

On the other hand, σ′(a)_{i,j} = m, the transposition then gives τσ′(a)_{j,i} = m and therefore

στσ′(a)_{m} = j.

Since τ acts as an involution on Y_{n}, β acts as an involution on B_{n}. Therefore, all ballot sequences are double points of β. This also shows that all ballot sequences are images under β. To prove Theorem 1 it remains to show that all images under β 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.

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} … with 0 ≤ a_{i} ≤ i, for all indices, and define A_{n} to be the set of sequences a = a_{0}a_{1}a_{2} … a_{n} of length n + 1 in A.

Theorem 2. Consider the following six transformations of sequences in A, given by

α_{eq}(a)_{i} = #{j | j < i, a_{j} = a_{i}},
α_{neq}(a)_{i} = #{j | j < i, a_{j} ≠ a_{i}},
α_{geq}(a)_{i} = #{j | j < i, a_{j} ≥ a_{i}},
α_{l}(a)_{i} = #{j | j < i, a_{j} < a_{i}},
α_{leq}(a)_{i} = #{j | j < i, a_{j} ≤ a_{i}},
α_{g}(a)_{i} = #{j | j < i, a_{j} > a_{i}}.

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.

type of points  number of points  steps needed
α_{eq}  double  (n + 1)-th Young number  1
α_{neq}  fixed  2^{n}  O(n^{2})
α_{geq}  double  unknown, at least 2^{n}  O(n^{2})
α_{l}  fixed  (n + 1)-th Catalan number  O(n^{2})
α_{leq}  fixed  unique fixed point 012 … n  O(n^{2})
α_{g}  fixed  unique fixed point 000 … 0  O(n)

The two transformations that have double points have the sequence 0 as their unique fixed point (which is counted as one double point).

The proof is divided in six parts corresponding to the six transformations.

Properties of α_{eq}. The assertions about α_{eq} follow from Theorem 1. Indeed, the transformations α_{eq} and β are conjugated by the bijection from A to A^{+} that adds 1 to each term of the sequences in A.

Properties of α_{neq}. We claim that the set of fixed points of α_{neq} in A_{n} is the set H_{n} that consist of the 2^{n} sequences a = a_{0}a_{1} … a_{n} with a_{i} = i or a_{i} = a_{i−1}, for i = 1, …, n.

The set of sequences in A_{n} can be ordered lexicographically. Namely, for a = a_{0}a_{1} … a_{n} and b = b_{0}b_{1} … b_{n}, set a < b if a_{i} < b_{i} at the first index where a and b differ.

The statement of the theorem then follows from the fact that α_{neq}(a) = a, for a in H_{n}, and α_{neq}(a) > a, for sequences a outside of 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 ≥ 1.

Let

a = a_{0}a_{1} … a_{n}x

be a sequence in H_{n+1}. We consider two cases.

If x = n + 1 then

#{j | j < n + 1, a_{j} ≠ x} = #{j | j < n + 1, a_{j} ≠ n + 1} = n + 1 = x.

If a_{n} = x then

#{j | j < n + 1, a_{j} ≠ 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 H_{n} are fixed under α_{neq}, for all n.

Now, let

a = a_{0}a_{1} … a_{n}x

be a sequence in A_{n+1} that is not in H_{n+1}. If the proper initial segment

a′ = a_{0}a_{1} … a_{n}

is not fixed by α_{neq} we obtain the claim directly by the inductive assumption. So let us assume that a′ is in H_{n} but a is not in H_{n+1}.

We have

#{j | j < n + 1, a_{j} ≠ x} = #{j | j < n, a_{j} ≠ x} + 1 ≥ x + 1,

where the equality comes from the fact that a_{n} ≠ x and the inequality follows from the inductive assumption. Note that we could use the inductive assumption because x ≠ n + 1 and therefore the sequence

a′′ = a_{0}a_{1} … a_{n−1}x

is in A_{n}.

Thus, for all n and sequences a in A_{n} but not in H_{n}, α_{neq}(a) > a.

Properties of α_{geq}. Define an extreme sequence in A_{n} to be a sequence a = a_{0}a_{1} … 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 α_{geq}.

We prove by induction on n that repeated applications of α_{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} … 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} … a_{n} is already a double point of α_{geq}. Starting with the sequence a, we apply α_{geq}, α_{geq}^{2} and α_{geq}^{3}, etc., and obtain consecutively the sequences

a_{0}a_{1} … a_{n}x
b_{0}b_{1} … b_{n}y
a_{0}a_{1} … a_{n}x′
b_{0}b_{1} … b_{n}y′
a_{0}a_{1} … a_{n}x′′
…

If x′ ≥ x then

{j | j < n + 1, a_{j} ≥ x′} ⊆ {j < n + 1 | a_{j} ≥ x}

and therefore

y′ = #{j | j < n + 1, a_{j} ≥ x′} ≤ #{j | j < n + 1, a_{j} ≥ x} = y.

By reversing the inequalities (including ⊆) we also obtain that

x′ ≤ x implies y′ ≥ y.

Therefore, the infinite sequence x, x′, x′′, … 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.

Properties of α_{l}. This is proved in [Šun02]. All fixed points of α_{l} can be organized in a certain rooted labelled tree (called Catalan family tree) and the results follow from there.

Properties of α_{leq}. If 012 … nx is a sequence with x ≠ n+1 then α_{leq}(012 … nx) = 012 … ny, where y = x + 1.

Properties of α_{g}. If 0 … 0x is a sequence with x ≠ 0 then α_{g}(0 … 0x) = 0 … 00.

As an example, we list the 10 double points of α_{geq} in A_{3}, namely the four extreme pairs

0000 ↔ 0123, 0003 ↔ 0120, 0020 ↔ 0103, 0023 ↔ 0100

and the only additional pair

0021 ↔ 0101.

One can verify directly that the sequence that counts the number of double points of α_{geq} in A_{n} starts as follows

1, 2, 4, 10, 26, 70, 216, …

This sequence (actually only the first several terms) was submitted by the author to the On-Line Encyclopedia of Integer Sequences [Slo] 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.

Concluding remarks

We note that the six transformations we defined are actually three pairs of transformations related by the mirror involution of A, given by

μ(a)_{i} = i − a_{i}.

Indeed, α_{eq} = μα_{neq}, α_{geq} = μα_{l} and α_{leq} = μα_{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 α_{geq} by relating them somehow to the fixed points of α_{l} counted by the Catalan numbers (see [Šun02]).

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 [RB81], 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 [Šun02]). 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.

Acknowledgments

Thanks to Richard Stanley and Louis Shapiro for their interest and input. Thanks to the referee for the suggested improvements of the text.

References

[RB81] D. P. Robbins and E. D. Bolker, The bias of three pseudorandom shuffles, Aequationes Math. 22 (1981), no. 2–3, 268–292.

[Sag90] Bruce E. Sagan, The ubiquitous Young tableau, in Invariant Theory and Tableaux (Minneapolis, MN, 1988), Springer, New York, 1990, pp. 262–298.

[Sag01] Bruce E. Sagan, The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, second ed., Graduate Texts in Mathematics, Vol. 203, Springer-Verlag, New York, 2001.

[Slo] N. J. A. Sloane, http://www.research.att.com/~njas/sequences/.

[SP95] N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press Inc., San Diego, CA, 1995.

[Šun02] Zoran Šuniḱ, Self-describing sequences and the Catalan family tree, preprint, 2002.

2000 Mathematics Subject Classification: 05A15, 05E10, 11Y55 Keywords: Young tableaux, periodic points

(Concerned with sequence \underline{A071962}.)

Received March 19, 2002; revised version received June 28, 2002. Published in Journal of Integer Sequences August 30, 2002.

Return to Journal of Integer Sequences home page.