On pattern avoiding indecomposable permutations

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

Research output: Contribution to journalArticle

14 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

Fingerprint

Permutation
Statistics
Equidistribution
Recursive Formula
Bijective
Prefix
Descent
Enumeration
Statistic
If and only if

Keywords

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

Cite this

@article{072a6a333b4c422d983b214bfdedd186,
title = "On pattern avoiding indecomposable permutations",
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.",
keywords = "connected permutations, Bell numbers, Catalan numbers, pattern avoiding permutations, irreducible permutations, indecomposable permutations",
author = "Gao, {Alice L. L.} and Sergey Kitaev and Zhang, {Philip B.}",
year = "2018",
month = "1",
day = "16",
language = "English",
volume = "18",
journal = "Integers: Electronic Journal of Combinatorial Number Theory",
issn = "1553-1732",

}

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

In: Integers: Electronic Journal of Combinatorial Number Theory, Vol. 18, A2, 16.01.2018.

Research output: Contribution to journalArticle

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 -