On pattern avoiding indecomposable permutations

Gao, Alice L. L. and Kitaev, Sergey and Zhang, Philip B. (2018) On pattern avoiding indecomposable permutations. Integers: Electronic Journal of Combinatorial Number Theory, 18. A2. ISSN 1553-1732

[thumbnail of Gao-etal-IEJCNT-2017-On-pattern-avoiding-indecomposable-permutations]
Preview
 Text. Filename: Gao_etal_IEJCNT_2017_On_pattern_avoiding_indecomposable_permutations.pdf
Accepted Author Manuscript
Download (285kB)| Preview

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.

CORE (COnnecting REpositories)