Simple permutations and algebraic generating functions. (English) Zbl 1139.05002
This paper deals with simple permutations, that is with permutations that never map a nontrivial contiguous set of indices contiguously. For an arbitrary set of permutations that is closed under taking subpermutations and contains only finitely many simple permutations, there is given a framework for enumerating subsets that are restricted by properties belonging to a finite “query-complete set”. Such properties include being even, being an alternating permutation and avoiding a given generalized (blocked or barred) pattern. The authors prove that the generating functions of these subsets are always algebraic, generalizing some recent results of Albert and Atkinson. These techniques are also applied to enumerate the involutions and cyclic closures.
Reviewer: Marius Tarnauceanu (Iaşi)
Keywords:
algebraic generating function; modular decomposition; permutation class; restricted permutation; simple permutation; substitution decompositionSoftware:
AARONOnline Encyclopedia of Integer Sequences:
Large Schröder numbers (or large Schroeder numbers, or big Schroeder numbers).Binomial transform of Fine’s sequence A000957: 1, 0, 1, 2, 6, 18, 57, 186, ...
Number of simple permutations of degree n.
Number of permutations avoiding 3142, 25314, 246135 and 362514.
Number of alternating separable permutations.
Number of separable involutions.
Number of permutations that lie in the cyclic closure of Av(132)–i.e., at least one cyclic rotation of the permutation avoids the pattern 132.
References:
| [1] | Möhring, R. H., Algorithmic aspects of the substitution decomposition in optimization over relations, sets systems and Boolean functions, Ann. Oper. Res., 4, 1-4, 195-225 (1985) |
| [2] | Möhring, R. H.; Radermacher, F. J., Substitution decomposition for discrete structures and connections with combinatorial optimization, (Algebraic and Combinatorial Methods in Operations Research. Algebraic and Combinatorial Methods in Operations Research, North-Holland Math. Stud., vol. 95 (1984), North-Holland: North-Holland Amsterdam), 257-355 · Zbl 0567.90073 |
| [3] | Albert, M. H.; Atkinson, M. D., Simple permutations and pattern restricted permutations, Discrete Math., 300, 1-3, 1-15 (2005), URL · Zbl 1073.05002 |
| [4] | Mansour, T., Restricted even permutations and Chebyshev polynomials, Discrete Math., 306, 12, 1161-1176 (2006), URL · Zbl 1093.05002 |
| [5] | Egge, E. S., Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials, Adv. in Appl. Math., 33, 3, 451-475 (2004), URL · Zbl 1059.05004 |
| [6] | Egge, E. S.; Mansour, T., 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers, Discrete Appl. Math., 143, 1-3, 72-83 (2004), URL · Zbl 1053.05007 |
| [7] | Egge, E. S.; Mansour, T., 231-avoiding involutions and Fibonacci numbers, Australas. J. Combin., 30, 75-84 (2004) · Zbl 1054.05006 |
| [8] | Elizalde, S.; Mansour, T., Restricted Motzkin permutations, Motzkin paths, continued fractions and Chebyshev polynomials, Discrete Math., 305, 1-3, 170-189 (2005), URL · Zbl 1078.05002 |
| [9] | Guibert, O.; Mansour, T., Restricted 132-involutions, Sém. Lothar. Combin., 48 (2002), Article B48a, 23 pp., URL · Zbl 1017.05009 |
| [10] | Guibert, O.; Mansour, T., Some statistics on restricted 132 involutions, Ann. Comb., 6, 3-4, 349-374 (2002), URL · Zbl 1017.05009 |
| [11] | Mansour, T., Restricted 1-3-2 permutations and generalized patterns, Ann. Comb., 6, 1, 65-76 (2002), URL · Zbl 1009.05002 |
| [12] | Mansour, T., Restricted 132-alternating permutations and Chebyshev polynomials, Ann. Comb., 7, 2, 201-227 (2003), URL · Zbl 1020.05002 |
| [13] | Mansour, T., Restricted 132-Dumont permutations, Australas. J. Combin., 29, 103-117 (2004) · Zbl 1050.05007 |
| [14] | Mansour, T.; Vainshtein, A., Restricted 132-avoiding permutations, Adv. in Appl. Math., 26, 3, 258-269 (2001), URL · Zbl 0982.05002 |
| [15] | West, J., Sorting twice through a stack, Theoret. Comput. Sci., 117, 1-2, 303-313 (1993) · Zbl 0797.68041 |
| [16] | Bousquet-Mélou, M.; Butler, S., Forest-like permutations, URL · Zbl 1141.05011 |
| [17] | Babson, E.; Steingrímsson, E., Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin., 44 (2000), Article B44b, 18 pp., URL · Zbl 0957.05010 |
| [18] | Dumont, D., Interprétations combinatoires des nombres de Genocchi, Duke Math. J., 41, 305-318 (1974) · Zbl 0297.05004 |
| [19] | Avis, D.; Newborn, M., On pop-stacks in series, Utilitas Math., 19, 129-140 (1981) · Zbl 0461.68060 |
| [20] | Shapiro, L.; Stephens, A. B., Bootstrap percolation, the Schröder numbers, and the \(n\)-kings problem, SIAM J. Discrete Math., 4, 2, 275-280 (1991) · Zbl 0736.05008 |
| [21] | Stanley, R. P., Enumerative Combinatorics, vol. 1, Cambridge Stud. Adv. Math., vol. 49 (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0889.05001 |
| [22] | Corneil, D. G.; Lerchs, H.; Burlingham, L. S., Complement reducible graphs, Discrete Appl. Math., 3, 3, 163-174 (1981) · Zbl 0463.05057 |
| [23] | Stanley, R. P., Enumerative Combinatorics, vol. 2, Cambridge Stud. Adv. Math., vol. 62 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001 |
| [24] | Higman, G., Ordering by divisibility in abstract algebras, Proc. London Math. Soc. (3), 2, 326-336 (1952) · Zbl 0047.03402 |
| [25] | Guibert, O.; Pergola, E., Enumeration of vexillary involutions which are equal to their mirror/complement, Discrete Math., 224, 1-3, 281-287 (2000), URL · Zbl 0963.05009 |
| [26] | Egge, E. S., Restricted symmetric permutations, preprint. URL · Zbl 1141.05003 |
| [27] | M.H. Albert, R.E.L. Aldred, M.D. Atkinson, H.P. van Ditmarsch, C.C. Handley, D.A. Holton, D.J. McCaughan, C.W. Monteith, Cyclically closed pattern classes of permutations, Australas. J. Combin., in press; M.H. Albert, R.E.L. Aldred, M.D. Atkinson, H.P. van Ditmarsch, C.C. Handley, D.A. Holton, D.J. McCaughan, C.W. Monteith, Cyclically closed pattern classes of permutations, Australas. J. Combin., in press · Zbl 1141.05001 |
| [28] | R. Brignall, N. Ruškuc, V. Vatter, Simple permutations: Decidability and unavoidable substructures, Theoret. Comput. Sci., in press. URL http://arxiv.org/abs/math.CO/0609211; R. Brignall, N. Ruškuc, V. Vatter, Simple permutations: Decidability and unavoidable substructures, Theoret. Comput. Sci., in press. URL http://arxiv.org/abs/math.CO/0609211 · Zbl 1133.05001 |
| [29] | M.M. Murphy, Restricted permutations, antichains, atomic classes, and stack sorting, PhD thesis, Univ. of St Andrews, 2002; M.M. Murphy, Restricted permutations, antichains, atomic classes, and stack sorting, PhD thesis, Univ. of St Andrews, 2002 |
| [30] | Ehrenfeucht, A.; McConnell, R., A \(k\)-structure generalization of the theory of 2-structures, Theoret. Comput. Sci., 132, 1-2, 209-227 (1994) · Zbl 0808.05089 |
| [31] | Schmerl, J. H.; Trotter, W. T., Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., 113, 1-3, 191-205 (1993) · Zbl 0776.06002 |
| [32] | Giakoumakis, V., On the closure of graphs under substitution, Discrete Math., 177, 1-3, 83-97 (1997), URL · Zbl 0893.05019 |
| [33] | Zverovich, I., A finiteness theorem for primal extensions, Discrete Math., 296, 1, 103-116 (2005), URL · Zbl 1074.05076 |
| [34] | Bóna, M., Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps, J. Combin. Theory Ser. A, 80, 2, 257-272 (1997), URL · Zbl 0887.05004 |
| [35] | O. Guibert, Combinatoire des permutations à motifs exclus, en liaison avec mots, cartes planaires et tableaux de Young, PhD thesis, LaBRI, Université Bordeaux 1, 1995; O. Guibert, Combinatoire des permutations à motifs exclus, en liaison avec mots, cartes planaires et tableaux de Young, PhD thesis, LaBRI, Université Bordeaux 1, 1995 |
| [36] | Guibert, O.; Pergola, E.; Pinzani, R., Vexillary involutions are enumerated by Motzkin numbers, Ann. Comb., 5, 2 (2001), 153-147, URL · Zbl 0988.05001 |
| [37] | Jaggard, A. D., Prefix exchanging and pattern avoidance by involutions, Electron. J. Combin., 9, 2 (2002/03), Research paper 16, 24 pp. (electronic) · Zbl 1045.05002 |
| [38] | Bousquet-Mélou, M.; Steingrímsson, E., Decreasing subsequences in permutations and Wilf equivalence for involutions, J. Algebraic Combin., 22, 4, 383-409 (2005), URL · Zbl 1085.05002 |
| [39] | Robertson, A.; Saracino, D.; Zeilberger, D., Refined restricted permutations, Ann. Comb., 6, 3-4, 427-444 (2002) · Zbl 1017.05014 |
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.
