On pattern avoiding indecomposable permutations

Alice L. L. Gao, Sergey Kitaev, Philip B. Zhang

Research output: Contribution to journalArticle

20 Downloads (Pure)

Abstract

Comtet introduced the notion of indecomposable permutations in 1972. A permutation is indecomposable if and only if it has no proper prefix which is itself a permutation. Indecomposable permutations were studied in the literature in various contexts. In particular, this notion has been proven to be useful in obtaining non-trivial enumeration and equidistribution results on permutations. In this paper, we give a complete classification of indecomposable permutations avoiding a classical pattern of length 3 or 4, and of indecomposable permutations avoiding a non-consecutive vincular pattern of length 3. Further, we provide a recursive formula for enumerating 12 ••• k-avoiding indecomposable permutations for k ≥ 3. Several of our results involve the descent statistic. We also provide a bijective proof of a fact relevant to our studies.
Original languageEnglish
Article numberA2
Number of pages23
JournalIntegers: Electronic Journal of Combinatorial Number Theory
Volume18
Publication statusPublished - 16 Jan 2018

Keywords

  • connected permutations
  • Bell numbers
  • Catalan numbers
  • pattern avoiding permutations
  • irreducible permutations
  • indecomposable permutations

Fingerprint Dive into the research topics of 'On pattern avoiding indecomposable permutations'. Together they form a unique fingerprint.

Cite this