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
Download 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.

Related papers

Cite this paper

APA

Callan, D., & Mansour, T. (2018). Enumeration of 3- and 4-Wilf classes of four 4-letter patterns. Notes on Number Theory and Discrete Mathematics, 24(3), 115-130, doi: 10.7546/nntdm.2018.24.3.115-130.

Chicago

Callan, David, and Toufik Mansour. “Enumeration of 3- and 4-Wilf Classes of Four 4-letter Patterns.” Notes on Number Theory and Discrete Mathematics 24, no. 3 (2018): 115-130, doi: 10.7546/nntdm.2018.24.3.115-130.

MLA

Callan, David, and Toufik Mansour. “Enumeration of 3- and 4-Wilf Classes of Four 4-letter Patterns.” Notes on Number Theory and Discrete Mathematics 24.3 (2018): 115-130. Print, doi: 10.7546/nntdm.2018.24.3.115-130.

Comments are closed.