Where the monotone pattern (mostly) rules

DOI10.1016/J.DISC.2007.10.030MaRDI QIDQ998460zbMATH OpenOpenAlexFDO

Authors Miklós Bóna

Publication date 28 January 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pattern avoidanceprobabilityexpectationpattern avoiding permutationspatterns in permutations

Mathematics Subject Classification ID

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

Abstract: We consider pattern containment and avoidance with a very tight definition that was used first by Riordan more than 60 years ago. Using this definition, we prove the monotone pattern is easier to avoid than almost any other pattern of the same length. We also show that with this definition, almost all patterns of length $k$ are avoided by the same number of permutations of length $n$. The corresponding statements are not known to be true for more relaxed definitions of pattern containment. This is the first time we know of that expectations are used to compare numbers of permutations avoiding certain patterns.

Recommendations

• Monotone Series
• The monotone cumulants
• Synergy of monotonic rules
• Monotone clutters
• On the monotony of certain sequences
• scientific article; zbMATH DE number 3246828
• Monotone triangles and 312 pattern avoidance
• scientific article; zbMATH DE number 1554750

Cites work

• scientific article; zbMATH DE number 3529866 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• A note on permutations without runs of given length
• Consecutive patterns in permutations
• Counting permutations by their rigid patterns
• Generalized permutation patterns and a classification of the Mahonian statistics
• New records in Stanley-Wilf limits
• Note on Runs of Consecutive Elements
• Permutations without 3-sequences
• The Asymptotic Distribution of Runs of Consecutive Elements
• The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns

Cited in

(5)

• From Hertzsprung's problem to pattern-rewriting systems
• Monotone clutters
• Longest monotone subsequences and rare regions of pattern-avoiding permutations
• On three different notions of monotone subsequences
• A land of monotone plenty

This page was built for publication: Where the monotone pattern (mostly) rules

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