Computational approaches to consecutive pattern avoidance in permutations

MaRDI QIDQ2915627zbMATH OpenFDO

Authors Brian Nakamura

Publication date 18 September 2012

Published in PU.M.A. Pure Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.2480

zbMATH Keywords

permutationenumerationconsecutive pattern avoidancecounting permutationsCAVcluster tail generating functionsingle pattern avoidance

Mathematics Subject Classification ID

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

Abstract: In recent years, there has been increasing interest in consecutive pattern avoidance in permutations. In this paper, we introduce two approaches to counting permutations that avoid a set of prescribed patterns consecutively. These algoritms have been implemented in the accompanying Maple package CAV, which can be downloaded from the author's website. As a byproduct of the first algorithm, we have a theorem giving a sufficient condition for when two pattern sets are strongly (consecutively) Wilf-Equivalent. For the implementation of the second algorithm, we define the cluster tail generating function and show that it always satisfies a certain functional equation. We also explain how the CAV package can be used to approximate asymptotic constants for single pattern avoidance.

Recommendations

• A probabilistic approach to consecutive pattern avoiding in permutations
• scientific article; zbMATH DE number 7058688
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• The most and the least avoided consecutive patterns
• Avoiding consecutive patterns in permutations

Cited in

(15)

• Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
• Consecutive patterns in inversion sequences. II: Avoiding patterns of relations
• Inversion sequences avoiding consecutive patterns
• Using homological duality in consecutive pattern avoidance
• A necessary condition for c-Wilf equivalence
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• Constraining strong \(c\)-Wilf equivalence using cluster poset asymptotics
• Wilf equivalence relations for consecutive patterns
• Consecutive patterns in Coxeter groups
• CAV
• Increasing consecutive patterns in words
• Consecutive pattern containment and c-Wilf equivalence
• Refined consecutive pattern enumeration via a generalized cluster method
• A probabilistic approach to consecutive pattern avoiding in permutations
• A spectral approach to consecutive pattern-avoiding permutations

Describes a project that uses

Uses Software

• Maple

This page was built for publication: Computational approaches to consecutive pattern avoidance in permutations

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