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

Albert, MH; Elder, M; Rechnitzer, A; Westcott, P; Zabrocki, M

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

Albert, MH Elder, M

Rechnitzer, A Westcott, P Zabrocki, M

Permalink

Publication Type:: Journal Article
Citation:: Advances in Applied Mathematics, 2006, 36 (2), pp. 96 - 105
Issue Date:: 2006-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (132.35 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Albert, MH	en_US
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.contributor.author	Rechnitzer, A	en_US
dc.contributor.author	Westcott, P	en_US
dc.contributor.author	Zabrocki, M	en_US
dc.date.issued	2006-01-01	en_US
dc.identifier.citation	Advances in Applied Mathematics, 2006, 36 (2), pp. 96 - 105	en_US
dc.identifier.issn	0196-8858	en_US
dc.identifier.uri	http://hdl.handle.net/10453/98769
dc.description.abstract	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.	en_US
dc.relation.ispartof	Advances in Applied Mathematics	en_US
dc.relation.isbasedon	10.1016/j.aam.2005.05.007	en_US
dc.subject.classification	Applied Mathematics	en_US
dc.title	On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia	en_US
dc.type	Journal Article
utslib.citation.volume	2	en_US
utslib.citation.volume	36	en_US
utslib.for	0101 Pure Mathematics	en_US
utslib.for	0102 Applied Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access
pubs.issue	2	en_US
pubs.publication-status	Published	en_US
pubs.volume	36	en_US

Abstract:

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:

http://hdl.handle.net/10453/98769