Decomposing simple permutations with enumerative consequences

Robert Brignall, Sophie Huczynska, Vincent Vatter

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that evely sufficiently long simple permutation contains two long almost disjoint simple subsequence, and then we show how this result has enumerative consequences. For example it, implies that, for any gamma(1) the number of permutations with at most r copies of 132 has an algebraic generating function (this was previously proved, constructively, by Bona and (independently) Mansour and Vainshtein).

Original languageEnglish
Pages (from-to)385-400
Number of pages16
JournalCombinatorica
Volume28
Issue number4
DOIs
Publication statusPublished - Jul 2008

Keywords

  • COUNTING OCCURRENCES
  • RESTRICTED PERMUTATIONS
  • PRESCRIBED NUMBER
  • PATTERN
  • 132-SUBSEQUENCES

Fingerprint

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

Cite this