On the number of permutations avoiding a given pattern (Q1971017)

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.