Enumeration of 3- and 4-Wilf classes of four 4-letter patterns

David Callan and Toufik Mansour
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 24, 2018, Number 3, Pages 115–130
DOI: 10.7546/nntdm.2018.24.3.115-130
Full paper (PDF, 220 Kb)

Details

Authors and affiliations

David Callan
Department of Statistics, University of Wisconsin
Madison, WI 53706, United States

Toufik Mansour
Department of Mathematics, University of Haifa
3498838 Haifa, Israel

Abstract

Let 𝑆_𝑛 be the symmetric group of all permutations of 𝑛 letters. We show that there are precisely 27 (respectively, 15) Wilf classes consisting of exactly 3 (respectively, 4) symmetry classes of subsets of four 4-letter patterns.

Keywords

• Pattern avoidance
• Wilf-equivalence

2010 Mathematics Subject Classification

• 05A15
• 05A05

References

1. Arıkan, T., Kılıç, E., &Mansour, T. (2017) AWilf class composed of 19 symmetry classes of quadruples of 4-letter patterns. Notes on Number Theory and Discrete Mathematics, 23(3), 79–99.
2. Callan, D. & Mansour, T. (2017) Enumeration of 2-Wilf classes of four 4-letter patterns, Turkish Journal of Analysis and Number Theory, 5(6), 210–225.
3. Knuth, D. E. (1997) The Art of Computer Programming, 3rd edition, AddisonWesley, Reading, MA.
4. Mansour, T. & Schork, M. (2018) Permutation patterns and cell decompositions, Mathematics in Computer Science, to appear, https://doi.org/10.1007/s11786-018-0353-5.
5. Mansour, T. & Vainshtein, A. (2001) Restricted 132-avoiding permutations, Advances in Applied Mathematics, 26, 258–269.
6. Simion, R. & Schmidt, F. W. (1985) Restricted permutations, European Journal of Combinatorics, 6, 383–406.
7. Vatter, V. (2012) Finding regular insertion encodings for permutation classes, Journal of Symbolic Computation, 47(3), 259–265.