On the sub-permutations of pattern avoiding permutations

DOI10.1016/J.DISC.2014.06.028MaRDI QIDQ465287zbMATH OpenOpenAlexFDO

Authors Filippo Disanto, Thomas Wiehe

Publication date 31 October 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

binary increasing treespattern avoidancepattern-searchsub-permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Analysis of algorithms and problem complexity (68Q25)

Abstract: There is a deep connection between permutations and trees. Certain sub-structures of permutations, called sub-permutations, bijectively map to sub-trees of binary increasing trees. This opens a powerful tool set to study enumerative and probabilistic properties of sub-permutations and to investigate the relationships between 'local' and 'global' features using the concept of pattern avoidance. First, given a pattern {mu}, we study how the avoidance of {mu} in a permutation {pi} affects the presence of other patterns in the sub-permutations of {pi}. More precisely, considering patterns of length 3, we solve instances of the following problem: given a class of permutations K and a pattern {mu}, we ask for the number of permutations $piinA{v}_n(mu)$ whose sub-permutations in K satisfy certain additional constraints on their size. Second, we study the probability for a generic pattern to be contained in a random permutation {pi} of size n without being present in the sub-permutations of {pi} generated by the entry $1leqkleqn$. These theoretical results can be useful to define efficient randomized pattern-search procedures based on classical algorithms of pattern-recognition, while the general problem of pattern-search is NP-complete.

Recommendations

• Pattern avoidance classes and subpermutations
• Subclasses of Baxter permutations based on pattern avoidance
• On pattern avoiding indecomposable permutations
• On the number of permutations avoiding a given pattern
• Pattern avoidance in partial permutations (extended abstract)
• On pattern avoiding alternating permutations
• Some equinumerous pattern-avoiding classes of permutations
• Pattern avoidance in poset permutations
• On bijections for pattern-avoiding permutations
• Pattern avoidance in partial permutations

Cites work

• Analytic combinatorics
• Avoiding patterns of length three in compositions and multiset permutations
• Counting strings in Dyck paths
• Descendants in increasing trees
• Dyck path enumeration
• ECO:a methodology for the enumeration of combinatorial objects
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Generating functions for generating trees
• Generating trees and the Catalan and Schröder numbers
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 177816 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1080355 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2081004 (Why is no real title available?)
• Non-contiguous pattern avoidance in binary trees
• Pattern avoidance in binary trees
• Pattern matching for permutations
• Pattern-avoiding Dyck paths
• Permutation trees and variation statistics
• Restricted permutations
• The kernel method: a collection of examples

Cited in

(2)

• On pattern-avoiding Fishburn permutations
• Another look at bijections for pattern-avoiding permutations

Describes a project that uses

Uses Software

• OEIS
• BinaryTrees

This page was built for publication: On the sub-permutations of pattern avoiding permutations

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