### Abstract

Original language | English |
---|---|

Article number | A2 |

Number of pages | 23 |

Journal | Integers: Electronic Journal of Combinatorial Number Theory |

Volume | 18 |

Publication status | Published - 16 Jan 2018 |

### Fingerprint

### Keywords

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

### Cite this

*Integers: Electronic Journal of Combinatorial Number Theory*,

*18*, [A2].

}

*Integers: Electronic Journal of Combinatorial Number Theory*, vol. 18, A2.

**On pattern avoiding indecomposable permutations.** / Gao, Alice L. L.; Kitaev, Sergey; Zhang, Philip B.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On pattern avoiding indecomposable permutations

AU - Gao, Alice L. L.

AU - Kitaev, Sergey

AU - Zhang, Philip B.

PY - 2018/1/16

Y1 - 2018/1/16

N2 - 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.

AB - 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.

KW - connected permutations

KW - Bell numbers

KW - Catalan numbers

KW - pattern avoiding permutations

KW - irreducible permutations

KW - indecomposable permutations

UR - http://math.colgate.edu/~integers/

M3 - Article

VL - 18

JO - Integers: Electronic Journal of Combinatorial Number Theory

JF - Integers: Electronic Journal of Combinatorial Number Theory

SN - 1553-1732

M1 - A2

ER -