×

On the effective and automatic enumeration of polynomial permutation classes. (English) Zbl 1331.05016

Summary: We describe an algorithm, implemented in Python, which can enumerate any permutation class with polynomial enumeration from a structural description of the class. In particular, this allows us to find formulas for the number of permutations of length \(n\) which can be obtained by a finite number of block sorting operations (e.g., reversals, block transpositions, cut-and-paste moves).

MSC:

05A15 Exact enumeration problems, generating functions
05A05 Permutations, words, matrices

Software:

OEIS; Python; InsEnc
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albert, M. H.; Atkinson, M. D., Simple permutations and pattern restricted permutations, Discrete Math., 300, 1-3, 1-15 (2005) · Zbl 1073.05002
[2] Albert, M. H.; Atkinson, M. D.; Bouvel, M.; Ruškuc, N.; Vatter, V., Geometric grid classes of permutations, Trans. Am. Math. Soc., 365, 5859-5881 (2013) · Zbl 1271.05004
[3] Albert, M. H.; Atkinson, M. D.; Brignall, R., Permutation classes of polynomial growth, Ann. Comb., 11, 3-4, 249-264 (2007) · Zbl 1141.05009
[4] Albert, M. H.; Linton, S.; Ruškuc, N., The insertion encoding of permutations, Electron. J. Combin., 12, 1 (2005), Paper 47, 31 pp · Zbl 1081.05001
[5] Bafna, V.; Pevzner, P. A., Sorting by transpositions, SIAM J. Discrete Math., 11, 2, 224-240 (1998) · Zbl 0973.92014
[6] Balogh, J.; Bollobás, B.; Morris, R., Hereditary properties of ordered graphs, (Klazar, M.; Kratochvíl, J.; Loebl, M.; Matoušek, J.; Thomas, R.; Valtr, P., Topics in Discrete Mathematics. Topics in Discrete Mathematics, Algorithms Comb., vol. 26 (2006), Springer: Springer Berlin), 179-213 · Zbl 1117.05104
[7] Bassino, F.; Bouvel, M.; Pierrot, A.; Pivoteau, C.; Rossin, D., Combinatorial specification of permutation classes, (24th International Conference on Formal Power Series and Algebraic Combinatorics. 24th International Conference on Formal Power Series and Algebraic Combinatorics, PSAC 2012, Nancy. 24th International Conference on Formal Power Series and Algebraic Combinatorics. 24th International Conference on Formal Power Series and Algebraic Combinatorics, PSAC 2012, Nancy, Discrete Math. Theor. Comput. Sci. Proc., AR. Assoc. Discrete Math. Theor. Comput. Sci. (2012)), 781-792 · Zbl 1412.05003
[8] Bollobás, B., Hereditary and monotone properties of combinatorial structures, (Hilton, A.; Talbot, J., Surveys in Combinatorics 2007. Surveys in Combinatorics 2007, Lond. Math. Soc. Lect. Note Ser., vol. 346 (2007), Cambridge University Press), 1-39 · Zbl 1129.05020
[9] Brignall, R.; Huczynska, S.; Vatter, V., Simple permutations and algebraic generating functions, J. Comb. Theory, Ser. A, 115, 3, 423-441 (2008) · Zbl 1139.05002
[10] Christie, D. A., Sorting permutations by block-interchanges, Inf. Process. Lett., 60, 4, 165-169 (1996) · Zbl 0900.68232
[11] Cranston, D. W.; Sudborough, I. H.; West, D. B., Short proofs for cut-and-paste sorting of permutations, Discrete Math., 307, 22, 2866-2870 (2007) · Zbl 1128.05001
[12] Dias, Z.; Meidanis, J., Sorting by prefix transpositions, (Proceedings of the 9th International Symposium on String Processing and Information Retrieval. Proceedings of the 9th International Symposium on String Processing and Information Retrieval, London, UK, UK, 2002, SPIRE (2002), Springer-Verlag), 65-76
[13] Dweighter, H., Elementary problems and solutions, problem E2569, Am. Math. Mon., 82, 1010 (1975)
[14] Fertin, G.; Labarre, A.; Rusu, I.; Tannier, É.; Vialette, S., Combinatorics of Genome Rearrangements, Comput. Mol. Biol. (2009), MIT Press: MIT Press Cambridge, MA · Zbl 1170.92022
[15] Higman, G., Ordering by divisibility in abstract algebras, Proc. Lond. Math. Soc. (3), 2, 326-336 (1952) · Zbl 0047.03402
[16] Huczynska, S.; Vatter, V., Grid classes and the Fibonacci dichotomy for restricted permutations, Electron. J. Combin., 13 (2006), R54, 14 pp · Zbl 1098.05003
[17] Kaiser, T.; Klazar, M., On growth rates of closed permutation classes, Electron. J. Comb., 9, 2 (2003), Paper 10, 20 pp · Zbl 1015.05002
[18] Klazar, M., Overview of some general results in combinatorial enumeration, (Linton, S.; Ruškuc, N.; Vatter, V., Permutation Patterns. Permutation Patterns, Lond. Math. Soc. Lect. Note Ser., vol. 376 (2010), Cambridge University Press), 3-40 · Zbl 1217.05026
[20] Vatter, V., Finding regular insertion encodings for permutation classes, J. Symb. Comput., 47, 259-265 (2012) · Zbl 1237.05014
[21] Vatter, V., Permutation classes, (Bóna, M., Handbook of Enumerative Combinatorics (2015), CRC Press), 754-833 · Zbl 1353.05010
[22] Watterson, G. A.; Ewens, W. J.; Hall, T. E.; Morgan, A., The chromosome inversion problem, J. Theor. Biol., 99, 1-7 (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.