On pattern avoiding indecomposable permutations

MaRDI QIDQ5384205zbMATH OpenFDO

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

Publication date 21 June 2019

Full work available at URL https://arxiv.org/abs/1605.05490, http://math.colgate.edu/~integers/s2/s2.pdf

zbMATH Keywords

equidistributionnon-trivial enumeration

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

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 $12cdotsk$-avoiding indecomposable permutations for $kgeq3$. Several of our results involve the descent statistic. We also provide a bijective proof of a fact relevant to our studies.

Recommendations

• Generating indecomposable permutations
• Avoiding patterns in irreducible permutations
• On the number of indecomposable permutations with a given number of cycles
• Pattern avoidance in compositions and multiset permutations
• Indecomposable permutations with a given number of cycles

Cites work

• A bijection between atomic partitions and unsplitable partitions
• A new record for \(1324\)-avoiding permutations
• Classification of bijections between 321- and 132-avoiding permutations
• Consecutive patterns in permutations
• Counting 1324-avoiding permutations
• Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• Generalized pattern avoidance
• Generalized permutation patterns -- a short survey
• Generalized permutation patterns and a classification of the Mahonian statistics
• Generating indecomposable permutations
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 3389044 (Why is no real title available?)
• Hypermaps and indecomposable permutations
• Indecomposable permutations, hypermaps and labeled Dyck paths
• On \(1324\)-avoiding permutations
• Patterns in permutations and words.
• Permutations avoiding 1324 and patterns in Łukasiewicz paths
• Some statistics on the hypercubes of Catalan permutations
• Symmetric functions and P-recursiveness
• Using functional equations to enumerate 1324-avoiding permutations

Cited in

(16)

• A family of Bell transformations
• Refined Wilf-equivalences by Comtet statistics
• On the poset of non-attacking King permutations
• On pattern-avoiding Fishburn permutations
• Permutation patterns and cell decompositions
• Generating indecomposable permutations
• Indecomposable permutations with a given number of cycles
• On the number of indecomposable permutations with a given number of cycles
• A spectral approach to consecutive pattern-avoiding permutations
• On the sub-permutations of pattern avoiding permutations
• scientific article; zbMATH DE number 7731168 (Why is no real title available?)
• Vincular pattern avoidance on cyclic permutations
• Pattern-avoiding stabilized-interval-free permutations
• Pattern avoiding permutations enumerated by inversions
• A combinatorial Hopf algebra on partition diagrams
• Another look at bijections for pattern-avoiding permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On pattern avoiding indecomposable permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384205)