On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia

Abstract

We construct a sequence of finite automata that accept subclasses of the class of 4231-avoiding permutations. We thereby show that the Wilf-Stanley limit for the class of 4231-avoiding permutations is bounded below by 9.35. This bound shows that this class has the largest such limit among all classes of permutations avoiding a single permutation of length 4 and refutes the conjecture that the Wilf-Stanley limit of a class of permutations avoiding a single permutation of length k cannot exceed (k-1)^2.

Submitted to Advances in Applied Mathematics

References in corpus (1)

• A New Class of Wilf-Equivalent Permutations

Cited by in corpus (19)

• Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
• A new upper bound for 1324-avoiding permutations
• Overview of some general results in combinatorial enumeration
• Problems and Conjectures presented at the Third International Conference on Permutation Patterns, University of Florida, March 7-11, 2005
• Pattern-Avoiding Involutions: Exact and Asymptotic Enumeration
• On the growth rate of 1324-avoiding permutations
• Permutations avoiding 1324 and patterns in Łukasiewicz paths
• Pattern avoidance in matchings and partitions
• Increasing and Decreasing Subsequences of Permutations and Their Variants
• On the Best Upper Bound for Permutations Avoiding A Pattern of a Given Length
• Enumeration schemes for restricted permutations
• Generalized permutation patterns -- a short survey
• Counting (3+1) - Avoiding permutations
• A new record for $1324$-avoiding permutations
• Interval minors of complete multipartite graphs
• Counting the Nontrivial Equivalence Classes of $S_n$ under $\{1234,3412\}$-Pattern-Replacement
• Patterns in Permutations and Involutions: A Structural and Enumerative Approach
• Permutations generated by a depth 2 and infinite stack in series are algebraic
• Interval minors of complete bipartite graphs