Séminaire Lotharingien de Combinatoire 86 (2022), Article B86a

PERMUTATIONS WHOSE REVERSE SHARES THE SAME RECORDING TABLEAU IN THE RS CORRESPONDENCE

TUCKER J. ERVIN, BLAKE JACKSON, JAY LANE, KYUNGYONG LEE, SON DANG NGUYEN, JACK O’DONOHUE, AND MICHAEL VAUGHAN

Abstract. The RS correspondence is a bijection between permutations and pairs of standard Young tableaux with identical shape, where the tableaux are commonly denoted P (insertion) and Q (recording). It has been an open problem to demonstrate

|\{w ∈ 𝔖_{n} | Q(w) = Q(w^{r})\}| = \begin{cases}2^{\frac{n−1}{2}} \binom{n − 1}{\frac{n−1}{2}}, & n odd, \\ 0, & n even, \end{cases}

where w^{r} is the reverse permutation of w. First we show that for each w where Q(w) = Q(w^{r}) the recording tableau Q(w) has a symmetric hook shape and satisfies a certain simple property. From these two results, we succeed in proving the desired identity.

1. Introduction

The bijection known as the Robinson–Schensted (RS) correspondence was first described in 1938 by Robinson [2] as a method for proving the Littlewood–Richardson rule. In 1961, Schensted [4] gave a much simpler description of the algorithm, and it is the one we will use throughout our paper. Even though the two descriptions are very different, the correspondence usually credits both authors. Knuth [1] extended the RS correspondence in 1970 to one between non-negative integer matrices and semi-standard Young tableaux. The generalized bijection is referred to as the Robinson–Schensted–Knuth (RSK) correspondence. While Knuth’s formulation and results are important to the theory and have been widely used, we keep our focus solely on permutations, which we write using one line notation.

Given a permutation w, there are three operations we can perform: the reverse w^{r}, the complement w^{c}, and the inverse w^{−1}.

All authors were supported by the University of Alabama. KL was supported by the NSF grant DMS-2042786 and Korea Institute for Advanced Study.

2 T. J. ERVIN, B. JACKSON, J. LANE, K. LEE, S. D. NGUYEN, J. O’DONOHUE, AND M. VAUGHAN

Definition 1.1. Let w = w_{1} … w_{n} ∈ 𝔖_{n}. Then we define the reverse permutation w^{r} = w_{n} … w_{1}, the complement permutation w^{c} = (n + 1 − w_{1}) … (n + 1 − w_{n}), and the reversecomplement permutation w^{rc} = w^{cr} = (n + 1 − w_{n}) … (n + 1 − w_{1}).

There exist several relations between the recording and insertion tableaux of w and its image under the three operations. The insertion tableaux of w and w^{r} are transposes of each other, written as P (w) = P (w^{r})^{T} [3, Theorem 3.2.3]. Similarly, the recording tableaux are related by Q(w) = ϵ(Q(w^{r}))^{T} [3, Theorem 3.9.4], where ϵ is the evacuation map. Other relations exist with regards to the inverse and complement operations, such as P (w) = Q(w^{−1}), Q(w) = P (w^{−1}), P (w) = ϵ(P (w^{c}))^{T}, and Q(w) = Q(w^{c})^{T} [6, Theorem 4.1.1]. To summarize, the RS correspondence takes w and its images under the operations to the following:

RS(w) = (P (w), Q(w)),
RS(w^{c}) = (ϵ(P (w))^{T} , Q(w)^{T}),
RS(w^{r}) = (P (w)^{T} , ϵ(Q(w))^{T}),
RS(w^{rc}) = (ϵ(P (w)), ϵ(Q(w))),
RS(w^{−1}) = (Q(w), P (w)),
RS(w^{−1c}) = (ϵ(Q(w))^{T} , P (w)^{T}),
RS(w^{−1r}) = (Q(w)^{T} , ϵ(P (w))^{T}),
RS(w^{−1rc}) = (ϵ(Q(w)), ϵ(P (w))).

Every combination of the three operations reduces to one of the eight options above. This then brings up two interesting questions: what kind of and how many permutations have their recording tableaux fixed by these operations?

For the complement, there are no non-trivial permutations such that Q(w) = Q(w^{c}), as Q(w^{c}) = Q(w)^{T}. The only possible such permutation is 1 ∈ 𝔖_{1}. The set of permutations such that Q(w) = Q(w^{−1}) is the set of involutions of 𝔖_{n}. Its cardinality is given by ∑_{λ ⊢n} f^{λ}, where f^{λ} is the number of standard Young tableaux of shape λ. As Q(w) = Q(w^{−1c}) only when Q(w) = P (w)^{T}, its cardinality is the sum of all f^{λ′}, where λ′ is a shape of size n preserved by transposition. Additionally, it is straightforward to show that the sets of permutations where Q(w) = Q(w^{−1rc}) or Q(w) = Q(w^{−1r}) are respectively equal to the previous two sets under the reverse operation. This leaves only permutations which have fixed recording tableaux under the reverse and the reverse complement maps to count.

REVERSE PERMUTATIONS IN THE RS CORRESPONDENCE 3

The question of what permutations have fixed recording tableaux under the reverse map may have been posed previously, but we first encountered the problem when using Jeremy L. Martin’s “Lecture Notes on Algebraic Combinatorics” [5, Exercise 9.8(b)]. In this paper we describe and count the permutations, w, such that Q(w) = Q(w^{r}). Our main theorem is as follows.

Theorem 1.2. Let w ∈ 𝔖_{n}. Then Q(w) = Q(w^{r}) if and only if Q(w) satisfies both of the following properties:

• Q(w) has a symmetric hook shape,

• The element i in the first row of Q(w) implies that n − i + 2 belongs to the first

column of Q(w) for all i ∈ [n] with i > 1. In particular, we have the formula

|\{w ∈ 𝔖_{n} | Q(w) = Q(w^{r})\}| = \begin{cases}2^{\frac{n−1}{2}} \binom{n − 1}{\frac{n−1}{2}}, & n odd, \\ 0, & n even. \end{cases}

A forthcoming paper will attempt to answer Martin’s additional question of what permutations satisfy Q(w) = Q(w^{rc}).

As for the structure of this paper, Section 2 covers background, notation, and definitions needed throughout the paper. Section 3 introduces a family of maps Φ_{n} and a function θ_{n} which map symmetric groups to “neighboring” symmetric groups. These maps further allow us to prove Theorem 1.2 in Section 4. Acknowledgements. We thank Nick Loehr, Jeremy Martin, Bruce Sagan, and Richard Stanley for their correspondence and insight on earlier drafts. We also thank the anonymous referee for their detailed reports, which greatly improved the paper.

2. Background, Notation, and Definitions

As the RS correspondence is a bijection from permutations to standard Young tableaux, we begin by fixing our notation. Let [n] denote the set of letters 1, 2, …, n. We write permutations of [n] in one-line notation so that

𝔖_{n} = {w = w_{1} … w_{n} | {w_{1}, …, w_{n}} = [n]}.

In other words, w represents the permutation

σ = (\begin{matrix}1 & 2 & ⋯ & n \\ w_{1} & w_{2} & ⋯ & w_{n} \end{matrix}) .

4 T. J. ERVIN, B. JACKSON, J. LANE, K. LEE, S. D. NGUYEN, J. O’DONOHUE, AND M. VAUGHAN

A shape λ of size n, denoted λ ⊢ n, is a tuple λ = (λ_{1}, λ_{2}, …, λ_{k}) for some 1 ≤ k ≤ n such that ∑_{i=1}^{k} λ_{i} = n and λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k}. A Young diagram of shape λ is formed from left justified boxes, where the ith row from the top has λ_{i} empty boxes. We often refer to boxes or cells by their coordinates (i, j), where i and j respectively count the number of rows from the top and the number of columns from the left. For example, the shape λ = (3, 1, 1) gives us the Young diagram of shape λ:

.

We call any cell of a Young diagram whose removal would produce a smaller Young diagram an inner corner. The last cell in the top row and the first cell in the third row — located at coordinates (1, 3) and (3, 1) respectively — of the Young diagram above are inner corners.

A tableau T of shape λ is a filling of a Young diagram of shape λ with positive integers that is increasing left-to-right and top-to-bottom. The entry at cell (i, j) is denoted by T_{i,j}. If λ is of size n, then we say that a tableau of shape λ is of size n as well. When λ = (3, 1, 1), the following are all tableaux of shape λ:

1 2 3 4 5  1 2 6 4 7  1 3 4 2 5 .

In the case where a tableau is of size n and the filling uses each of the integers in [n] exactly once, we say that the tableau is a standard Young tableau. The previous example consists of two standard Young tableaux–the first and third. Finally, we denote the set of all standard Young tableaux of shape λ by SYT(λ). We can now describe the method by which we turn a permutation into a pair of standard Young tableaux.

Definition 2.1. Let T be a tableau and let x be a positive integer that is not already an entry of T. Then the Schensted insertion or row-insertion algorithm T ← x is defined as follows:

• If T = ∅, then T ← x = x .

• If x > u for all entries u in the top row of T, then append x to the end of the top row of T.

• Otherwise, find the leftmost entry u such that x < u. Replace u with x, and then perform the row-insertion with u in the subtableau consisting of the second and succeeding rows. In this case, we say x bumps u.

• Repeat until the bumping stops.

REVERSE PERMUTATIONS IN THE RS CORRESPONDENCE 5

To obtain the promised pair of standard Young tableaux, we let P (w) be the insertion tableau given by ((∅ ← w_{1}) ← w_{2}) ← ⋯ ← w_{n} and let the recording tableau Q(w) be the standard tableau of the same shape as P (w) that records where the new box appears in the underlying Young diagram at each step. The RS correspondence is the map w ↦ (P (w), Q(w)).

Example 2.2. Consider 52314 ∈ 𝔖_{5}. Step 1: The initial tableau is empty.

P = 5 Q = 1

Step 2: 2 bumps 5.

P = 2 5 Q = 1 2

Step 3: 3 appends to the first row.

P = 2 3 5 Q = 1 3 2

Step 4: 1 bumps 2, 2 bumps 5.

P = 1 3 2 5 Q = 1 3 2 4

Step 5: 4 appends to the first row.

P = 1 3 4 2 5 Q = 1 3 5 2 4

One can easily check that w = 52314 satisfies Q(w) = Q(w^{r}). We next define the evacuation process, beginning with the concept of a skew shape and skew tableau. A skew shape λ/μ is defined for any shapes λ and μ such that the Young diagram of shape μ is contained in the Young diagram of shape λ, i.e., we have μ_{i} ≤ λ_{i} for all i. If λ = μ, then λ/μ = ∅ is the diagram with no cells. Skew diagrams are given by the removal of the cells belonging to the diagram of shape μ from the diagram of shape λ. For example, if λ = (3, 1, 1) and μ = (2), the skew diagram of shape λ/μ is

.

A skew tableau is any tableau of skew shape λ/μ.

6 T. J. ERVIN, B. JACKSON, J. LANE, K. LEE, S. D. NGUYEN, J. O’DONOHUE, AND M. VAUGHAN

Definition 2.3 ([3, Definition 3.7.2]). A forward jeu de taquin slide of a skew tableau T of shape λ/μ is given by:

• Pick α to be an inner corner of μ. Note that if α does not share at least one cell of λ as a neighbor in λ/μ, then it must also be an inner corner of λ.

• While α is not an inner corner of λ do:

– Suppose that α = (i, j). As α is not an inner corner of λ, at least one of the cells (i + 1, j) and (i, j + 1) must exist in λ.

– If only the cell (i + 1, j) exists in λ, let α′ be the cell (i + 1, j). Similarly, if only the cell (i, j + 1) exists in λ, let α′ be the cell (i, j + 1).

– If both (i + 1, j) and (i, j + 1) exist in λ, let α′ be the cell of min{T_{i+l,j}, T_{i,j+1}}, where T_{i+1,j} and T_{i,j+1} are the fillings at cells (i+1, j) and (i, j+1) respectively.

– Slide T_{α′} into cell α and let α := α′. The resulting tableau is denoted j^{α}(T).

Definition 2.4 ([3, Definition 3.9.1]). For any tableau Q with distinct entries, let m be the minimal element of Q. Then the delta operator applied to Q yields a new tableau, ΔQ, given by performing the following steps:

• Erase m from its cell, α, in Q.

• Perform the slide j^{α} on the resultant tableau.

Definition 2.5 ([3, Definition 3.9.1]). For any standard Young tableau Q on n elements, we define the evacuation tableau, ϵ(Q), as the vacating tableau for the sequence

Q, ΔQ, Δ^{2}Q, …, Δ^{n}Q.

That is, the cell α of ϵ(Q) contains n − i if cell α was vacated when passing from Δ^{i}Q to Δ^{i+1}Q.

Again, we return to our previous example to demonstrate evacuation.

Example 2.6. Consider Q(52314), which was calculated in Example 2.2. Step 1: Cell (3,1) is vacated.

ΔQ = 2 3 5 4 ϵ(Q) = 5

Step 2: Cell (1,3) is vacated.

Δ^{2}Q = 3 5 4  ϵ(Q) = 4 5

Step 3: Cell (2,1) is vacated.

Δ^{3}Q = 4 5  ϵ(Q) = 4 3 5

Step 4: Cell (1,2) is vacated.

Δ^{4}Q = 5 ϵ(Q) = 2 4 3 5

Step 5: The final cell (1,1) is vacated.

Δ^{5}Q = ∅ ϵ(Q) = 1 2 4 3 5

Immediately, we see that ϵ(Q(w))^{T} = Q(w) for w = 52314, as expected from Q(w) = Q(w^{r}). To prove Theorem 1.2, we first construct three sets that will be used to great effect in Section 4.

Definition 2.7. Define two sets of permutations:

R_{n} = {w ∈ 𝔖_{n} | Q(w) = Q(w^{r})}

and

H_{n} = {w ∈ 𝔖_{n} | Q(w) is of symmetric hook shape},

where a symmetric shape is one that shares the same shape with its transpose as Young diagrams and a hook shape tableau has an underlying Young diagram of shape μ = (k, 1^{n−k}), k < n. Note that H_{n} is empty for all even n, as there are no symmetric hook shape tableaux for even n.

Concerning to sets of standard Young tableaux, for all shapes λ ⊢ n define the sets

M_{n}^{λ} = {Q ∈ SYT(λ) | ϵ(Q)^{T} = Q}.

We now split Theorem 1.2 into two parts. Theorem 2.8, combined with the fact that H_{n} is empty for all even n, sheds light on some of the subtleties of the main result, specifically the dependence on the parity of n.

Theorem 2.8. For all n ≥ 1, the set R_{n} is a subset of H_{n}, forcing Q(w) to have a symmetric hook shape for all w ∈ R_{n}.

Finally, Theorem 2.9 — previously a conjecture — is what began our research direction.

8 T. J. ERVIN, B. JACKSON, J. LANE, K. LEE, S. D. NGUYEN, J. O’DONOHUE, AND M. VAUGHAN

Theorem 2.9. The cardinality of the set R_{n} is given by

|R_{n}| = \begin{cases}2^{\frac{n−1}{2}} \binom{n − 1}{\frac{n−1}{2}}, & n odd, \\ 0, & n even. \end{cases}

3. The Maps ϕ_{a,b} and Their Left Inverse

To begin proving Theorem 2.8, we define a family of maps that take permutations of [n] to permutations of [n + 2] arising from the standardization of a sequence of distinct integers.

Definition 3.1. Let v = v_{1}v_{2} … v_{n} be any sequence of distinct positive integers and v_{i_{1}} < v_{i_{2}} < ⋯ < v_{i_{n}} be the ordering of the integers v_{i}. The standardization of v, denoted std(v), is obtained by replacing each integer v_{i_{j}} in v by the integer j.

Since both the reverse and complement operators will change increasing sequences to decreasing and vice-versa, it is apparent that std(v^{r}) = std(v)^{r} and std(v^{c}) = std(v)^{c} for all sequences of distinct positive integers v. We may then define our maps ϕ_{a,b}.

Definition 3.2. For any w ∈ 𝔖_{n} and any two distinct integers a, b ∈ [n + 2], let v = v_{1}v_{2} … v_{n} be the unique sequence of integers from [n+2]\{a, b} such that std(v) = w. Define the map ϕ_{a,b} : 𝔖_{n} ↦ 𝔖_{n+2} by ϕ_{a,b}(w) = avb, where adjacency denotes concatenation. These maps are then well-defined for all distinct a, b ∈ [n + 2]. Let Φ_{n} denote the family of maps ϕ_{a,b} from 𝔖_{n} to 𝔖_{n+2}.

Example 3.3. Application of ϕ_{1,7} to 52314 ∈ 𝔖_{5} produces

ϕ_{1,7}(52314) = 1634257.

As we saw previously, the permutation 52314 belongs to R_{5}, but ϕ_{1,7}(52314) does not belong to R_{7}. When w ∈ R_{n} implies ϕ_{a,b}(w) ∈ R_{n+2} is explored in Lemma 4.2.

Remark 3.4. Now that we have seen the maps in action, we can speak more of their properties.

• Each map ϕ_{a,b} is injective.

• In general, the maps ϕ_{a,b} are not group homomorphisms, as ϕ_{a,b} only sends the identity element to the identity element when a = 1 and b = n + 2. However, the map ϕ_{1,n+2} is a group monomorphism.

• If ϕ_{a,b}(w) = ϕ_{x,y}(w) for any w ∈ 𝔖_{n}, then a = x and b = y.

• The set 𝔖_{n+2} is partitioned by the images of the functions ϕ_{a,b}.

The Φ_{n} maps go “up” the symmetric groups, but we need a function to go “down” from 𝔖_{n+2} to 𝔖_{n}. We then construct a left inverse function shared by every ϕ_{a,b} ∈ Φ_{n}.

Definition 3.5. We define the map θ_{n} : 𝔖_{n+2} ↦ 𝔖_{n} as follows. If w = w_{1}w_{2} … w_{n+1}w_{n+2} ∈ 𝔖_{n+2}, form the subword w′ = w_{2}w_{3} … w_{n}w_{n+1}. Then θ_{n}(w) = std(w′). These maps are well defined for all positive integers n.

Example 3.6. If we apply θ_{3} to our permutation 52314, then we arrive at

θ_{3}(52314) = 231.

Note that θ_{n} seems to send R_{n+2} to R_{n}, as every permutation, w, above has Q(w) = Q(w^{r}). This relation is further explored in Lemma 4.1.

Remark 3.7. As before, we will now list some of the important properties of θ_{n}. • Each map θ_{n} is surjective.

• For all ϕ_{a,b} ∈ Φ_{n} and w ∈ 𝔖_{n}, θ_{n} acts as a left inverse, i.e.,

θ_{n}(ϕ_{a,b}(w)) = w.

• If i, j ∈ [n], then w_{i+1} < w_{j+1} implies that θ_{n}(w)_{i} < θ_{n}(w)_{j}, following directly from our definition of standardization.

Because θ_{n} is a left inverse and the images of the Φ_{n} maps partition 𝔖_{n+2}, we immediately see that

θ_{n}^{−1}(w) = ⨄_{ϕ_{a,b}∈Φ_{n}} ϕ_{a,b}(w).

Combined with the next two lemmas, this fact is instrumental in proving Theorem 2.8.

Lemma 3.8. For any w ∈ 𝔖_{n+2},

θ_{n}(w^{r}) = θ_{n}(w)^{r}

and

θ_{n}(w^{c}) = θ_{n}(w)^{c}.

Proof. From the definition of θ_{n}, we know that θ_{n}(w^{r}) equals the standardization of the sequence w_{n+1}w_{n} … w_{3}w_{2}. Additionally, the permutation θ_{n}(w)^{r} = std(w_{2}w_{3} … w_{n}w_{n+1})^{r}. As std(w_{n+1}w_{n} … w_{3}w_{2}) = std(w_{2}w_{3} … w_{n}w_{n+1})^{r}, we must have

θ_{n}(w^{r}) = θ_{n}(w)^{r}.

10 T. J. ERVIN, B. JACKSON, J. LANE, K. LEE, S. D. NGUYEN, J. O’DONOHUE, AND M. VAUGHAN

By a similar argument, we know that std((n + 3 − w_{2})(n + 3 − w_{3}) … (n + 3 − w_{n})(n + 3 − w_{n+1})) = std(w_{2}w_{3} … w_{n}w_{n+1})^{c}. Hence

θ_{n}(w^{c}) = θ_{n}(w)^{c},

proving our desired result. □

Lemma 3.9. Choose ϕ_{a,b} ∈ Φ_{n} and w ∈ H_{n} for odd n. Then either ϕ_{a,b}(w) ∈ H_{n+2} or Q(ϕ_{a,b}(w)) is not of symmetric shape.

Proof. Let w ∈ H_{n}. Suppose that ϕ_{a,b}(w) ∉ H_{n+2} for some ϕ_{a,b} ∈ Φ_{n}. As ϕ_{a,b} preserves all the relative orderings of w by its construction, longest increasing and longest decreasing subsequences of ϕ_{a,b}(w) are the same length or longer than respective longest increasing and longest decreasing subsequences of w. It is well-known that the lengths of the first row and the first column of Q(w) equal the lengths of longest increasing and longest decreasing subsequences respectively of w [3, Theorem 3.3.2]. The first row and the first column of Q(w) both have length \frac{n+1}{2} as Q(w) is of symmetric hook shape. Hence, longest increasing and longest decreasing subsequences of ϕ_{a,b}(w) must have length at least \frac{n+1}{2}. If Q(ϕ_{a,b}(w)) is of symmetric shape, then the length of longest increasing and longest decreasing subsequences of ϕ_{a,b}(w) must equal each other. Since ϕ_{a,b}(w) ∉ H_{n+2}, longest increasing and decreasing subsequences necessarily have length \frac{n+1}{2}. Thus two cells were added to the second row or column of Q(ϕ_{a,b}(w)), contradicting the symmetry of Q(ϕ_{a,b}(w)). Therefore, either ϕ_{a,b}(w) ∈ H_{n+2} or Q(ϕ_{a,b}(w)) is not of symmetric shape. □

As an example of the possibilities discussed in Lemma 3.9, we give the following.

Example 3.10. Consider the Young diagram of symmetric hook shape

.

After an application of a ϕ_{a,b} ∈ Φ_{n}, two new cells will be added to the diagram. There are four possibilities — up to transposition — for the resulting shape:

.

Clearly, only the tableau in H_{7} has symmetric shape.

REVERSE PERMUTATIONS IN THE RS CORRESPONDENCE 11

4. Proof of Theorems 2.8 and 2.9

To begin our proof of Theorem 2.8, we first prove the two lemmas we mentioned previously when exploring the actions of the Φ_{n} and θ_{n} maps.

Lemma 4.1. If w ∈ R_{n+2}, then θ_{n}(w) ∈ R_{n}.

Proof. Suppose that w ∈ R_{n+2}. Let x = w_{2}w_{3} … w_{n+2} and y = w_{n+1}w_{n} … w_{1}. Then Q(x) = ΔQ(w) and Q(y) = ΔQ(w^{r}) [3, Proposition 3.9.3]. As w ∈ R_{n+2}, we have Q(w) = Q(w^{r}), showing that Q(x) = Q(y). Since n + 1 occupies the same cell in Q(x) and Q(y), not inserting w_{n+2} or w_{1} in the respective x and y cases produces the same recording tableau. Hence,

Q(w_{2}w_{3} … w_{n+1}) = Q(w_{n+1}w_{n} … w_{2}).

As θ_{n} preserves all the relative orderings among middle entries of permutations by our definition of standardization, it follows that

Q(θ_{n}(w)) = Q(w_{2}w_{3} … w_{n+1})

and

Q(θ_{n}(w^{r})) = Q(w_{n+1}w_{n} … w_{2}).

As Lemma 3.8 proves Q(θ_{n}(w)^{r}) = Q(θ_{n}(w^{r})), the equality

Q(θ_{n}(w)) = Q(θ_{n}(w)^{r})

holds. Therefore, the permutation θ_{n}(w) belongs to R_{n} for all w ∈ R_{n+2}. □

Lemma 4.2. For all n, we have

R_{n+2} ⊆ ⋃_{ϕ_{a,b}∈Φ_{n}} ϕ_{a,b}(R_{n}).

Proof. If w ∈ R_{n+2}, Lemma 4.1 gives us that θ_{n}(w) ∈ R_{n}. Thus w ∈ ϕ_{w_{1},w_{n+2}}(R_{n}). Hence,

R_{n+2} ⊆ ⋃_{ϕ_{a,b}∈Φ_{n}} ϕ_{a,b}(R_{n})

for all n. □

Theorem 4.3 (Theorem 2.8). For all n ≥ 1, the set R_{n} is a subset of H_{n}, forcing Q(w) to have a symmetric hook shape for all w ∈ R_{n}.

12 T. J. ERVIN, B. JACKSON, J. LANE, K. LEE, S. D. NGUYEN, J. O’DONOHUE, AND M. VAUGHAN

Proof. We split into two separate induction arguments, one odd and one even. In the odd scenario, the base case of n = 1 is clear, as R_{1} = H_{1} = 𝔖_{1}. As such, we assume that R_{n−2} ⊆ H_{n−2} for n = 2ℓ + 1. If v ∈ 𝔖_{n}, then P (v) = P (v^{r})^{T} [3, Theorem 3.2.3]. Hence the shape of Q(v) must be symmetric for all v ∈ R_{n}. If ϕ_{a,b}(w) is not in H_{n} for a ϕ_{a,b} ∈ Φ_{n−2} and some w ∈ R_{n−2}, then the shape of Q(ϕ_{a,b}(w)) is non-symmetric by Lemma 3.9. This further implies that ϕ_{a,b}(w) is not in R_{n}. The contrapositive gives that ϕ_{a,b}(w) ∈ R_{n} implies ϕ_{a,b}(w) ∈ H_{n}.

From Lemma 4.2, we have R_{n} ⊆ ⋃_{ϕ_{a,b}∈Φ_{n−2}} ϕ_{a,b}(R_{n−2}). Thus every element of R_{n} is of the form ϕ_{a,b}(w) for ϕ_{a,b} ∈ Φ_{n−2} and w ∈ R_{n−2}. Therefore R_{n} ⊆ H_{n}, completing the inductive step.

In the even case, the base case of n = 2 is clear, as R_{2} = H_{2} = ∅. The set H_{n} is empty for all even n. As such, we assume that R_{n−2} is empty for n = 2ℓ. If R_{n} is nonempty, Lemma 4.1 gives us that θ_{n−2}(R_{n}) ⊆ R_{n−2}, creating a contradiction of our inductive assumption. Hence R_{n} must be empty and a subset of H_{n} as well, completing the inductive step. Therefore R_{n} ⊆ H_{n} for all n. □

Furthermore, if λ ⊢ n is a symmetric hook shape for n > 1, then the tableau T of shape λ with entries 1, 2, 3, …, \frac{n+1}{2} in the first row and entries 1, \frac{n+3}{2}, \frac{n+5}{2}, …, n in the first column can be readily seen to satisfy T = ϵ(T)^{T}. Thus T ∈ M_{n}^{λ}. For n = 5, we have the example

T = 1 2 3 4 5 .

Corollary 4.4. For all λ ⊢ n, the set M_{n}^{λ} is non-empty if and only if λ is a symmetric hook shape.

Remark 4.5. It should be stressed that R_{n} really is a proper subset of H_{n} for odd n ≥ 5. In other words, there are w ∈ 𝔖_{n} that are of symmetric hook shape but do not have fixed recording tableaux under the reverse operation. The permutation 34521 is such an example.

Since we have shown that M_{n}^{λ} is only non-empty when n is odd and λ is a symmetric hook shape, we may restrict ourselves to those conditions and begin to examine the properties of Q ∈ M_{n}^{λ}.

Lemma 4.6. For odd n, let λ = (\frac{n+1}{2}, 1^{\frac{n−1}{2}} ). The standard Young tableau Q belongs to M_{n}^{λ} if and only if i in the first row of Q implies that n − i + 2 belongs to the first column of Q for all i ∈ [n] with i > 1.

REVERSE PERMUTATIONS IN THE RS CORRESPONDENCE 13

Proof. Suppose that Q ∈ M_{n}^{λ}. Additionally assume that i is in the first row of a symmetric hook shape tableau, Q, where i ∈ [n] and i > 1. The cell vacated when passing from Δ^{i−2}Q to Δ^{i−1}Q is filled with n − i + 2 in ϵ(Q). As i − 1 is minimal in Δ^{i−2}Q, it appears in the first cell of Δ^{i−2}Q and i is in the cell to its right. Hence the cell vacated when passing from Δ^{i−2}Q to Δ^{i−1}Q will be in the first row. Thus n − i + 2 appears in the first row of ϵ(Q) if i appears in the first row of Q. As Q = ϵ(Q)^{T}, the location of i in the first row of Q implies that n − i + 2 belongs to the first column of Q for all i ∈ [n] with i > 1 whenever Q ∈ M_{n}^{λ}.

Conversely, suppose that i in the first row of Q implies that n − i + 2 belongs to the first column of Q for all i ∈ [n] with i > 1. Let 1, i_{2}, i_{3}, …, i_{\frac{n+1}{2}} be the increasing sequence that forms the first row of Q. Thus 1, n − i_{\frac{n+1}{2}} + 2, …, n − i_{3} + 2, n − i_{2} + 2 must be the increasing sequence that forms the first column of Q. The cell erased when passing from Δ^{i−2}Q to Δ^{i−1}Q always contains i − 1 and is located in the uppermost left corner of the tableau. This implies that the cell vacated from Δ^{i−2}Q to Δ^{i−1}Q will belong to the same row or column in Q as i. Hence ϵ(Q) will have n − i + 2 in its first row whenever i is in the first row of Q. This further implies that 1, n − i_{\frac{n+1}{2}} + 2, …, n − i_{3} + 2, n − i_{2} + 2 must be the increasing sequence that forms the first row of ϵ(Q). Similarly, the first row of Q and the first column of ϵ(Q) must coincide. Hence Q = ϵ(Q)^{T} whenever i in the first row of Q implies that n − i + 2 belongs to the first column of Q for all i ∈ [n] with i > 1. Therefore, for odd n, the standard Young tableau Q belongs to M_{n}^{λ} if and only if i in the first row of Q implies that n − i + 2 belongs to the first column of Q for all i ∈ [n] with i > 1. □

Returning to the previous Example 2.2, we can verify that the tableau Q(52314) ∈ M_{5}^{λ} by Lemma 4.6. Lemma 4.7 follows immediately from Lemma 4.6, and it allows us to correctly count the number of tableaux in M_{n}^{λ}.

Lemma 4.7. Let λ = (\frac{n+1}{2}, 1^{\frac{n−1}{2}} ). If n is odd, then

|M_{n}^{λ}| = 2^{\frac{n−1}{2}} .

We may then prove Theorem 2.9.

Theorem 4.8 (Theorem 2.9). The cardinality of the set R_{n} is given by

|R_{n}| = \begin{cases}2^{\frac{n−1}{2}} \binom{n − 1}{\frac{n−1}{2}}, & n odd, \\ 0, & n even. \end{cases}

14 T. J. ERVIN, B. JACKSON, J. LANE, K. LEE, S. D. NGUYEN, J. O’DONOHUE, AND M. VAUGHAN

Proof. For even n, the result follows directly from Theorem 4.3 as R_{n} is empty. We then focus on odd n. Let λ = (\frac{n+1}{2}, 1^{\frac{n−1}{2}} ). If w ∈ R_{n}, then Q(w) = Q(w^{r}) = ϵ(Q(w))^{T} [3, Theorem 3.9.4]. Thus Q(w) ∈ M_{n}^{λ} for all w ∈ R_{n}.

Let T ∈ M_{n}^{λ}. The number of pairs of standard Young tableaux with T as the recording tableau is equal to the number of standard Young tableaux of shape λ. As the RSK correspondence is a bijection of permutations and pairs of standard Young tableaux, there are f^{λ} = \binom{n−1}{\frac{n−1}{2}} many w ∈ 𝔖_{n} such that Q(w) = T. If Q(w) ∈ M_{n}^{λ}, then Q(w) = ϵ(Q(w))^{T} = Q(w^{r}). Thus w ∈ R_{n}. The cardinality of R_{n} must then be |M_{n}^{λ}|f^{λ} for all odd n.

Therefore,

|R_{n}| = \begin{cases}2^{\frac{n−1}{2}} \binom{n − 1}{\frac{n−1}{2}}, & n odd, \\ 0, & n even. \end{cases}

proving the desired result. □

Theorems 4.3 and 4.8, along with Lemma 4.6, combine to prove Theorem 1.2.

References

[1] D. E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific Journal of Mathematics, 34: 709–727, 1970.

[2] G. de B. Robinson, On the representations of the symmetric group, American Journal of Mathematics, 60 (3): 745–760, 1938.

[3] B. E. Sagan, The Symmetric Group, 2nd edition, Graduate Texts in Mathematics, 203, New York: Springer-Verlag, 2001.

[4] C. Schensted, Longest increasing and decreasing subsequences, Canadian Journal of Mathematics, 13: 179–191, 1961.

[5] J. L. Martin, Lecture Notes on Algebraic Combinatorics, Available online at

   https://jlmartin.ku.edu/CombinatoricsNotes.pdf (updated March 12, 2021), 2021.

[6] M. V. Leeuwen, The Robinson–Schensted and Schützenberger algorithms, an elementary approach, The Electronic Journal of Combinatorics, 3 (2): Article R15, 32 pp., 1996.

Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.

Email address: tjervin@crimson.ua.edu

Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.

Email address: bajackson9@crimson.ua.edu

Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.

Email address: Jay.D.Lane-1@ou.edu

Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A. and Korea Institute for Advanced Study, Seoul 02455, Republic of Korea

Email address: klee94@ua.edu; klee1@kias.re.kr

Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.

Email address: sdnguyen1@crimson.ua.edu

Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.

Email address: jro5347@psu.edu

Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487, U.S.A.

Email address: mvaughan1@crimson.ua.edu