Published on

15-Dec-2016View

212Download

0

Transcript

<ul><li><p>Discrete Mathematics 313 (2013) 26142625</p><p>Contents lists available at ScienceDirect</p><p>Discrete Mathematics</p><p>journal homepage: www.elsevier.com/locate/disc</p><p>Partial permutations avoiding pairs of patternsNoah ArbesfeldDepartment of Mathematics, Columbia University, New York, NY 10027, United States</p><p>a r t i c l e i n f o</p><p>Article history:Received 1 January 2013Received in revised form 1 August 2013Accepted 2 August 2013Available online 25 August 2013</p><p>Keywords:Pattern avoidancePartial permutationsWilf-equivalence</p><p>a b s t r a c t</p><p>We continue the study of pattern avoidance in partial permutations initiated by Claesson,Jelnek, Jelnkova, and Kitaev. We extend previous definitions of shape-Wilf-equivalenceand -Wilf-equivalence to sets of patterns, and determine new shape-Wilf-equivalencesand shape--Wilf-equivalences between pairs of patterns of length 3. Using these results,we find infinite families of Wilf-equivalences and -Wilf-equivalences between pairs ofpatterns. We also classify pairs of patterns of length up to 4 up to -Wilf-equivalence.</p><p> 2013 Elsevier B.V. All rights reserved.</p><p>1. Introduction</p><p>We continue the study of pattern avoidance in partial permutations initiated by Claesson, Jelnek, Jelnkova, and Kitaevin [6]. We begin by recalling concepts from classical pattern avoidance. A permutation p of length n is an ordered list p1 pnof {1, . . . , n} in which each element appears exactly once. Let Sn denote the set of permutations of length n. Given twopermutations p = p1 pn and q = q1 qm, the permutation p contains q if there exist indices 1 i1 < < im n suchthat pij < pij if and only if qj < qj for all j, j</p><p>; in such a case the substring pi1 pim is an occurrence of q. In this setting, qis called a pattern. If p does not contain q, the permutation p avoids the pattern q. If a permutation p avoids each pattern ina set A of patterns then p avoids the set A. Let Sn(A) denote the set of permutations in Sn avoiding A; two sets of patterns Aand B areWilf-equivalent if |Sn(A)| = |Sn(B)| for all n.</p><p>A central goal of the study of pattern avoidance is to classify sets of patterns up to Wilf-equivalence. For singleton setsof patterns, the following results are known. First, a pattern p = p1 pn is trivially Wilf-equivalent to its reversal pn p1,its complement (n + 1 p1) (n + 1 pn), and its inverse q1 qn, where qi satisfies pqi = i. Beyond these trivial Wilf-equivalences, Backelin, West, and Xin prove in [2] that the patterns 1 n x and n 1 x are Wilf-equivalent for anyx, and Stankova and West prove in [14] that the patterns 231 x and 312 x are Wilf-equivalent for any x, where, for twopermutations p and qwith |p| = m and |q| = n, the direct sum pq is the permutation p1 pm(q1+m) (qn+m). Thesefamilies ofWilf-equivalences were proven by showing that the patterns in question satisfy a stronger equivalence conditioncalled shape-Wilf-equivalence, a condition on the number of fillings of Ferrers diagrams that avoid permutation matrices.The only other knownWilf-equivalence is between 2314 and 2413, shown by Stankova in [13].</p><p>In [6], the study of pattern avoidance is expanded to the setting of partial permutations. We recall the necessarydefinitions from that paper. Introduce a symbol , called a hole. Then, a partial permutation of {1, . . . , n} is an orderedlist 1 m of elements of {1, . . . , n,} in which each of {1, . . . , n} appears exactly once. Then Skn is the set of partialpermutations of {1, . . . , n k}with exactly k holes; for example S13 = {12, 1 2, 21, 2 1,12,21}. Let = 1 nbe a partial permutation in Skn whose nonhole elements arei1 , . . . , ink with i1 < < ink; then, a standard permutationp Sn is an extension of the partial permutation 1 n if the following statement holds: ij < ij if and only if pij < pijfor all j, j. For example, the extensions of 1 32 are 2143, 1243, 1342, and 1432.</p><p>E-mail address: nma2141@columbia.edu.</p><p>0012-365X/$ see front matter 2013 Elsevier B.V. All rights reserved.http://dx.doi.org/10.1016/j.disc.2013.08.004</p></li><li><p>N. Arbesfeld / Discrete Mathematics 313 (2013) 26142625 2615</p><p>Then, a partial permutation avoids a pattern p if each extension of avoids p, and a partial permutation avoids a setA of patterns if avoids each element of A. In this sense, a partial permutation can be thought of as encoding the set of itsextensions. We let Skn(A) denote the set of all partial permutations in S</p><p>kn that avoid A, and let s</p><p>kn(A) = |Skn(A)|. When writing</p><p>an expression of the form Skn(A)we omit the brackets around the set A.This notion of pattern avoidance for partial permutations enables us to extend the notion of Wilf-equivalence to the</p><p>setting of partial permutations. Two sets A and B of patterns are k-Wilf-equivalent if skn(A) = skn(B) for all n, and A and Bare -Wilf-equivalent if they are k-Wilf-equivalent for k 0. In particular, 0-Wilf-equivalence is the same as the standardnotion of Wilf-equivalence.</p><p>In [6], the authors find that results from pattern avoidance have analogues which hold in the setting of partialpermutations. They find -Wilf-equivalences between patterns by proving that the patterns in question satisfy a conditioncalled shape--Wilf-equivalence, an extension of shape-Wilf-equivalence that imposes a condition on the number ofso-called partial fillings of diagrams that avoid permutation matrices. Namely, the authors show that the shape-Wilf-equivalence between 1 n x and n 1 x and the shape-Wilf-equivalence between 231 x with 312 x extend toshape--Wilf-equivalences. So, all known Wilf-equivalences extend to -Wilf-equivalences with the following exceptions:a pattern is not necessary -Wilf-equivalent to its inverse, and the patterns 2314 and 2413 are not -Wilf-equivalent. Weremark that the condition shape-Wilf-equivalencewas recently extended in [3] to the setting of vincular patterns, a differentgeneralization of pattern avoidance.</p><p>In the present work, we find -Wilf-equivalences between pairs of patterns, with a focus on determining which resultsfrom Wilf-equivalence can be extended to -Wilf-equivalences. A set of patterns is trivially -Wilf-equivalent to the setsformed by taking the complements and reversals of the sets patterns; we seek nontrivial -Wilf-equivalences.</p><p>In Section 2, we recall the definition of shape-Wilf-equivalence, and find shape-Wilf-equivalences among pairs ofpatterns of length 3. Namely, we prove the following.</p><p>Theorem 1.1. The following seven pairs of patterns of length 3 are shape-Wilf-equivalent:</p><p>{123, 213}, {132, 231}, {132, 312}, {213, 231}, {213, 312}, {231, 321} and {312, 321}.We remark that a complete classification of pairs of patterns of length 3 up to shape-Wilf-equivalence was obtainedindependently by Bloom and Elizalde in [4]. The authors also enumerate matchings and set partitions that avoid pairs ofpatterns of length 3 for most such pairs of patterns.</p><p>In Section 3, we extend the definition of shape--Wilf-equivalence from [6] to include pairs of patterns and generalize aresult from [6, Section 3] to sets of patterns, enabling us to find infinite families ofWilf-equivalences and -Wilf-equivalencesbetween pairs of patterns.</p><p>In Section 4, we classify pairs of patterns of length 3 up to shape--Wilf-equivalence. Namely, we prove the following.</p><p>Theorem 1.2. The shape--Wilf-equivalences among pairs of patterns of length 3 are as follows: {123, 213} and {231, 321}, {132, 231} and {213, 312}, {132, 312} and {213, 231}.By Proposition 3.1, we deduce the following corollary.</p><p>Corollary 1.3. Given a set {pi} of patterns, the following sets of patterns are -Wilf-equivalent: {132 pi, 231 pi} and {213 pi, 312 pi}, {132 pi, 312 pi} and {213 pi, 231 pi}, {123 pi, 213 pi} and {231 pi, 321 pi}.Whereas all known shape-Wilf-equivalent (single) patterns are shown in [6] to be shape--Wilf-equivalent, we deduce</p><p>as a consequence of Theorems 1.1 and 1.2 that there exist shape-Wilf-equivalent sets of patterns that are not shape--Wilf-equivalent.</p><p>In Section 5, we determine the -Wilf-equivalence classes among pairs of short patterns A = {p, q} for p and q of lengthat most 4. When p or q has length 2 the classification is straightforward.</p><p>The classification of pairs of patterns {p, q} with |p| = |q| = 3 up to Wilf-equivalence is stated in [11]. Up to trivial-Wilf-equivalence, there are six such pairs, distributed across three 0-Wilf-equivalence classes. Among these six pairs,there is only one nontrivial -Wilf-equivalence. Namely, we have the following.</p><p>Theorem 1.4. Among pairs of patterns {p, q} with |p| = |q| = 3, the only nontrivial -Wilf-equivalence is {123, 132} and {132, 231}.The classification up to Wilf-equivalence of pairs of patterns {p, q} with |p| = 3, |q| = 4, and p not contained in q, is</p><p>listed in [1,16]. Up to trivial -Wilf-equivalence, there are 24 such pairs (note that some inverses to the pairs listed in [1,16]must also be considered).</p></li><li><p>2616 N. Arbesfeld / Discrete Mathematics 313 (2013) 26142625</p><p>Theorem 1.5. Among pairs of patterns {p, q} with |p| = 3 and |q| = 4 with p not contained in q, the nontrivial -Wilf-equivalences are</p><p> {321, 1342} and {321, 1423}, {321, 2341}, {132, 1234}, {132, 3241}, {132, 3124}, {132, 2134}, and {132, 3412}, {321, 3412}, {321, 3142}, {321, 2413}, {132, 2341}, and {132, 2314}.The classification of pairs of patterns of length 4 up to Wilf-equivalence is completed in [10], building on work done</p><p>in [5,79,13,15]. In the present work we find that most nontrivially Wilf-equivalent pairs of patterns of length 4 are not-Wilf-equivalent. Namely, the following theorem gives the only nontrivial -Wilf-equivalences.</p><p>Theorem 1.6. Among pairs of patterns {p, q} with |p| = |q| = 4, the nontrivial -Wilf-equivalence classes are {4123, 3214} and {1234, 2143}, {1324, 2314} and {2134, 3124}, {1324, 3124}, {2413, 4213}, and {2134, 2314}, {1234, 2134}, {1342, 2341}, {2314, 3214}, and {1243, 2143}.We conclude the introduction by mentioning that the present work emerged from an investigation into the questions</p><p>posed at the end of [6]. Based on computations, we provide the following conjectures. The first is an analogue of theStanleyWilf theorem in the setting of partial permutations.</p><p>Conjecture 1.7. If p is a pattern then limn ns1n(p) exists and is finite.</p><p>In particular, [6, Theorem8.1] reduces this conjecture to the statement that s1m(p)s1n(p) s1m+n(p) for allm and n. Preliminary</p><p>computations suggest that limn nskn(p) exists and is finite for all patterns p and all integers k.</p><p>We also state the following conjecture.</p><p>Conjecture 1.8. The patterns k-Wilf-equivalent to the permutation 12 (k+ 3) are exactly the layered permutations in Sk+3.It would also be interesting to investigate which permutations are -Wilf-equivalent to their inverses, as this is the one ofthe few cases in which Wilf-equivalent permutations are not -Wilf-equivalent.</p><p>2. Shape-Wilf-equivalences for pairs of patterns of length 3</p><p>We begin by recalling the definition of shape-Wilf-equivalence.Let D = (1, . . . , n)with 1 n 1 denote a bottom-left justified array of boxes, with i boxes in the i-th row</p><p>from the bottom. Such an array D is a Ferrers diagram. We number the rows of D from bottom to top and the columns fromleft to right (the so-called French notation). We allow the possibility that D is an empty list, in which case D is the emptyFerrers diagram. Note that our definition of a Ferrers diagram differs from that given in [6] as we exclude the possibility ofcolumns of zero height; the inclusion of such diagrams does not require significant modification of our proofs.</p><p>A transversal of D is a filling of each cell of D with either a 0 or a 1 such that each row and column of D contains exactlyone 1. By convention, we say that the empty diagram has exactly one transversal. A Ferrers diagram D = (1, . . . , n) isfillable if 1 = n and i > n i for i = 1, . . . , n or if D is empty; in other words, a Ferrers diagram is fillable if and only if ithas a transversal.</p><p>Wenow recall the notion of pattern avoidance for transversals of diagrams. The permutationmatrix associated to a patternp = p1 pn is the transversal of the square diagram (n, . . . , n)with a 1 in the ith column from the left and pi-th row fromthe bottom for i = 1, . . . , n; when there is no confusion we also let p denote the permutation matrix of the pattern p. Atransversal F of Ferrers diagram D contains a pattern p if there is an n by n submatrix of F that is equal to the permutationmatrix p; i.e., if one may choose i1 < i2 < < in and j1 < j2 < < jn such that for all 1 l, k n there is a cell inthe il-th row and jk-th column of F , and the entry found in this cell is the same as the entry found in the l-th row and k-thcolumn of the matrix p. A transversal F avoids p if it does not contain p, and avoids a set A if it avoids each element of A.</p><p>Given a Ferrers diagram D and a set A of patterns, let SD(A) denote the set of transversals of D that avoid each element ofA and let sD(A) = |SD(A)|. Two sets of patterns A and B are shape-Wilf-equivalent if sD(A) = sD(B) for any diagram D. Notethat two sets A and B are Wilf-equivalent if sD(A) = sD(B) for all square diagrams D; in particular, shape-Wilf-equivalenceis a stronger condition than Wilf-equivalence.</p><p>Up to the present work, the following shape-Wilf-equivalences between patterns are known: in [2] it is shown that12 n p and n 21 p are shape-Wilf-equivalent for any pattern p, and in [14] it is shown that 312 p and 231 pare shape-Wilf-equivalent for any pattern p.</p><p>We now prove Theorem 1.1. First, given a fillable Ferrers diagram D = (1, . . . , n), set e(D) to be the number of indicesi for which i > n + 1 i. As D is fillable, we know that 0 e(D) < n. In other words, e(D) is the number of rows of Dwhose length exceeds the length of the corresponding row of the so-called staircase Ferrers diagram, (n, n 1, . . . , 1). Forexample, e((4, 4, 3, 1)) = 2.</p></li><li><p>N. Arbesfeld / Discrete Mathematics 313 (2013) 26142625 2617</p><p>Fig. 1. A Ferrers diagram D with n = 7 and 4 = 4. The top and right parts (in the language of Case 1) are labelled. The remaining boxes comprise thebottom part.</p><p>Proposition 2.1. Let D be a fillable Ferrers diagram with e(D) 0. Then,sD(123, 213) = sD(132, 231) = sD(132, 312) = sD(231, 321) = sD(312, 321) = 2e(D).</p><p>Proof. Our argument is similar to that deduced independently in [4]. Let D = (1, . . . , n) be a nonempty fillable Ferrersdiagram. For each pair A listed in the theorem, we use strong induction on the number of rows n of D to count sD(A). Thebase case n = 1 is clear. So suppose n > 1. We first compute sD(132, 231). Consider filling in D starting from the top rowto obtain a {132, 231}-avoiding transversal. If n = 1, then there is only one choice for the 1 in the uppermost row. Then,if D denotes the Ferrers diagram obtained by removing the column and row containing this 1, by induction there are 2e(D)ways of filling in the remainder of D to obtain a transversal that avoids {132, 231}. As n = 1, one has e(D) =...</p></li></ul>