Hostname: page-component-74656f9884-8rzl6 Total loading time: 0 Render date: 2026-11-06T09:40:22.491Z Has data issue: false hasContentIssue false
  • English
  • Français

A New Upper Bound for 1324-Avoiding Permutations

Published online by Cambridge University Press:  09 July 2014

MIKLÓS BÓNA
MIKLÓS BÓNA*
Affiliation:
Department of Mathematics, University of Florida, 358 Little Hall, PO Box 118105, Gainesville, FL 32611–8105, USA (e-mail: bona@ufl.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We prove that the number of 1324-avoiding permutations of length n is less than $(7+4\sqrt{3})^n$. The novelty of our method is that we injectively encode such permutations by a pair of words of length n over a finite alphabet that avoid a given factor.

Keywords

Primary 05A15Secondary 05A0505A1605A20

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 5: Honouring the Memory of Philippe Flajolet - Part 1 , September 2014 , pp. 717 - 724
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Albert, M. H., Elder, M., Rechnitzer, A., Westcott, P. and Zabrocki, M. (2006) On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. Appl. Math. 36 96–105.Google Scholar
[2]Arratia, R. (1999) On the Stanley–Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin. 6 #1.Google Scholar
[3]Bóna, M. (2007) New records in Stanley–Wilf limits. Europ. J. Combin. 28 75–85.CrossRefGoogle Scholar
[4]Bóna, M. (2012) Combinatorics of Permutations, second edition, CRC Press/Chapman & Hall.Google Scholar
[5]Claesson, A., Jelinek, V. and Steingrímsson, E. (2012) Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns. J.Combin. Theory Ser. A 119 1680–1691.CrossRefGoogle Scholar
[6]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
[7]Marcus, A. and Tardos, G. (2004) Excluded permutation matrices and the Stanley–Wilf conjecture. J. Combin. Theory Ser. A 107 153–160.CrossRefGoogle Scholar
[8]Simion, R. and Schmidt, F. (1985) Restricted permutations. Europ. J. Combin. 6 383–406.CrossRefGoogle Scholar