Decomposing simple permutations, with enumerative consequences

RLF Brignall, S Huczynska, V Vatter

Research output: Contribution to journalArticle (Academic Journal)peer-review

11 Citations (Scopus)

Abstract

We prove that every sufficiently long simple permutation contains two long almost disjoint simple subsequences, and then we show how this result has enumerative consequences. For example, it implies that, for any r, the number of permutations with at most r copies of 132 has an algebraic generating function (this was previously proved, constructively, by Bóna and (independently) Mansour and Vainshtein).
Translated title of the contributionDecomposing simple permutations, with enumerative consequences
Original languageEnglish
Pages (from-to)385 - 400
Number of pages16
JournalCombinatorica
Volume28 (4)
DOIs
Publication statusPublished - Jul 2008

Bibliographical note

Publisher: Springer

Fingerprint Dive into the research topics of 'Decomposing simple permutations, with enumerative consequences'. Together they form a unique fingerprint.

Cite this