Enumeration of permutations avoiding a triple of 4-letter patterns is almost all done

Callan, David; Mansour, Toufik; Shattuck, Mark

doi:10.1515/puma-2015-0031

Abstract

This paper basically completes a project to enumerate permutations avoiding a triple T of 4-letter patterns, in the sense of classical pattern avoidance, for every T. There are 317 symmetry classes of such triples T and previous papers have enumerated avoiders for all but 14 of them. One of these 14 is conjectured not to have an algebraic generating function. Here, we find the generating function for each of the remaining 13, and it is algebraic in each case.

References

[1] M. H. Albert, C. Homberger, J. Pantone, N. Shar and V. Vatter, Generating permutations with restricted containers, at http://arxiv.org/abs/1510.00269.
Search in Google Scholar Back to article
[2] 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
[3] D. Callan and T. 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
[4] D. Callan and T. 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
[5] D. Callan and T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, Pure Math. Appl. (PU.M.A.), 27(1) (2018) 32–61.10.1515/puma-2015-0026
Search in Google Scholar Back to article
[6] D. Callan and T. Mansour, Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns, Pure Math. Appl. (PU.M.A.), 27(1) (2018) 62–97.10.1515/puma-2015-0027
Search in Google Scholar Back to article
[7] D. Callan, T. Mansour and M. Shattuck, Wilf classification of triples of 4-letter patterns I, Discrete Math. Theor. Comput. Sci., 19 (2017) #5.10.18576/jant/050104
Search in Google Scholar Back to article
[8] D. Callan, T. Mansour and M. Shattuck, Wilf classification of triples of 4-letter patterns II, Discrete Math. Theor. Comput. Sci., 19 (2017) #6.10.18576/jant/050104
Search in Google Scholar Back to article
[9] D. Callan, T. Mansour and M.Shattuck, Wilf classification of triples of 4-letter patterns, at http://arxiv.org/abs/1605.04969.
Search in Google Scholar Back to article
[10] 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
[11] 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
[12] D. E. Knuth, The Art of Computer Programming, 3rd edition, Addison Wesley, Reading, MA, 1997.
Search in Google Scholar Back to article
[13] 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
[14] 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
[15] T. Mansour and M. Schork, Wilf classification of subsets of four letter patterns, J. Comb. Number Theory, 8 (2016) 1–129.
Search in Google Scholar Back to article
[16] T. Mansour and M. Schork, Wilf classification of subsets of eight and nine four-letter patterns, J. Comb. Number Theory, 8 (2016) 257–283.
Search in Google Scholar Back to article
[17] 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
[18] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, at http://oeis.org.
Search in Google Scholar Back to article
[19] Z. Stankova, Forbidden subsequences, Discrete Math., 132 (1994) 291–316.10.1016/0012-365X(94)90242-9
Search in Google Scholar Back to article
[20] 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
[21] 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
[22] 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
[23] Wikipedia, Permutation pattern, at https://en.wikipedia.org/wiki/Permutation_pattern
Search in Google Scholar Back to article
[24] Wikipedia, Enumerations of specific permutation classes, available at https://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes
Search in Google Scholar Back to article

Enumeration of permutations avoiding a triple of 4-letter patterns is almost all done

Abstract

Paradigm

My account