Generating and enumerating 321-avoiding and skew-merged simple permutations

MaRDI QIDQ1953536zbMATH OpenFDO

Authors Vincent Vatter, Michael Albert

Publication date 7 June 2013

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.3122, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p44

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

enumeration of the simple skew-merged permutationspermutation patternsimple permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: The simple permutations in two permutation classes --- the 321-avoiding permutations and the skew-merged permutations --- are enumerated using a uniform method. In both cases, these enumerations were known implicitly, by working backwards from the enumeration of the class, but the simple permutations had not been enumerated explicitly. In particular, the enumeration of the simple skew-merged permutations leads to the first truly structural enumeration of this class as a whole. The extension of this method to a wider collection of classes namely grid classes of infinite paths is discussed.

Review text

Summary: The simple permutations in two permutation classes -- the \(321\)-avoiding permutations and the skew-merged permutations -- are enumerated using a uniform method. In both cases, these enumerations were known implicitly, by working backwards from the enumeration of the class, but the simple permutations had not been enumerated explicitly. In particular, the enumeration of the simple skew-merged permutations leads to the first truly structural enumeration of this class as a whole. The extension of this method to a wider collection of classes namely grid classes of infinite paths is discussed.

Recommendations

• The enumeration of permutations avoiding 3124 and 4312
• Simple permutations and pattern restricted permutations
• The permutation class Av(4213,2143)
• scientific article; zbMATH DE number 2186865
• The enumeration of three pattern classes using monotone grid classes

Cited in

(7)

• Longest increasing subsequences and log concavity
• Universal limits of substitution-closed permutation classes
• Well-quasi-order for permutation graphs omitting a path and a clique
• Rationality for subclasses of 321-avoiding permutations
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Labelled well-quasi-order for permutation classes
• First-order convergence for 321-avoiding permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Generating and enumerating 321-avoiding and skew-merged simple permutations

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