TY - JOUR
AB - We show that the Stanley-Wilf limit for the class of 4231-avoiding permutations is at least by 9.47. 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 Stanley-Wilf limit of a class of permutations avoiding a single permutation of length k cannot exceed (k-1)2. The result is established by constructing a sequence of finite automata that accept subclasses of the class of 4231-avoiding permutations and analysing their transition matrices. © 2005 Elsevier Inc. All rights reserved.
AU - Albert, MH
AU - Elder, M
AU - Rechnitzer, A
AU - Westcott, P
AU - Zabrocki, M
DA - 2006/01/01
DO - 10.1016/j.aam.2005.05.007
EP - 105
JO - Advances in Applied Mathematics
PY - 2006/01/01
SP - 96
TI - On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
VL - 36
Y1 - 2006/01/01
Y2 - 2023/12/04
ER -