| Autor: |
Albert, MH, Elder, M, Rechnitzer, A, Westcott, P, Zabrocki, M |
| Rok vydání: |
2006 |
| Předmět: |
|
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
