The Number of Permutations Avoiding a Set of Generalized Permutation Patterns

Yonah Biers-Ariel Department of Mathematics Rutgers University Piscataway, NJ 08854 USA

                    yb165@math.rutgers.edu

Abstract We prove a conjecture that the sequence defined recursively by a_{1} = 1, a_{2} = 2, a_{n} = 4a_{n−1}−2a_{n−2} counts the number of length-n permutations avoiding the four generalized permutation patterns 1-32-4, 1-42-3, 2-31-4, and 2-41-3.

1 Introduction

Let (a_{n})_{n≥1} be defined recursively by a_{1} = 1, a_{2} = 2, and a_{n} = 4a_{n−1} − 2a_{n−2} for n ≥ 3. Callan [2, \underline{A006012}] conjectured that a_{n} gives the number of permutations of length n for which no subsequence abcd has the following two properties: b and c occur consecutively in the permutation and max{a, c} < min{b, d}. In this paper, we prove Callan’s conjecture by first restating it in terms of generalized pattern avoidance. Next, we show that the permutations that avoid the relevant generalized patterns are exactly the same ones that avoid a similar set of ordinary patterns, and we finally count the number of permutations that avoid this set of ordinary patterns.

2 Preliminaries

First, we rewrite the conjecture in the language of pattern avoidance using the dashed notation introduced by Babson and Steingrímsson [1]. Therefore, we define a pattern to be a permutation π_{1} ⋯ π_{k} where some of its elements may be separated by dashes. A subsequence of a permutation is an occurrence of a pattern if

(i) all the elements have the same relative order as the elements of the pattern; and

(ii) if there is no dash between the i^{th} and i + 1^{th} elements of the pattern, then the i^{th} and i + 1^{th} elements of the subsequence occur consecutively in the permutation.

We say that a permutation avoids a pattern if it does not contain any occurrence of the pattern, and a permutation avoids a set of patterns if it does not contain any occurrence of any of them. If A is a set of patterns, then Av(A) is the set of permutations that avoid them, and Av_{n}(A) is the set of length-n permutations that avoid them. The following two examples should help clarify these definitions.

Example 1. The permutation 251346 contains the subsequence 5146 which is an occurrence of the pattern 3-1-24 because the elements of the subsequence occur in the same relative order as 3124, and the 4 and 6 are consecutive in the original permutation. Note that the 5 and 1 are also consecutive - that is allowed but not necessary.

Example 2. The permutation 251346 avoids 32-1-4; i.e.,

251346 ∈ Av_{6}({32-1-4}) ⊆ Av({32-1-4}).

We are now ready to rewrite the conjecture using this notation. To express it and the theorems in the next section concisely, we let A = {1-32-4, 1-42-3, 2-31-4, 2-41-3} and B = {1-3-2-4, 1-4-2-3, 2-3-1-4, 2-4-1-3}.

Proposition 3. A subsequence of a permutation abcd has the properties that b and c occur consecutively in the permutation and max{a, c} < min{b, d} if and only if that subsequence is an occurrence of a pattern in A.

Proof. Let abcd be a subsequence with the two indicated properties. Suppose that a < c and b < d. Because max{a, c} < min{b, d}, it follows that a < c < b < d, and so abcd is an occurrence of 1-3-2-4. Also, because b and c occur consecutively, we can remove the middle dash and say that abcd is an occurrence of 1-32-4. If a > c or b > d, we can apply the same argument as long as we switch 1-32-4 with another appropriately chosen member of A.

Conversely, suppose that abcd is an occurrence of a pattern in A. In every pattern in A, the first and third elements are 1 and 2, while the second and fourth are 3 and 4. Therefore, we have max{a, c} < min{b, d}. Further, since there is no dash between the second and third elements of any pattern in A, it must be that b and c occur consecutively.

Using Proposition 3, we rewrite Callan’s conjecture as

a_{n} = | Av_{n}(A)|.  (1)

3 Main results

We will prove two theorems. The first is that Av(A) and Av(B) are the same set. In particular, this theorem establishes that | Av_{n}(A)| = | Av_{n}(B)| for n ≥ 1. The second theorem is that a_{n} = | Av_{n}(B)| for n ≥ 1, so together these two theorems prove that Equation 1 holds.

Theorem 4. Let A and B be the sets defined in Section 2. Then Av(A) = Av(B).

Proof. It is immediately clear that any permutation containing an occurrence of an element of A must contain an occurrence of an element of B, so we only need to show that the converse is also true. Let π be a permutation. First, recall that a subpermutation π_{a}π_{b}π_{c}π_{d} of π is an occurrence of a pattern in A if and only if c = b+1 and max{π_{a}, π_{c}} < min{π_{b}, π_{d}}. Similarly, a subpermutation π_{a}π_{b}π_{c}π_{d} of π is an occurrence of a pattern in B if and only if max{π_{a}, π_{c}} < min{π_{b}, π_{d}}.

Choose any element of B, and suppose that π contains an occurrence of this element. As noted above, this means that we can find a < b < c < d such that max{π_{a}, π_{c}} < min{π_{b}, π_{d}}. Let e be the largest index less than c such that π_{e} > max{π_{a}, π_{c}}, i.e., e = max{i : i < c, π_{i} > max{π_{a}, π_{c}}}. Because b is an element of {i : i < c, π_{i} > max{π_{a}, π_{c}}}, it follows that e exists and a < b ≤ e < e + 1 ≤ c < d. Now, we claim that π_{a}π_{e}π_{e+1}π_{d} is an occurrence of a pattern in A. Obviously, e + 1 = e + 1, and so it remains to check that max{π_{a}, π_{e+1}} < min{π_{e}, π_{d}}. Because max{π_{a}, π_{c}} < min{π_{b}, π_{d}}, we conclude that π_{a} < π_{d}, and by the choice of e, we also have π_{a} < π_{e}. Now, either e+1 = c, in which case π_{e+1} = π_{c}, or else π_{e+1} < max{π_{a}, π_{c}} because otherwise we would have chosen e+1 as the max{i : i < c, π_{i} > max{π_{a}, π_{c}}} instead of e. It follows that π_{e+1} ≤ max{π_{a}, π_{c}} < π_{d}, π_{e} for the same reasons as π_{a}. Therefore, max{π_{a}, π_{e+1}} < min{π_{e}, π_{d}} and π_{a}π_{e}π_{e+1}π_{d} is an occurrence of a pattern in A. We conclude that the permutations avoiding the patterns of A are the same as the permutations avoiding the patterns of B.

Armed with this theorem, we now need only show that (| Av_{n}(B)|)_{n≥1} satisfies the same recurrence as (a_{n})_{n≥1}. Our strategy will be as follows: given Av_{n−1}(B), define four maps which, when all of them are applied to all the permutations of Av_{n−1}(B), will generate all of the permutations of Av_{n}(B). Then we will count how many permutations of Av_{n}(B) are double-counted in this way, and find that there are two for every element of Av_{n−2}(B), thereby establishing the recurrence.

Note that, for a permutation to avoid all the patterns of A, it must be the case that either 1 and 2 occur consecutively (not necessarily in that order) or either 1 or 2 is the last element of the permutation. This observation motivates the following definitions of the four maps f_{before}, f_{after}, f_{end}, and f_{bump}. Let f_{before} be the function that inputs a permutation and outputs that permutation with all elements increased by 1 and a 1 inserted immediately before the new 2. Let f_{after} be the function that also inputs a permutation and outputs that permutation with all the elements increased by 1 and a 1 inserted immediately after the new 2. Similarly, let f_{end} be the function that inputs a permutation, increases all its elements by 1 and puts a 1 at the end of it, and let f_{bump} be the function that inputs a permutation, increases all its elements by 1, replaces the new 2 with a 1 and puts a 2 at the end. The following example gives a concrete illustration of the four functions.

Example 5. Let π = 31542. Then f_{before}(π) = 412653, f_{after}(π) = 421653, f_{end}(π) = 426531, and f_{bump}(π) = 416532. Note that π ∈ Av(B), and so are all its images.

Suppose n ≥ 2. The following two lemmas will together establish that

f_{before}(Av_{n−1}(B)) ∪ f_{after}(Av_{n−1}(B)) ∪ f_{end}(Av_{n−1}(B)) ∪ f_{bump}(Av_{n−1}(B)) = Av_{n}(B). (2)

Lemma 6. The functions f_{before}, f_{after}, f_{end}, and f_{bump} all map elements of Av_{n−1}(B) to elements of Av_{n}(B).

Proof. Choose some σ ∈ Av_{n−1}(B), and consider each function in turn. If f_{before}(σ) or f_{after}(σ) contains an occurrence τ of a pattern in B, then this occurrence must use the element 1 or else τ would already be an offending pattern in σ. But then replacing 1 by 2 would again give an offending pattern in σ. Thus, no such occurrence is possible in either f_{before}(σ) or f_{after}(σ). In addition, if f_{end}(σ) or f_{bump}(σ) contains an occurrence of a pattern in B, then this occurrence cannot use the last element because that element is either a 1 or a 2, and patterns in B only end with 3 or 4. So, this occurrence would already be an occurrence of the pattern in σ, and therefore cannot exist.

Lemma 7. Every permutation in Av_{n}(B) is the image of a permutation in Av_{n−1}(B) under at least one of the functions f_{before}, f_{after}, f_{end}, or f_{bump}.

Proof. Choose some π ∈ Av_{n}(B). As previously noted, either 1 and 2 occur consecutively in π, or else either 1 or 2 is the final element of π. Let π′ be π with the 1 removed and each element decreased by 1. We have introduced no new patterns, and so π′ ∈ Av_{n−1}(B). Suppose that 1 occurs immediately before 2 in π, then f_{before}(π′) = π. If the 1 occurs immediately after 2 in π, then f_{after}(π′) = π. If the 1 occurs at the end of π, then f_{end}(π′) = π. If the 2 occurs at the end of π, then we need to define π′′, which is π with the 1 removed, the 2 moved the position where the 1 used to be, and each element decreased by 1. Again, we have introduced no new patterns, and so π′′ ∈ Av_{n−1}(B), and f_{bump}(π′′) = π.

Now that we have established Equation 2, we can prove the main result.

Theorem 8. The sequence (| Av_{n}(B)|)_{n≥1} satisfies the same recurrence as (a_{n})_{n≥1}.

Proof. Since Av_{1}(B) = {1} and Av_{2}(B) = {12, 21}, the initial conditions hold. If the four functions f_{before}, f_{after}, f_{end}, and f_{bump} all had disjoint ranges, we could conclude from Equation 2 that | Av_{n}(B)| = 4 · | Av_{n−1}(B)|. Unfortunately, some permutations are counted in the range of multiple functions. Each f outputs a certain kind of permutation: f_{before} outputs permutations where 1 immediately precedes 2, f_{after} outputs permutations where 2 immediately precedes 1, f_{end} outputs permutations where 1 occurs at the end, and f_{bump} outputs permutations where 2 occurs at the end. A permutation in Av_{n}(B) that fulfills two of these criteria will be hit twice, hence double-counted. Such permutations must be hit once by either f_{before} or f_{after} and again by either f_{end} or f_{bump} because no permutation can be hit by both f_{before} and f_{after} or both f_{end} and f_{bump}. Thus, the final two elements of such permutations are 1 and 2 (not necessarily in that order). Let g : Av_{n}(B) → Av_{n−2}(B) be defined as the function that takes a permutation, removes from it the elements 1 and 2, and reduces all other elements by 2. If we restrict g to those permutations that end in either 12 or 21, g becomes a 2-to-1 map from the double-counted permutations of Av_{n}(B) to the permutations of Av_{n−2}(B), and so the number of double-counted permutations is twice | Av_{n−2}(B)|. It follows that | Av_{n}(B)| = 4 · | Av_{n−1}(B)| − 2 · | Av_{n−2}(B)| for n ≥ 3.

4 Acknowledgments

The author would like to thank his (intended) advisor Doron Zeilberger for introducing him to the conjecture and Matthew Russell for providing substantial revisions to this paper.

References

[1] E. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art B44b.

[2] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2017. Available

   at https://oeis.org.

2010 Mathematics Subject Classification: Primary 05A05. Keywords: permutation pattern, Wilf-equivalence.

(Concerned with sequence \underline{A006012}.)

Received July 29 2017; revised version received August 29 2017. Published in Journal of Integer Sequences, August 31 2017.

Return to Journal of Integer Sequences home page.