Where the monotone pattern (mostly) rules

DOI10.1016/J.DISC.2007.10.030zbMATH Open1186.05003arXiv0704.1489OpenAlexW1995381083MaRDI QIDQ998460FDOQ998460

Authors: Miklós Bóna 

Publication date: 28 January 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

pattern avoidanceprobabilityexpectationpattern avoiding permutationspatterns in permutations

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized permutation patterns and a classification of the Mahonian statistics
• Consecutive patterns in permutations
• Permutations without 3-sequences
• The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns
• New records in Stanley-Wilf limits
• Counting permutations by their rigid patterns
• A note on permutations without runs of given length
• Title not available (Why is that?)
• The Asymptotic Distribution of Runs of Consecutive Elements
• Note on Runs of Consecutive Elements

Cited In (5)

• Monotone clutters
• On three different notions of monotone subsequences
• From Hertzsprung's problem to pattern-rewriting systems
• Longest monotone subsequences and rare regions of pattern-avoiding permutations
• 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)