The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns

DOI10.1016/J.JCTA.2004.07.014zbMATH Open1067.05003arXivmath/0403502OpenAlexW2105493981MaRDI QIDQ556857FDOQ556857

Miklós Bóna

Publication date: 23 June 2005

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We show the first known example for a pattern $q$ for which $li{m}_{noinfty}sqrt[n]S_n(q)$ is not an integer. We find the exact value of the limit and show that it is irrational. Then we generalize our results to an infinite sequence of patterns. Finally, we provide further generalizations that start explaining why certain patterns are easier to avoid than others. Finally, we show that if $q$ is a layered pattern of length $k$, then $L(q)geq(k-1{)}^2$ holds.

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

zbMATH Keywords

permutationpattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted permutations
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• Asymptotic values for degrees associated with strips of Young diagrams
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Wilf-equivalence for singleton classes
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• Permutations avoiding certain patterns: The case of length 4 and some generalizations
• On growth rates of closed permutation classes

Cited In (10)

• Permutations avoiding sets of patterns with long monotone subsequences
• Where the monotone pattern (mostly) rules
• Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
• Asymptotic enumeration of permutations avoiding generalized patterns
• New records in Stanley-Wilf limits
• Classical length-5 pattern-avoiding permutations
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
• Staircases, dominoes, and the growth rate of 1324-avoiders
• On the growth of merges and staircases of permutation classes
• A structural characterisation of \(\mathrm{Av}(1324)\) and new bounds on its growth rate

This page was built for publication: The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns

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