Counting the Nontrivial Equivalence Classes of S_{n} Under {1234, 3412}-Pattern-Replacement

Quinn Perian Stanford Online High School Academy Hall Floor 2 8853

415 Broadway Redwood City, CA 94063

USA

quinn.perian@outlook.com

Bella Xu

William P. Clements High School

4200 Elkins Drive Sugar Land, TX 77479

USA

bxu107@gmail.com

Alexander Lu Zhang Lower Merion High School 315 E Montgomery Ave

Ardmore, PA 19003

USA

azhang896@gmail.com

Abstract

We study the {1234, 3412}-pattern-replacement equivalence relation on the set S_{n} of permutations of length n, which is conceptually similar to the Knuth relation. In particular, we enumerate and characterize the nontrivial equivalence classes, or equivalence classes with size greater than 1, in S_{n} for n ≥ 7 under the {1234, 3412}-equivalence. This proves a conjecture by Ma, who found three equivalence relations of interest in studying the number of nontrivial equivalence classes of S_{n} under pattern-replacement equivalence relations with patterns of length 4, enumerated the nontrivial classes under two of these relations, and left the aforementioned conjecture regarding enumeration under the third as an open problem.

1 Introduction

A permutation π ∈ S_{n} is said to contain a pattern σ ∈ S_{c}, c ≤ n, if there is a c-letter subsequence π_{i_{1}}, π_{i_{2}}, …, π_{i_{c}} of π that is order-isomorphic with σ (i.e., for indices j, k ∈ [c], π_{i_{j}} < π_{i_{k}} if and only if σ_{j} < σ_{k}). In the past thirty years, the topic of permutation patterns has risen to the forefront of combinatorics (see Kitaev [9] for a survey) and has even spawned its own annual conference [8].

The focus of this paper is permutation pattern-replacement equivalences. Given a set of patterns P ⊆ S_{c} and a permutation π ∈ S_{n}, one can perform a P -pattern-replacement on π by taking a subsequence π_{i_{1}}, …, π_{i_{c}} of π that forms a pattern σ ∈ P and rearranging the relative order of the letters π_{i_{1}}, …, π_{i_{c}} so that they form a different pattern in P. We say that two permutations α, β ∈ S_{n} are P -replacement equivalent if α can be reached from β by a series of P -pattern-replacements. This defines an equivalence relation on S_{n}, which is known as the P -replacement equivalence [11, 13, 22, 15, 19, 10, 18, 16, 7].

The study of permutation pattern-replacement equivalences is closely related to the study of permutation pattern avoidance [9, 20, 6, 14, 17, 3, 5, 4], which seeks to count the number of singleton equivalence classes (i.e., the number of permutations containing no patterns in P). The dual problem of counting the number of non-singleton (i.e., nontrivial) equivalence classes has recently received a large amount of attention in the literature [11, 13, 22, 15, 19, 10, 18, 16, 7].

Other variations of pattern-replacement equivalence, beyond the variant defined above that we study in this paper, have also been investigated in the past. For instance, patternreplacement equivalences where the letters forming a pattern are required to be consecutive in value, adjacent in the permutation, or both have been examined in previous papers [16, 13]. Other variants include equivalence relations in which there exist multiple disjoint sets of patterns, such that a pattern in any set can be rearranged to form other patterns in the same set [12, 13].

Most of the research so far on permutation pattern-replacement equivalences has worked to systematically understand the equivalence classes for all pattern-replacement equivalence relations involving patterns of length three [11, 13, 22, 15, 19, 10, 18]. Many interesting number sequences have arisen (e.g., the Catalan numbers, Motzkin numbers, tribonacci numbers, central binomial coefficients, and many more complicated number sequences).

Recently, Ma [16] initiated the systematic study of pattern-replacement equivalences with patterns of length four. Because the number of pattern-replacement sets P ⊆ S_{4} is very large, Ma took a computational approach to identify which of the pattern-replacement sets were most interesting to study. In particular, Ma computed the number of nontrivial equivalence classes under P -equivalence for all sets P ∈ S_{4}^{2} and then matched the resulting number sequences with the On-Line Encyclopedia of Integer Sequences (OEIS) [21] in order to identify pattern-replacement sets P for which the number of nontrivial equivalence classes is described by a natural formula. Ma identified three formulae of particular interest and was able to enumerate the nontrivial equivalence classes for the equivalence relations corresponding to two of them. Enumerating the equivalence classes for the third equivalence relation, namely the {1234, 3412}-equivalence, has remained an open question.

In this paper, we resolve the aforementioned open problem by proving the following theorem:

Theorem 1 (Conjectured by Ma [16]). For n ≥ 7, the number of nontrivial equivalence classes of S_{n} under the \{1234, 3412\}-equivalence is \frac{n^{3}+6n^{2}−55n+54}{6} (given by sequence \underline{A330395}).

Recall that we define two permutations α, β ∈ S_{n} to be equivalent under the {1234, 3412}- equivalence if α can be reached from β by performing a series of 1234 → 3412 and 3412 → 1234 pattern-replacements. A 1234 → 3412 pattern-replacement in a permutation π simply takes an increasing 4-letter subsequence π_{i_{1}}, π_{i_{2}}, π_{i_{3}}, π_{i_{3}} (where i_{1} < i_{2} < i_{3} < i_{4}), and places each of π_{i_{3}}, π_{i_{4}}, π_{i_{1}}, π_{i_{2}} in positions i_{1}, i_{2}, i_{3}, i_{4} of the permutation. For example, in the permutation π = 7162435, the subsequence 1, 2, 3, 5 forms a 1234 pattern, and we can perform a 1234 → 3412 pattern replacement to obtain the new permutation π′ = 7365412. Similarly, a 3412 → 1234 pattern-replacement takes any four-letter subsequence that forms a 3412 pattern, and rearranges the letters in that subsequence to instead be in increasing order, thereby forming a 1234 pattern.

Theorem 1 counts the number of nontrivial equivalence classes in S_{n} under the {1234, 3412}- equivalence. These are the equivalence classes of size greater than one, or alternatively, the equivalence classes consisting of non-{1234, 3412}-avoiding permutations. In the remainder of the paper, we prove Theorem 1.

1.1 Formal definitions

Definition 2 (Standardization of a permutation). Given a word ρ of length n consisting of n distinct letters in ℕ, the standardization of ρ is the permutation in S_{n} obtained by replacing the ith smallest letter in ρ with i for each i ∈ {1, 2, …, n}.

Definition 3 (Sub-standardization of a permutation). Given a permutation π ∈ S_{n}, and a subword ρ of π, the standardization of ρ is known as a sub-standardization of π. If removing the letter a from π gives ρ, then the standardization of ρ is also called the substandardization of π formed by removing a, denoted by π_{−(a)}. In general, the standardization of the permutation formed by removing distinct letters a_{1}, a_{1}, …, a_{n} from π is denoted by π_{−(a_{1},...,a_{n})}.

Definition 4 (Pattern formation). Given a pattern p ∈ S_{c} and a permutation π ∈ S_{n}, we say that π contains pattern p if p is a sub-standardization of π. If a subword ρ of π has standardization p, then we say that ρ forms pattern p.

Definition 5 (Pattern-replacement). Given two patterns p, q ∈ S_{c} and a permutation π ∈ S_{n}, a p → q pattern-replacement can be performed by taking any subword ρ of π that forms pattern p, and rearranging the letters in ρ to instead form pattern q.

Definition 6 (Pattern-replacement equivalences). Given a set of patterns P ⊆ S_{c}, we say that two permutations p, q ∈ S_{n} are equivalent under P -equivalence if p can be reached from q by a sequence of pattern-replacements using patterns in P. Maximal collections of P -equivalent permutations are known as equivalence classes, and an equivalence class is said to be nontrivial if it contains more than one permutation.

1.2 Paper outline

To prove Theorem 1, we use three lemmas in order to characterize the equivalence classes under the {1234, 3412}-equivalence. To begin, we use the principle of inclusion-exclusion to establish a recurrence relation that allows us to express the equivalence classes in S_{n} in terms of the equivalence classes in S_{n−1} and S_{n−2} (Section 2). This reduces the proof of Theorem 1 to proving that the number of equivalence classes of a certain form is n + 1. We then characterize n−1 of these classes that have a natural combinatorial structure, consisting of all permutations one transposition away from one of n−1 different representative permutations (Section 3). Finally, we show that the remaining permutations fall into exactly two classes depending on the parity of the number of inversions they contain (Section 4); here, we use a proof structure that exploits the stooge-sort technique of Kuszmaul [11]. The authors have checked, by computer, the veracity of each of these intermediate steps for the first few values of n. Combining these steps, we prove Theorem 1.

2 Reducing to permutations neither beginning with n nor ending with 1

In this section, we reduce the proof of Theorem 1 to counting the number of nontrivial equivalence classes that contain no permutations with n in the first position or 1 in the last position.

Lemma 7. Theorem 1 can be reduced to proving that there are exactly n + 1 nontrivial equivalence classes of S_{n} where no permutation begins with n or ends with 1.

Proof. Let A_{n} be the total number of nontrivial equivalence classes of S_{n} under the {1234, 3412}- equivalence. Let B_{n} be the number of nontrivial equivalence classes of S_{n} under the {1234, 3412}- equivalence that do not contain any permutation beginning with n or ending with 1. Then we have the following recurrence relation.

Claim 8. For n ≥ 3,

A_{n} − B_{n} = 2A_{n−1} − A_{n−2}.  (1)

Proof. Since the largest element is never first and the smallest element is never last in the patterns 1234 and 3412, no pattern-replacements under the {1234, 3412}-equivalence can move a leading n or an ending 1. Therefore, appending n to the front (resp., 1 to the end) of all permutations of an equivalence class in S_{n−1} results in an equivalence class in S_{n}. Call this the lifting observation.

We can count the number of equivalence classes where all permutations have either n in the first position or 1 in the last position (or both) in two different ways. The left side of (1) represents this number with complementary counting, where all equivalence classes not satisfying the requisite are subtracted from the total number of equivalences classes. On the right side of (1), we count the same number of equivalence classes using the principle of inclusion-exclusion. By the lifting observation, we can append an n to the front of all permutations in S_{n−1} or append a 1 to the back of all permutations in S_{n−1} to form all possible equivalence classes where all permutations have either n in the first position or 1 in the last position (or both). (This contributes 2A_{n−1} to (1).) The repeats, which are formed by appending both an n to the front and a 1 to the back of all permutations in S_{n−2}, are then subtracted off. (This removes A_{n−2}.)

Since the two sides of (1) count the same quantity, we must have equality.

Using the recursion given in the preceding claim, we now analyze the value that B_{n} must take in order for A_{n} to satisfy the formula stated in Theorem 1.

Claim 9. Showing that B_{n} = n + 1 suffices to prove that A_{n} = \frac{n^{3}+6n^{2}−55n+54}{6} for all n ≥ 7.

Proof. Suppose B_{n} = n + 1 for all n ≥ 7. We use this to prove that A_{n} = \frac{n^{3}+6n^{2}−55n+54}{6} for all n ≥ 7.

The base cases of n = 7, 8 for A_{n} = \frac{n^{3}+6n^{2}−55n+54}{6} have been checked by computer [16]. Assume by induction that our formula for A_{n} holds for n = k − 1 and n = k − 2 for some

integer k ≥ 9. Then by Claim 8,

A_{k} = B_{k} + 2A_{k−1} − A_{k−2}

= k + 1 + 2 · \frac{(k − 1)^{3} + 6(k − 1)^{2} − 55(k − 1) + 54}{6}

− \frac{(k − 2)^{3} + 6(k − 2)^{2} − 55(k − 2) + 54}{6}

= k + 1 + 2 · \frac{k^{3} + 3k^{2} − 64k + 114}{6} − \frac{k^{3} − 67k + 180}{6}

= \frac{k^{3} + 6k^{2} − 55k + 54}{6},

which is our formula for A_{k}.

By induction, A_{n} = \frac{n^{3}+6n^{2}−55n+54}{6} holds for all n ≥ 7.

This completes the proof of the lemma.

3 Characterizing the n − 1 small classes

In this section, we characterize n − 1 of the nontrivial equivalence classes of S_{n} that contain no permutation beginning with n or ending with 1. Each of these classes is associated with a “leader permutation” that is one transposition away from each permutation in the class.

Below we define the notion of a leader permutation and what we mean when we call two permutations “adjacent.” The equivalence classes then correspond to the sets of permutations that are adjacent to each leader permutation.

Definition 10 (Leader permutation). Define a leader permutation of length n to be a permutation of the form a_{1}a_{2} ⋯ a_{n} such that for some integer k ∈ [2, n], a_{i} = k − i for all 1 ≤ i < k and a_{i} = n + k − i for all k ≤ i ≤ n.

Two equivalent definitions are that a permutation is a leader permutation if it is the pluscomposition of two nonempty, decreasing patterns [2], and that a permutation is a leader

permutation if it is a member of the geometric grid class of (\begin{matrix}0 & −1 \\ −1 & 0 \end{matrix}) with at least one

letter on each of the two lines corresponding to the −1’s [1].

Example 11. The 7 leader permutations of length 8 are 18765432, 21876543, 32187654, 43218765, 54321876, 65432187, and 76543218.

Definition 12 (Adjacent permutations). We define two permutations π, ρ ∈ S_{n} to be adjacent if neither π nor ρ begins with n or end with 1 and if π is a transposition of ρ such that the positive difference between the two letters in the transposition is neither 1 nor n − 1.

We now provide our characterization of the equivalence classes associated with the leader permutations in S_{n}.

Proposition 13. For any leader permutation π, the set of permutations adjacent to π is an equivalence class. Moreover, there are n − 1 of these classes.

To prove Proposition 13, we begin by proving that the equivalence classes are disjoint.

Lemma 14. For distinct leader permutations π, ψ, the set of permutations adjacent to π is disjoint from the set of permutations adjacent to ψ.

Proof. Assume for the sake of contradiction that the two sets share a common element. This would imply that it is possible to reach π from ψ in two or fewer transpositions. Since any leader permutation is a derangement of any other leader permutation, the permutations π and ψ differ in all n ≥ 7 positions. However, since each transposition can only switch the positions of two letters, it is impossible for two or fewer transpositions to get π from ψ, a contradiction.

Next we prove that

Lemma 15. If we have a permutation adjacent to some leader permutation π and we apply a {1234, 3412}-pattern-replacement to it, the resulting permutation is also adjacent to π.

Proof. Note that π consists of a decreasing set of consecutive letters followed by another decreasing set of consecutive letters that are all larger than those of the first set; let X and Y denote these two sets, respectively. Figure 1 shows this for π = 32187654, for which X consists of 321 and Y consists of 87654.

Figure 1: The leader permutation 32187654. X is in gray on left and Y is on right.

Consider a permutation a_{1}a_{2} ⋯ a_{n} such that if a transposition is applied to two letters a_{i} and a_{j}, i ≠ j, the resulting permutation is equal to a leader permutation π. We claim that any {1234, 3412}-pattern-replacement applied to a_{1}a_{2} ⋯ a_{n} must use both a_{i} and a_{j} and result in a permutation adjacent to π.

To show that a {1234, 3412}-pattern-replacement applied to a_{1}a_{2} ⋯ a_{n} must use both a_{i} and a_{j}, first note that any three-letter subsequence of π must correspond to one of the patterns 321, 213, or 132 depending on how many letters are from each of X and Y. Figure 2 shows three examples of such three-letter subsequences in the leader permutation 54321876; each corresponds to a different pattern.

Figure 2: The subsequences 532, 417, and 487 of 54321876.

However, neither 1234 nor 3412 contains any of 321, 213, or 132 as a subpattern, which means π does not contain any three-letter subpattern of 1234 or 3412. As a consequence, any 1234 or 3412 pattern in a_{1}a_{2} ⋯ a_{n} must contain both a_{i} and a_{j}.

Furthermore, the pattern in a_{1}a_{2} ⋯ a_{n} must contain exactly one letter between a_{i} and a_{j}. To see this, note that in π, any four-letter subsequence corresponds to one of the patterns 4321, 3214, 2143, or 1432 depending on how many letters are from each of X and Y. The only transpositions of two letters that could result in 1234 are swapping the 1 and 3 in 3214 and swapping the 2 and 4 in 1432, and the only transpositions that could result in 3412 are swapping the 2 and 4 in 3214 and swapping the 1 and 3 in 1432. In any case, there is exactly one letter between the swapped letters a_{i} and a_{j}.

Since a {1234, 3412}-pattern-replacement swaps the first and third letters and swaps the second and fourth letters, a_{i} and a_{j} are swapped back to their original order in π, and a new transposition is applied. The new permutation is adjacent to π.

This completes the proof of the claim.

Finally, we show that any two permutations adjacent to the same leader permutation are always equivalent.

Lemma 16. For any permutations τ and σ that are both adjacent to a leader permutation π, τ can be reached from σ by a sequence of {1234, 3412}-pattern-replacements.

Proof. We prove this using induction on n. Our base cases of n = 7 and 8 can be checked by computer. Assume as an inductive hypothesis that the result holds for n − 1 ≥ 8. Consider two permutations τ and σ of length n that are adjacent to some leader permutation π. Pick one of their common letters a that is (1) not 1 or n; (2) not part of either transposition from the leader permutation; (3) not adjacent in position to both letters in the transposition from π to τ; and (4) not adjacent in position to both letters in the transposition from π to σ. Such an a is guaranteed to exist because n ≥ 9 and the four aforementioned conditions on a restrict at most 8 letters in total.

Now, consider the sub-standardizations τ′, σ′, and π′ respectively formed by removing a from τ, σ, and π. Note that π′ is a leader permutation of length n − 1 (because a ≠ 1 and a ≠ n). In addition, τ′ and σ′ are both adjacent to π′. Thus, by our inductive hypothesis, π′ can be reached from τ′ by a sequence of pattern-replacements. By looking at the letters in τ corresponding to those of τ′, we see that π can be reached from τ by a sequence of pattern-replacements. This completes the proof by induction.

Combined, Lemmas 14, 15, and 16 complete the proof of Proposition 13.

4 Showing that there are two remaining classes

We now proceed to show that there are only two nontrivial classes remaining to be analyzed. To do this, we find two representative permutations, one from each class. First, we show that these representative permutations cannot be in the same equivalence class because they differ in parity, which implies that there are at least two remaining equivalence classes. Then, we show that every permutation that we have yet to analyze is equivalent to one of these two representative permutations, hence showing that there are at most, and thus exactly, two remaining nontrivial equivalence classes. To show the second part, we use induction on the size of the permutation. We begin by applying the inductive hypothesis to all but one of the letters of the permutation to transform them to be order-isomorphic to a representative permutation (of length n−1). After applying this transformation, we return to considering all n letters of the transformed permutation. We then select a different letter in the transformed permutation (specifically, we pick a letter that is already in the “final” position that we want it to be in), and we apply the inductive hypothesis to the n − 1 letters of the permutation excluding that letter in order to transform them to be order-isomorphic to a representative permutation (of length n − 1). If done correctly, this construction causes the entire final permutation to form a representative permutation of length n, completing the proof.

We begin with some preliminary definitions.

Definition 17 (Primary permutation). We call a permutation in S_{n} primary if it is not adjacent to a leader permutation and does not start with n or end with 1.

Definition 18 (Primary class). We define a primary class to be a nontrivial equivalence class of primary permutations in S_{n}.

Lemma 19. All of the permutations in each equivalence class have the same parity.

Proof. Each 1234 ↔ 3412 pattern-replacement consists of two transpositions. Since parity is invariant under both transpositions, the lemma follows.

In the remainder of the section, we work to be able apply induction. To do so, we examine a sub-standardization of an arbitrary primary permutation formed by excluding one letter. The goal is to find conditions on the letter removed such that the sub-standardization is also primary, hence allowing us to apply the inductive hypothesis to the sub-standardization. There are two possible problems with this approach: either the sub-standardization is adjacent to a leader permutation, or the sub-standardization could start with its largest letter or end in 1. The latter is easily dealt with, and we put it off to Case 2 of Lemma 25. The former, however, can be dealt with using an intuitive claim that we prove in Lemma 22. We show in Lemma 22 that, if removing a certain letter results in a permutation adjacent to a leader permutation, we can instead choose a different letter, with some constraints, to yield a permutation that is not adjacent to a leader permutation.

We start by defining and proving some basic results about semi-leader permutations.

Definition 20. We define a semi-leader permutation to be a permutation that is either a leader permutation or the decreasing permutation.

Two equivalent definitions are that a permutation is a leader permutation if it is the plus-composition of two (possibly empty) decreasing patterns [2], and that a permutation is

a leader permutation if it is a member of the geometric grid class of (\begin{matrix}0 & −1 \\ −1 & 0 \end{matrix}) [1].

In the following lemmas, we say that a transposition of a sub-standardization swaps the same physical letters as it did in the original permutation.

Lemma 21. For any permutation ρ ∈ S_{k} with k ≥ 5, distinct letters a, b in ρ, and transposition τ not operating on a or b such that τ · ρ_{−(a)} is a leader permutation, τ · ρ_{−(a,b)} is the unique semi-leader permutation adjacent to ρ_{−(a,b)}.

Proof. To begin, note that the standardization of any semi-leader permutation with one letter removed is always a semi-leader permutation.

We first show that τ · ρ_{−(a,b)} is a semi-leader permutation (note that τ does not involve a or b). In particular, τ · ρ_{−(a)} is a leader permutation, and thus removing b to get τ · ρ_{−(a,b)} results in a semi-leader permutation.

Moreover, τ · ρ_{−(a,b)} is the unique semi-leader permutation adjacent to ρ_{−(a,b)}. In particular, any other such semi-leader permutation x would differ from τ · ρ_{−(a,b)} in at most 4 positions and would therefore have to agree with τ ·ρ_{−(a,b)} in at least one position. Whenever two semi-leader permutations of the same length agree in at least one position, they must be the same permutation, meaning that x would actually equal τ · ρ_{−(a,b)}.

Lemma 22 (Creating primary permutations). Let ρ ∈ S_{k} with k ≥ 5 be a primary permutation. Suppose there exists a letter a in ρ such that removing a results in a sub-standardization ρ_{−(a)} that is leader-permutation-adjacent. Let τ_{1} be the transposition taking ρ_{−(a)} to a leader permutation, and suppose b is some letter in both ρ and ρ_{−(a)} that is not operated on by τ_{1} and such that a ≢ b ± 1 (mod k). Also, suppose that if τ_{1} operates on two letters with only one letter of ρ_{−(a)} between them, then b is not that letter. Then the sub-standardization ρ_{−(b)} obtained by removing b from ρ is not adjacent to any leader permutation.

Proof. Suppose, for the sake of contradiction, that τ_{2} · ρ_{−(b)} is a leader permutation for some transposition τ_{2}.

If τ_{2} operates only on elements of ρ_{−(a,b)} (i.e., τ_{2} does not involve a), we can conclude that τ_{2} = τ_{1} by Lemma 21. In particular, τ_{2} · ρ_{−(a,b)} is a semi-leader permutation because τ_{2} · ρ_{−(b)} is a leader permutation. Thus τ_{1} · ρ_{−(a,b)} = τ_{2} · ρ_{−(a,b)}, so τ_{1} = τ_{2}.

However, if τ_{1} = τ_{2} then τ_{1} takes both ρ_{−(b)} and ρ_{−(a)} to leader permutations. We claim that this then implies that ρ is also a leader permutation, a contradiction. This is because when we add b to ρ_{−(b)} to get ρ, b is not adjacent to a (recall that a ≢ b ± 1 (mod k)), so the letters that b is adjacent to in ρ_{−(a)} remain adjacent to b in ρ (although their values may be shifted by 1), ensuring that ρ is a leader permutation.

It remains to consider the case in which τ_{2} operates on a. In this case, we define τ_{2} ·ρ_{−(a,b)} to be the standardization of τ_{2} ·ρ_{−(b)} with a removed. Now, τ_{2} moves only one letter in ρ_{−(a,b)} and results in a semi-leader permutation (as τ_{2} · ρ_{−(a,b)} is contained in τ_{2} · ρ_{−(b)}, which is a semi-leader permutation). Thus, there are two semi-leader permutations x = τ_{1} · ρ_{−(a,b)} and y = τ_{2} · ρ_{−(a,b)}, each of length k − 2, such that we can get from x to y by swapping two letters (applying the inverse of τ_{1}, which is itself) and then moving one letter (the end result of τ_{2} after removing b). We place each letter of the permutation on a circle in clockwise order starting with the first letter. Observe that, up to rotation, all semi-leader permutations are equivalent in such a circular formation, implying that on the circle x and y are equivalent up to rotation. Let τ_{1} swap letters j, k. An example of a semi-leader permutation placed on a circle with τ_{1} applied is shown in Figure 3. Note that, because τ_{1} does not swap adjacent letters, neither j nor k are adjacent to any of the same letters as they were before τ_{1}. However, moving one letter can remove at most three adjacencies (2 containing the moved letter and 1 for the letters it moved between), so one of the four new adjacencies with j or k remains. Hence, after performing transposition τ_{1} and moving one letter, the circle is not the same up to rotation, a contradiction.

Figure 3: Example of a semi-leader permutation of length 8 placed on a circle, where τ_{1} swaps 3 and 6 and creates four new adjacencies involving 3 or 6, namely (4, 6), (6, 2), (3, 5), and (7, 3).

We now proceed with a definition and then show that 2 is both a lower and upper bound on the number of primary classes in the following two lemmas, respectively.

Definition 23. Define Π_{n} = 123 ⋯ n and Ψ_{n} = 123 ⋯ (n − 3)(n − 2)n(n − 1).

Lemma 24. There are at least two primary classes in S_{n} for n ≥ 7.

Proof. Let n ≥ 7. First of all, note that the permutations Π_{n} and Ψ_{n} are both primary permutations. In particular, for n ≥ 7, no transposition takes Π or Ψ to a leader permutation because for any transposition τ, both τ ·Π and τ ·Ψ contain 123 patterns. Further, the parity of the number of inversions is even in Π and odd for Ψ, so they are in two distinct primary classes by Lemma 19. This proves that 2 is a lower bound on the number of primary classes.

Lemma 25. There are exactly two primary classes in S_{n} for n ≥ 7.

Proof. Let n ≥ 7. We have, by Lemma 24, that 2 is a lower bound on the number of primary classes. To proceed, we use induction to show 2 is an upper bound on the number of primary classes.

The base cases of n = 7, 8, 9, 10 are verifiable by computer.

For the inductive step, we assume that Lemma 25 holds for an n = k − 1 with k − 1 ≥ 9 and prove that Lemma 25 holds for n = k. To do so, we show that any primary permutation in S_{k} is equivalent to one of Π_{k} and Ψ_{k}. Let ρ ∈ S_{k} be an arbitrary primary permutation; we show that ρ is equivalent to either Π_{k} or Ψ_{k} depending on the parity of the number of inversions ρ contains. Because primary classes are nontrivial, we can find some 1234 or 3412 pattern in ρ. Take an arbitrary such pattern q. Since k ≥ 10, we can now find some letter a inside of ρ such that a ≠ 1, a ≠ k, a is neither the first nor last letter in ρ, and q does not contain a. Now, we consider the sub-standardization ρ′ ∈ S_{k−1} of ρ that excludes a. Because a was not in q, ρ′ still contains q and thus is part of a nontrivial class, and because a was neither n nor the first letter in ρ, ρ′ does not start with n. Similarly, ρ′ does not end with 1. We proceed by cases based on whether ρ′ is adjacent to a leader permutation.

Case 1: ρ′ is a primary permutation. In this case, by the inductive hypothesis, ρ′ is equivalent to either Π_{k−1} or Ψ_{k−1}. Hence, in ρ, we can use the equivalence relation to reorder the elements excluding a to form Π_{k−1} or Ψ_{k−1}. Call this new permutation after the reordering ρ_{1}. Now, observe that because a was not the first letter in ρ but both Π_{k−1} and Ψ_{k−1} begin with 1, 1 is the first letter in ρ_{1}. Moreover, the second letter in ρ_{1} is either 2 or a, neither of which equals n.

Consider the sub-standardization ρ_{1}′ created by excluding the 1 in ρ_{1}. Note that ρ_{1}′ neither starts with n nor ends with 1. Additionally, we attain a 1234 ⋯ (k − 4) pattern in ρ_{1}′ by ignoring the a and the final two letters of ρ_{1}′. Such a pattern clearly must contain a 1234 pattern and can never occur in a permutation adjacent to a leader permutation because k − 4 ≥ 5, so ρ_{1}′ is primary. Since ρ_{1}′ is primary, by our inductive hypothesis it is equivalent to either Ψ_{k−1} or Π_{k−1}. In either case rearranging the sub-permutation of ρ_{1} that ρ_{1}′ corresponds to yields that ρ_{1}, and hence ρ, must be equivalent to either Ψ_{k} or Π_{k}, as desired.

Case 2: ρ′ is not primary. In this case, consider some letter b in ρ such that

1. if the second letter of ρ is k, b is not the first letter in ρ

2. if the second to last letter of ρ is 1, b is not the last letter in ρ

3. if the last letter in ρ is 2, b ≠ 1

4. if the first letter in ρ is k − 1, b ≠ k.

Next we show that, as long as k ≥ 11, it is possible to select b satisfying conditions (1), (2), (3), and (4) as well as the conditions of Lemma 22 (which we reiterate shortly). Let τ be the transposition taking ρ′ to a leader permutation. Note that these conditions imply that the sub-standardization ρ^{⋆} ∈ S_{k−1} attained by removing b from ρ neither ends in 1 nor starts with k. Further, note that if the if-conditions for (2) and (3) both take effect, this would force ρ to end with 12, and either the 1 or the 2 would be operated on by τ as no leader permutation ends with 12. Similarly, if the if-conditions for (1) and (4) both take effect, ρ would start with (k − 1)k, and either (k − 1) or k would be operated on by τ. Also, it is easy to see that both letters operated by τ must be a part of any 1234 or 3412 pattern in ρ′, because the 3-letter subsequences of these patterns do not appear in leader permutations. Hence, we if we take b satisfying (1), (2), (3), and (4) and we require b to satisfy the conditions of Lemma 22 (meaning that b is not contained in the pattern q; b is not operated on by τ; b ≠ a; b ≢ a ± 1 (mod k); and if τ swaps two letters separated by only one letter, b is not that letter) then in total we exclude at most 10 elements from the possible choices (in particular, (1), (2), (3), and (4) exclude at most two elements not already excluded as part of τ). This means that as long as k ≥ 11, we can find such a b in ρ.

Then, by Lemma 22, the permutation pattern formed by removing b from ρ must be a primary permutation, so this case reduces to Case 1.

These two cases complete the induction, establishing that the number of primary classes is exactly 2.

5 Putting the proof together

We now finish proving Theorem 1 by combining the lemmas proven in the previous sections.

Theorem (Theorem 1 restated). For n ≥ 7, the number of nontrivial equivalence classes of S_{n} under the \{1234, 3412\}-equivalence is \frac{n^{3}+6n^{2}−55n+54}{6}.

Proof. First of all, by Lemma 7, we see that it is sufficient to show that there are exactly n+1 classes of permutations in S_{n} not beginning with n or ending with 1. Every such permutation is in exactly one of two categories, the set of permutations adjacent to leader permutations and primary permutations. By Proposition 13 there are n−1 classes of permutations adjacent to a leader permutation, and by Lemma 25 there are exactly two primary classes. Thus, in total we find that permutations not beginning in n or ending in 1 fit into n − 1 + 2 = n + 1 classes, as desired. By Lemma 7, this completes the proof.

6 Acknowledgments

The authors would like to thank Canada/USA Mathcamp for providing the opportunity to conduct this research. The authors would also like to thank William Kuszmaul for his mentorship on the project and for suggesting the research problem.

References

[1] M. Albert, M. Atkinson, M. Bouvel, N. Ruškuc, and V. Vatter, Geometric grid classes of permutations, Trans. Amer. Math. Soc. 365 (2013), 5859–5881.

[2] M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Math. 300 (2005), 1–15.

[3] M. H. Albert, M. Elder, A. Rechnitzer, P. Westcott, and M. Zabrocki, On the Stanley– Wilf limit of 4231-avoiding permutations and a conjecture of Arratia, Adv. in Appl. Math. 36 (2006), 96–105.

[4] M. Bóna, The limit of a Stanley–Wilf sequence is not always rational, and layered patterns beat monotone patterns, J. Combin. Theory Ser. A 110 (2005), 223–235.

[5] M. Bóna, New records in Stanley–Wilf limits, European J. Combin. 28 (2007), 75–85.

[6] A. Claesson, Generalized pattern avoidance, European J. Combin. 22 (2001), 961–971.

[7] V. Fazel-Rezai, Equivalence classes of permutations modulo replacements between 123 and two-integer patterns, Electron. J. Combin. 21 (2014), Article P2.47.

[8] The international conference on permutation patterns, 2020. Available at https://

    permutationpatterns.com.

[9] S. Kitaev, Patterns in Permutations and Words, Springer Science & Business Media, 2011.

[10] D. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific J. Math. 34 (1970), 709–727.

[11] W. Kuszmaul, Counting permutations modulo pattern-replacement equivalences for three-letter patterns, Electron. J. Combin. 20 (2013), Article P10.

[12] W. Kuszmaul, Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations, Math. Comp. 87 (2018), 987–1011.

[13] W. Kuszmaul and Z. Zhou, New results on families of pattern-replacement equivalences, Discrete Math. 343 (2020), 111878.

[14] J. B. Lewis, Pattern avoidance for alternating permutations and Young tableaux, J. Combin. Theory Ser. A 118 (2011), 1436–1450.

[15] S. Linton, J. Propp, T. Roby, and J. West, Equivalence classes of permutations under various relations generated by constrained transpositions, J. Integer Sequences 15 (2012), Article 12.9.1.

[16] M. Ma, New results on pattern-replacement equivalences: generalizing a classical theorem and revising a recent conjecture, preprint, 2020. Available at https://arxiv.org/

    abs/2009.04546.

[17] A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley–Wilf conjecture, J. Combin. Theory Ser. A 107 (2004), 153–160.

[18] J.-C. Novelli and A. Schilling, The forgotten monoid, RIMS Kôkyûroku Bessatsu 8 (2008), 71–83.

[19] A. Pierrot, D. Rossin, and J. West, Adjacent transformations in permutations, in FP-SAC 2011, Discrete Math. Theor. Comput. Sci. Proc., 2011, pp. 765–776.

[20] R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383–406.

[21] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, 2020. Available at

    https://oeis.org.

[22] R. P. Stanley, An equivalence relation on the symmetric group and multiplicity-free flag h-vectors, J. Comb. 3 (2012), 277–298.

2020 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: permutation, permutation pattern, equivalence class, integer sequence, patternreplacement, transposition.

(Concerned with sequence \underline{A330395}.)

Received June 29 2020; revised versions received September 18 2020; October 16 2020. Published in Journal of Integer Sequences, October 17 2020.

Return to Journal of Integer Sequences home page.