Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns

Callan, David; Mansour, Toufik

doi:10.1515/puma-2015-0026

Abstract

Recently, it has been determined that there are 242 Wilf classes of triples of 4-letter permutation patterns by showing that there are 32 non-singleton Wilf classes. Moreover, the generating function for each triple lying in a non-singleton Wilf class has been explicitly determined. In this paper, toward the goal of enumerating avoiders for the singleton Wilf classes, we obtain the generating function for all but one of the triples containing 1324. (The exceptional triple is conjectured to be intractable.) Our methods are both combinatorial and analytic, including generating trees, recurrence relations, and decompositions by left-right maxima. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence amenable to the kernel method.

References

[1] Enumerations of specific permutation classes, Published electronically at https://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes.
Search in Google Scholar Back to article
[2] M. H. Albert, C. Homberger, J. Pantone, N. Shar and V. Vatter, Generating permutations with restricted containers, preprint, at https://arxiv.org/abs/1510.00269, 2015.
Search in Google Scholar Back to article
[3] M. H. Albert, S. Linton and N. Ruskuc, The insertion encoding of permutations, Electron. J. Combin., 12 (2005) #R47.10.37236/1944
Search in Google Scholar Back to article
[4] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Math., 246 (2002) 29–55.10.1016/S0012-365X(01)00250-3
Search in Google Scholar Back to article
[5] D. Callan, T. Mansour and M. Shattuck, Wilf classification of triples of 4-letter patterns, preprint, at http://arxiv.org/abs/1605.04969, 2016.
Search in Google Scholar Back to article
[6] D. Callan and Mansour, Five subsets of permutations enumerated as weak sorting permutations, Southeast Asian Bull. Math., to appear.
Search in Google Scholar Back to article
[7] D. Callan and Mansour, A Wilf class composed of 7 symmetry classes of triples of 4-letter patterns, Journal of Analysis & Number Theory, 5 (2017) 19–26.10.18576/jant/050104
Search in Google Scholar Back to article
[8] D. Callan and Mansour, On permutations avoiding 1243, 2134, and another 4-letter pattern, Pure Math. Appl. (PU.M.A.), 26 (2017) 11–21.10.1515/puma-2015-0019
Search in Google Scholar Back to article
[9] D. Callan and Mansour, On permutations avoiding 1324, 2143, and another 4-letter pattern, Pure Math. Appl. (PU.M.A.), 26 (2017) 1–10.10.1515/puma-2015-0018
Search in Google Scholar Back to article
[10] D. Callan and Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, at http://arxiv.org/abs/1705.00933, 2017.10.1515/puma-2015-0026
Search in Google Scholar Back to article
[11] D. Callan, T. Mansour and M. Shattuck, Twelve subsets of permutations enumerated as maximally clustered permutations, Ann. Math. Inform., 47 (2017) 41–74.
Search in Google Scholar Back to article
[12] D. Callan, T. Mansour and M. Shattuck, Wilf classification of triples of 4-letter patterns I, Discrete Math. Theoret. Comput. Sci., 19:1 (2017) #5, 35 pp.10.18576/jant/050104
Search in Google Scholar Back to article
[13] D. Callan, T. Mansour and M. Shattuck, Wilf classification of triples of 4-letter patterns II, Discrete Math. Theoret. Comput. Sci., 19:1 (2017) #6, 44 pp.10.18576/jant/050104
Search in Google Scholar Back to article
[14] G. Firro and T. Mansour, Three-letter-pattern avoiding permutations and functional equations, Electron J. Combin., 13 (2006) #R51.10.37236/1077
Search in Google Scholar Back to article
[15] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, CRC Press, Boca Raton, FL, 2009.10.1201/9781420072686
Search in Google Scholar Back to article
[16] Q. Hou and T. Mansour, Kernel method and linear recurrence system, J. Comput. Appl. Math., 261 (2008) 227–242.10.1016/j.cam.2007.05.001
Search in Google Scholar Back to article
[17] D. E. Knuth, The Art of Computer Programming, 3rd edition, Addison Wesley, Reading, MA, 1997.
Search in Google Scholar Back to article
[18] D. Kremer and W. C. Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math., 268 (2003) 171–183.10.1016/S0012-365X(03)00042-6
Search in Google Scholar Back to article
[19] W. Kuszmaul, Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations, preprint, at https://arxiv.org/abs/1509.08216, 2015.
Search in Google Scholar Back to article
[20] I. Le, Wilf classes of pairs of permutations of length 4, Electron. J. Combin., 12 (2005) #R25.10.37236/1922
Search in Google Scholar Back to article
[21] P. A. MacMahon, Combinatory Analysis, Volumes 1 and 2, Cambridge University Press, 1915-16.
Search in Google Scholar Back to article
[22] T. Mansour, Combinatorics of Set Partitions, CRC Press, Boca Raton, FL, 2012.10.1201/b12691
Search in Google Scholar Back to article
[23] T. Mansour and M. Shattuck, Nine classes of permutations enumerated by binomial transform of Fine’s sequence, Discrete Appl. Math., 226 (2017) 94–105.10.1016/j.dam.2017.04.015
Search in Google Scholar Back to article
[24] T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. in Appl. Math., 26 (2001) 258–269.10.1006/aama.2000.0719
Search in Google Scholar Back to article
[25] R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6 (1985) 383–406.10.1016/S0195-6698(85)80052-4
Search in Google Scholar Back to article
[26] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org/.
Search in Google Scholar Back to article
[27] Z. E. Stankova, Forbidden subsequences, Discrete Math., 132 (1994) 291–316.10.1016/0012-365X(94)90242-9
Search in Google Scholar Back to article
[28] Z. Stankova, Classification of forbidden subsequences of length four, European J. Combin., 17 (1996) 501–517.10.1006/eujc.1996.0044
Search in Google Scholar Back to article
[29] V. Vatter, Finding regular insertion encodings for permutation classes, J. Symbolic Comput., 47 (2012) 259–265.10.1016/j.jsc.2011.11.002
Search in Google Scholar Back to article
[30] J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math., 146 (1995) 247–262.10.1016/0012-365X(94)00067-1
Search in Google Scholar Back to article

Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns

Abstract

Paradigm

My account