Decomposing simple permutations, with enumerative consequences

DOI10.1007/S00493-008-2314-0MaRDI QIDQ2377669zbMATH OpenOpenAlexFDO

Authors Robert Brignall, Sophie Huczynska, Vincent Vatter

Publication date 20 January 2009

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0606186

zbMATH Keywords

alternationindecomposable graphsimple permutationpin sequencesimple subsequenceErdős-Szekeres theorem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07) Extremal combinatorics (05D99)

Abstract: We prove that every sufficiently long simple permutation contains two long almost disjoint simple subsequences. This result has applications to the enumeration of restricted permutations. For example, it immediately implies a result of Bona and (independently) Mansour and Vainshtein that for any r, the number of permutations with at most r copies of 132 has an algebraic generating function.

Recommendations

• scientific article; zbMATH DE number 2186865
• Small configurations in simple permutations
• Simple permutations and pattern restricted permutations
• Simple permutations and algebraic generating functions
• Simple permutations, alternating permutations, and the superpatterns that contain them.

Cites work

• scientific article; zbMATH DE number 2186865 (Why is no real title available?)
• scientific article; zbMATH DE number 2127712 (Why is no real title available?)
• scientific article; zbMATH DE number 1478125 (Why is no real title available?)
• Counting occurrences of 132 in a permutation
• Counting occurrences of 132 in an even permutation
• Counting occurrences of 231 in an involution
• Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
• Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
• Generalized permutation patterns and a classification of the Mahonian statistics
• Graph derivatives
• Indecomposable graphs
• On Intervals in Relational Structures
• Permutations with one or two 132-subsequences
• Restricted 132-alternating permutations and Chebyshev polynomials
• Restricted permutations
• Simple permutations and algebraic generating functions
• Simple permutations and pattern restricted permutations
• Simple permutations: Decidability and unavoidable substructures
• The enumeration of permutations with a prescribed number of ``forbidden patterns
• The number of permutations containing exactly one increasing subsequence of length three
• The number of permutations with exactly \(r\) 132-subsequences is \(P\)-recursive in the size!

Cited in

(17)

• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Simple permutations and algebraic generating functions
• Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
• Small configurations in simple permutations
• A counterexample regarding labelled well-quasi-ordering
• A survey of simple permutations
• Simple permutations: Decidability and unavoidable substructures
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
• Simple extensions of combinatorial structures
• Scaling limits of permutation classes with a finite specification: a dichotomy
• scientific article; zbMATH DE number 2186865 (Why is no real title available?)
• Substitution-closed pattern classes
• Almost avoiding permutations
• Characterising inflations of monotone grid classes of permutations
• Grid classes and partial well order
• Permutations destroying arithmetic structure
• The advantage of truncated permutations

This page was built for publication: Decomposing simple permutations, with enumerative consequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2377669)