On the number of permutations avoiding a given pattern
type: Item
instance of: scholarly article
title: On the number of permutations avoiding a given pattern
zbMATH Open document ID: 0948.05003
author: Noga Alon
author: Ehud Friedgut
published in: Journal of Combinatorial Theory. Series A
publication date: 2000-11-19T00:00:00Z
review text: R. P. Stanley and H. Wilf [see, e.g., \textit{M. Bóna}, J. Comb. Theory, Ser. A 85, No. 1, 96-104 (1999; Zbl 0919.05002)] conjectured that for the number \(F(n,\sigma)\) of \(n\)-permutations avoiding (not containing) a given permutation \(\sigma\) there exists a constant \(c= c(\sigma)\) such that \(F(n,\sigma)\leq c^n\) for all \(n\). Using results about generalized Davenport-Schinzel sequences, the authors prove a slightly weaker statement: \(F(n,\sigma)\leq c^{n\gamma^*(n)}\), where \(\gamma^*(n)\) is an extremaly slowly growing function, related to the Ackermann hierarchy. They also prove that the conjecture holds for every permutation which consists of an increasing subsequence followed by a decreasing one, or vice versa.
reviewed by: Indulis Strazdins
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A20
zbMATH DE Number: 1421336
zbMATH Keywords: pattern
zbMATH Keywords: permutation
zbMATH Keywords: Davenport-Schinzel sequences
MaRDI profile type: Publication
full work available at URL: jcta.1999.3002
OpenAlex ID: W2021480278
cites work: Permutations avoiding certain patterns: The case of length 4 and some generalizations
cites work: Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
cites work: The solution of a conjecture of Stanley and Wilf for all layered patterns
cites work: Q3137399
cites work: Generalized Davenport-Schinzel sequences
cites work: Asymptotic values for degrees associated with strips of Young diagrams
cites work: Q4325546
cites work: Restricted permutations
DOI: 10.1006/JCTA.1999.3002
description: scientific article; zbMATH DE number 1421336