2016/05/18 by Gao, Alice L. L., Kitaev, Sergey, Zhang, Philip B. · 1 citation
#05A05 #05A15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1605.05490
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.