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

Publication Type:
Journal Article
Citation:
Advances in Applied Mathematics, 2006, 36 (2), pp. 96 - 105
Issue Date:
2006-02-01
Full metadata record
Files in This Item:
Filename Description Size
1324arxiv.pdfAccepted Manuscript Version132.35 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: