Turkish Journal of Analysis and Number Theory
ISSN (Print): 2333-1100 ISSN (Online): 2333-1232 Website: http://www.sciepub.com/journal/tjant
Open Access
Journal Browser
Go
Turkish Journal of Analysis and Number Theory. 2017, 5(6), 210-225
DOI: 10.12691/tjant-5-6-3
Open AccessArticle

Enumeration of 2-Wilf Classes of Four 4-letter Patterns

David Callan1 and Toufik Mansour2,

1Department of Statistics, University of Wisconsin, Madison, WI

2Department of Mathematics, University of Haifa, Haifa, Israel

Pub. Date: November 03, 2017

Cite this paper:
David Callan and Toufik Mansour. Enumeration of 2-Wilf Classes of Four 4-letter Patterns. Turkish Journal of Analysis and Number Theory. 2017; 5(6):210-225. doi: 10.12691/tjant-5-6-3

Abstract

Let Sn 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.

Keywords:
pattern avoidance Wilf-equivalence

Creative CommonsThis work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]  T. Arıkan, E. Kılı¸c and T. Mansour, A Wilf class composed of 19 symmetry classes of quadruples of 4-letter patterns, Notes on Number Theory and Discrete Mathematics. 23:3 (2017), 79-99.
 
[2]  D. Callan, T. Mansour and M. Shattuck, Wilf classification of triples of 4-letter patterns I, Discr. Math. Theor. Comput. Sci. 19 (2017) #5, 35pp.
 
[3]  D. Callan, T. Mansour and M. Shattuck, Wilf classification of triples of 4-letter patterns II, Discr. Math. Theor. Comput. Sci. 19 (2017) #6, 44pp.
 
[4]  D. E. Knuth, The Art of Computer Programming, 3rd edition, Addison Wesley, Reading, MA, 1997.
 
[5]  W. Kuszmaul, Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations, Preprint, arXiv:1509.08216, 2015.
 
[6]  I. Le, Wilf classes of pairs of permutations of length 4, Electron. J. Combin. 12 (2005), #R25.
 
[7]  T. Mansour and M. Schork, Wilf classification of subsets of four letter patterns, J. Combin. Number Theory 8 (2016), 1-129.
 
[8]  T. Mansour and M. Schork, Wilf classification of subsets of eight and nine four-letter patterns, J. Combin. Number Theory 8 (2016), 257-283.
 
[9]  T. Mansour and M. Schork, Wilf classification of subsets of six and seven four-letter patterns, preprint.
 
[10]  T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. in Appl. Math. 26 (2001), 258-269.
 
[11]  R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383-406.
 
[12]  V. Vatter, Finding regular insertion encodings for permutation classes, J. Symbolic Comput. 47:3 (2012), 259-265.