DocServer

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

Albert, M.H. and Elder, M. and Rechnitzer, A. and Westcott, P. and Zabrocki, M. (2006) On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia. Advances in Applied Mathematics, 36 (2). pp. 96-105. ISSN 01968858

[img]
Preview
PDF - Accepted Version
Download (119Kb) | Preview

    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.

    Item Type: Article
    Subjects: 05-xx Combinatorics > 05Axx Enumerative combinatorics
    Faculty: UNSPECIFIED
    Depositing User: Dr Murray Elder
    Date Deposited: 17 Sep 2012 10:42
    Last Modified: 17 Sep 2012 10:42
    URI: https://docserver.carma.newcastle.edu.au/id/eprint/1074

    Actions (login required)

    View Item