Abstract

Let S_n be the symmetric group of all permutations of n letters. We show that there are precisely 64 Wilf classes consisting of exactly 2 symmetry classes of subsets of four 4-letter patterns.

1. Introduction

Let be the set of all permutations of We say a permutation is standard if its support set is an initial segment of the positive integers, and for a permutation whose support is any set of positive integers, is the standard permutation obtained by replacing the smallest entry of by 1, the next smallest entry by 2, and so on. For example, A permutation avoids a sequence if there is no subsequence of for which In this context, is called a pattern. For a set of patterns, we denote the set of permutations of that avoid all the patterns in T by For instance, Knuth ⁴ showed that

where denotes the nth Catalan number. The generating function for the Catalan numbers is given by and satisfies

Two sets of patterns T and belong to the same symmetry class if and only if can be obtained by the action of the dihedral group of order eight – generated by the operations inverse, reverse and complement – on T. The sets of patterns T and R belong to the same Wilf class (or are Wilf-equivalent) if and only if for all Let wk be the number of distinct Wilf classes of subsets of exactly k patterns in Le ⁶ established that Recently, Callan, Mansour and Shattuck ^{2, 3} studied the distinct Wilf classes of subsets of exactly three 4-letter patterns and showed that Mansour and Schork ^{7, 8, 9} showed that

Toward the goal of finding w₄, we establish the following result.

Theorem 1. The number of Wilf classes consisting of exactly 2 symmetry classes of subsets of 4 patterns in (2-Wilf classes) is 64.

2. Proof of Theorem 1

Using software of Kuszmaul ⁵ we determined all symmetry classes of 4 patterns in and the sequence for a representative quadruple T in each symmetry class. Considering the pairs T, R with shows that there at most 64 2-Wilf classes of subsets of 4 patterns in , see Table 1 in the appendix below. Then we used the insertion encoding algorithm (INSENC) ¹² on the symmetry classes in Table 1 and successful outcomes, always a rational generating function, are referenced by “INSENC”.

So, to prove Theorem 1, in the following subsections we find an explicit formula for the generating function whenever is nonrational. The 15 cases where is rational and INSENC fails are marked “EX” in Table 1; their proofs are omitted and left to the interested reader. The following notation and definitions will be useful. A permutation expressed as where and for is said to have m left-right maxima (at ). Given nonempty sets of numbers S and T, we will write to mean (with the inequality vacuously holding if S or T is empty). In this context, we will often denote singleton sets simply by the element in question. Also, for a number , S − k means the set

Note that all three patterns contain 231.

Lemma 2. Let T = {1342, 2314, 3412, 4231}. The generating function for T -avoiders with 2 leftright maxima is given by

Proof. Let be the generating function for T-avoiders with 2 left-right maxima where has d letters smaller than i. If d = 0, then and independently avoid 231, and so Now let and be the letters in smaller than i. These letters occur in decreasing order (to avoid 3412). Since avoids 1342, 4231, we can write as

where Since avoids 2314, we also have Note that , are decreasing, and both avoid 231. Thus Summing over d ≥ 1 and using the expression for we obtain the required result.

Theorem 3. Let T = {1342, 2314, 3412, 4231}. Then

Proof. Let be the generating function for T -avoiders with m left-right maxima. Clearly, and Lemma 2 gives For with suppose has left-right maxima. Since avoids 1342 and 2314, we see that for all and can be written as with and (to avoid 1342), and is decreasing (to avoid 3412).

If then avoids T if and only if each of avoids 231. If then are all decreasing. Thus, Summing over m ≥ 3, we obtain

Substituting for and solving for we complete the proof.

Again, all three patterns contain 231.

Lemma 4. Let T = {1342, 2314, 3412, 2431}. The generating function for T -avoiders with 2 leftright maxima is given by

Proof. As in Lemma 2, let be the generating function for T-avoiders with 2 left-right maxima. Let d be the number letters smaller than i in . If d = 0, then and independently avoid 231, and so the contribution is Now let d ≥ 1 and be the letters in smaller than i. These letters occur in decreasing order (to avoid 3412). Since avoids 1342, 2431, we can write as

where Since avoids 2314, we also have Also, both avoid 231. If is decreasing, the contribution is otherwise, which implies a contribution of Add all the contributions to complete the proof.

Theorem 5. Let T = {1342, 2314, 3412, 2431}. Then

Proof. Let be the generating function for T -avoiders with m left-right maxima. Clearly, and Lemma 4 gives For with m ≥ 3, suppose has m ≥ 3 left-right maxima. Since avoids 1342, 2314, 3412, we see that for all and can be written as with and (to avoid 1342), and is decreasing (to avoid 3412).

If then avoids T if and only if each of avoids 231. If then and avoids both 132 and 231. Thus, by ^{4, 11}, we have

Summing over m ≥ 3, we obtain

Substituting for and solving for we complete the proof.

Note that all three patterns contain 231.

Theorem 6. Let T = {1342, 2314, 2413, 4231}. Then

Proof. Let be the generating function for T -avoiders with m left-right maxima. Clearly, and

To find suppose has 2 left-right maxima. If then we have a contribution of Otherwise, since avoids T, we have that

where is the maximal letter of that smaller than i, and each of avoids 231. So we have a contribution of Hence,

For with m ≥ 3, suppose has m ≥ 3 left-right maxima. Since avoids 1342, 2314, 2413, we see that for all and can be written as with and (to avoid 1342). If then avoids T if and only if each of avoids 231. If then each of , is decreasing and avoids 231. Thus,

Summing over m ≥ 3, we obtain

Substitute for and solve for to complete the proof.

Note that all three patterns contain 132.

Theorem 7. Let T = {1324, 1342, 2143, 2431}. Then

Proof. Let be the generating function for T -avoiders with m left-right maxima. Clearly, and

To find suppose has 2 left-right maxima. If then we have a contribution of Otherwise, by considering whether or we get contributions of or Hence,

For with m ≥ 3, suppose has m ≥ 3 left-right maxima. Since avoids 1324, 1342, we see that for all and can be written as with and (to avoid 2431). Note that (to avoid 1324 and 1342). If then we have a contribution of Otherwise, (to avoid 2143) and avoids T if and only if avoids 132 and avoids T, so we have a contribution of

Thus,

Summing over m ≥ 3, we obtain

Substitute for and solve for to complete the proof.

Lemma 8. Let T = {2341, 4123, 1342, 1243}. Let (respectively, and ) be the generating function for the number of T-avoiders of the form (respectively, such that and ). Then, for all d ≥ 1,

and

Proof. Let us write an equation for the generating function Let If n= d + 2 then we have a contribution of Thus, we can assume that n > d + 2. By considering the position of n − 2 − d ≥ 1, we have

• If belongs to then so avoids T if and only if

avoids T. Thus we have a contribution of

• If belongs to then since avoids 1243 and 4123, we see that there is no letter smaller than on its left side. Thus, we have a contribution of

• If belongs to (resp. ), then we have a contribution of (resp. ).

Adding all contributions, we have, for d ≥ 1,

By restricting the above proof to the case we obtain that for all d ≥ 1,

It is not hard to see that for all d ≥ 1. To find a formula for , we define to be the generating function for T-avoiders of the form

such that and has e letters. Since avoids 4123, these e letters are decreasing. By direct calculations, we see that and for all Hence,

We leave as an exercise for the interested reader (Hint: consider the position of the letter n − 2 − d).

Lemma 9. The generating function for T-avoiders of the form is

Proof. Let be the number of permutations Then, (details left to the reader)

with and where is the Catalan number (number of 123-avoiders of length n).

Define Then the above recurrence can be written as

with and

Define Multiplying the last recurrence by and summing over

By taking we obtain

as required.

Lemma 10. The generating function for T -avoiders with 2 left-right maxima is

Proof. Suppose with exactly 2 left-right maxima. Denote the contribution of the cases and by H and so that

To find a formula for H, we distinguish the cases has a subsequence of two letters ab such that i < a < b, or not. In the former case, the contribution is In the latter case, by Lemma 8, the contribution is where

Lemma 9 shows that Therefore,

and the result follows after algebraic simplification.

Theorem 11. Let T = {2341, 4123, 1342, 1243}. Then

Proof. Let be the generating function for T -avoiders with m left-right maxima. Clearly, and Lemma 10 gives

For with m ≥ 3, suppose

has m ≥ 3 left-right maxima. Since avoids T, we see that Thus, avoids T if and only I avoids T. Therefore,

By summing over m, we have

which completes the proof.

Theorem 12. Let T = {2341, 4123, 1342, 1234}. Then

Proof. To write a formula for let If avoids 123, the contribution is Otherwise, let be an occurrence of 123 such that a, a+b and a+b+c are minimal. If then can be written as such that has exactly 2 left-right maxima and and avoids 123. Thus, we have a contribution of

If then can be written as

where and are decreasing and Thus, we have a contribution of The result follows by adding contributions.

Theorem 13. Let T = {2314, 3124, 1342, 1423}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

To find suppose with 2 left-right maxima. It is not hard to see that avoids T if and only if can be decomposed as such that is a permutation on that avoids 123 and where cannot be decomposed as with and are not empty. Hence,

For with m ≥ 3, suppose

has m left-right maxima. Since avoids T, we see that for all and with and Thus, avoids T if and only if are all decreasing and avoids T. Hence,

Summing over m, we have

and solving for completes the proof.

Theorem 14. Let T = {2413, 3142, 1324, 1243}. Then

Proof. Let be the generating function for T -avoiders with m left-right maxima. Clearly, and

For with m ≥ 2, suppose

has m left-right maxima. Since avoids T, we see that where and If then avoids T if and only if avoids 132 and avoids T. Otherwise, avoids T is and only if is decreasing, is not empty and avoids both 132 and 213, and avoids T. Thus, by ^{4, 11}, we have

Summing over m, we have

and solving for completes the proof.

Theorem 15. Let T = {2314, 1342, 1324, 4123}. Then

Proof. To write a formula for let If avoids 123, then we have a contribution of Otherwise, let be an occurrence of 123 such that a, a+b and a+b+c are minimal. W consider the following four cases:

• and with and where avoids {123, 132, 213}, avoids {213, 231, 123}, and avoids 123. Thus, we have a contribution of where

see ^{4, 11}.

• and Here,

where and avoids 123. Thus, we have a contribution of

• There is a letter x on the right side of greater than Here, where avoids {4123, 213, 231}, avoids {123, 132, 231}, and avoids 123. Thus, we have a contribution of where

• There is a letter x between and such that and there is no letter x on the right side of greater than When a = 1, has the form

where and avoids 123, giving a contribution of When has the form

where and avoids 123, giving a contribution of

Adding all the contribution, we obtain as claimed.

Theorem 16. Let T = {2314, 1342, 4123, 1234}. Then

Proof. Let If avoids 123, the contribution is Otherwise, let be an occurrence of 123 such that a, a + b and a + b + c are minimal. In this case can be written as

where avoids 123. Thus, the contribution is and the result follows.

Theorem 17. Let T = {2413, 3142, 3412, 2341}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

Now suppose m ≥ 2 and has m left-right maxima. Since avoids 2341, we have for all j. If then the contribution is Otherwise, since avoids 2413, we have and

where which leads to contribution of Thus,

for all m ≥ 2. Summing over m, we find that

and solving for completes the proof.

Theorem 18. Let T = {2413, 3142, 1243, 1432}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

To find suppose has 2 left-right maxima. If the contribution is If and is not empty, the contribution is If and is not empty, the contribution is Otherwise, and has a letter smaller than so we have a contribution of Hence,

Now suppose m ≥ 2 and has m left-right maxima. Since avoids 1243, we have for all j. If then the contribution is Otherwise, has a letter between and so is decreasing and where and is nonempty increasing. Also, and avoids Thus,

for all m ≥ 3. Summing over m, we find that the generating function satisfies

Substituting for and then solving for completes the proof.

Note that all four patterns contain 231.

Theorem 19. Let T = {2413, 3142, 1342, 2341}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

To find suppose has 2 left-right maxima. If then we have a contribution of where counts the number of 231-avoiders of length n. Otherwise, can be written as where is nonempty and avoids T, which gives contribution of Hence,

Now let m ≥ 3 and suppose has m left-right maxima. Then avoids T if and only if for and avoids T and avoids 231 for all Thus,

Summing over m, we find that the generating function satisfies

and solving for completes the proof.

Note that all four patterns contain 132.

Theorem 20. Let T = {2143, 1324, 1342, 1423}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

To find suppose has 2 left-right maxima. If has a letter greater than i, then can be written as where avoids T, and so we have a contribution of Otherwise, that is, if i = n − 1, we have a contribution of Thus,

Now let m ≥ 3 and suppose has m left-right maxima. If then

and avoids 132 for and avoids T, which leads to contribution of where counts 132-avoiders of length n. Otherwise, has a letter greater than so can be written as

where avoids T, which gives a contribution of Thus,

Summing over m, we find that the generating function satisfies

and solving for completes the proof.

Theorem 21. Let T = {3142, 2314, 1342, 2431}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

To find suppose has 2 left-right maxima. If then we have a contribution of where counts the number of 231-avoiders of length Otherwise, has a letter smaller than i. If is decreasing and then and the contribution is and if is sequence and has a letter greater than i, we have a contribution of If is not decreasing, then we have a contribution where is the generating function for {231, 132}-avoiders ¹¹. Thus,

To find suppose has 3 left-right maxima. If then by considering whether has a letter smaller than i or not, we get a contribution of Otherwise, we have a contribution of Thus,

Now let m ≥ 4 and suppose has m left-right maxima. Since avoids T, we have for and has no letters between and By considering whether is empty or not, we get a contribution of

Summing over m, we find that

Substituting for and solving for completes the proof.

Theorem 22. Let T = {2413, 2431, 2314, 1342}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

To find suppose has 2 left-right maxima. The contribution of the case is If then and is not empty and both avoid 231, and so the contribution is Hence,

Now let m ≥ 3 and suppose has m left-right maxima. Since avoids T, we have either with or with

and The contribution of first case is and the contribution of the second case is for the cases is empty or not, where ¹¹. Hence,

Summing over m, we obtain

and solving for completes the proof.

Theorem 23. Let T = {3412, 3421, 2413, 3241}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

To find a formula for with m ≥ 2, suppose has m leftright maxima. If the contribution is Otherwise, since avoids {3412, 3421}, there exists such that contains a letter between and Since avoids {3412, 3421, 2413}, we have that and where avoids {231, 213}. Thus, for fixed we have a contribution of Therefore,

Summing over m ≥ 2, we obtain

and solving for completes the proof.

Theorem 24. Let T = {3142, 1342, 1423, 1243}. Then

Proof. Let be the generating function for T-avoiders with m left-right maxima. Clearly, and

To find a formula for suppose has 2 left-right maxima. If then and we have a contribution of Otherwise, can be written as where and is decreasing, and each avoids T. So we have a contribution of Hence,

To find a formula for with m ≥ 3, suppose has m left-right maxima. If the contribution is Otherwise, leading to a contribution of Thus,

By summing over m ≥ 3, we obtain

and solving for completes the proof.

Define and to be the number of permutations in Define and

Since avoids 2314 and 2331, for Also, it is not hard to see for and

Thus,

If with then the leftmost letter of is either or Thus, for Similarly, for all Moreover, Thus,

Hence,

If with then contains the subword Hence, for If with then

Thus,

and

Define . Then

which is equivalent to

for n ≥ 2, with Define

Multiplying the last recurrence by and summing over n ≥ 2, we obtain

Taking , we obtain

Now, since we obtain the following result.

Theorem 25. Let T = {2134, 2314, 2341, 1423}. Then

Theorem 26. Let T = {1234, 2314, 2341, 1423}. Then

Proof. To write a formula for let If avoids 123, then we have a contribution of Otherwise, let be an occurrence of 123 such that a, a+b and a+b+c are minimal. Since avoids T, we see that can be written as

where Since avoids 123 and has the form with the contribution is

Therefore, by adding all the contribution, we obtain as claimed.

Define and set Note that avoids {213, 1342, 2341, 1423} if and only if avoids {123, 213} and avoids {312, 213, 231}. Thus, by ¹¹, we have

and so for all

Define where is the number of permutations of the form in

Lemma 27. For all n ≥ 3,

Proof. Let in If and then is increasing, so for all Since we have and for Thus,

Let us write a formula for Let with Then either or with The first case contributes For the second case, since avoids 1423 we see that which leads to a contribution of Hence, for all

Since T contains 1432, Set

Then

which, since implies

Hence,

which implies that a required.

Define

Lemma 28. We have

Proof. Let us write an equation for Since we have

Let with We claim

(1)

for

To prove (1), let with If then contains the subword so by removing the letter we obtain which implies that (1) holds for Now, assume that with Note that avoids T if and only if avoids T, for all So for all Thus,

Since has the form

the number such permutations is given by

Thus,

which leads to

An avoider has the form with or and so

Hence,

as required.

Define So (1) is equivalent to

and by summing over we have

Also, and To solve this recurrence, we define Then, we have

(2)

with

Define Multiplying (2) by and summing over n ≥ 3, we obtain

By taking we have

By Lemma 27,

with Thus, by Lemma 28, we obtain

Solving for we get the following result.

Theorem 29. Let T = {2134, 1342, 2341, 1423}. Then

Let T = {2134, 1342, 2341, 1243}. Define

and

where is the number of permutations in

Lemma 30. For all n ≥ 3,

Proof. The permutation in if and only if in Thus, for all If with and then contains either 1243 or 2341, so If then is increasing, and so If with then contains 2134, thus If then where avoids {213, 132, 2341}, so

Now, assume that with Then where avoids {213, 1342, 2341, 1243}. Thus, as defined in Sec. 2.11.1.

Hence,

Lemma 31. We have

Proof. Define and

By similar arguments as in the proof of Lemma 28, we obtain

with and So and, for

(3)

Define Multiplying (3) by and summing over we obtain

By taking we have

By Lemma 30, we have

Thus, by Lemma 31, we obtain

Solving for , we get the following result.

Theorem 32. Let T = {2134, 1342, 2341, 1243}. Then

References