Permutations avoiding 1324 and patterns in Łukasiewicz paths

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

The class Av(1324), of permutations avoiding the pattern 1324, is one of the simplest sets of combinatorial objects to define that has, thus far, failed to reveal its enumerative secrets. By considering certain large subsets of the class, which consist of permutations with a particularly regular structure, we prove that the growth rate of the class exceeds 9.81. This improves on a previous lower bound of 9.47. Central to our proof is an examination of the asymptotic distributions of certain substructures in the Hasse graphs of the permutations. In this context, we consider occurrences of patterns in Łukasiewicz paths and prove that in the limit they exhibit a concentrated Gaussian distribution.
LanguageEnglish
Pages105–122
Number of pages18
JournalJournal of the London Mathematical Society
Volume92
Issue number1
Early online date16 Jun 2015
DOIs
Publication statusPublished - 1 Aug 2015

Fingerprint

Permutation
Path
Substructure
Asymptotic distribution
Gaussian distribution
Exceed
Lower bound
Subset
Graph in graph theory
Class
Context
Object

Keywords

  • permutations
  • permutation classes
  • Av(3124)
  • Łukasiewicz paths

Cite this

@article{f93ea3fb2884467e978d2c676ac844ea,
title = "Permutations avoiding 1324 and patterns in Łukasiewicz paths",
abstract = "The class Av(1324), of permutations avoiding the pattern 1324, is one of the simplest sets of combinatorial objects to define that has, thus far, failed to reveal its enumerative secrets. By considering certain large subsets of the class, which consist of permutations with a particularly regular structure, we prove that the growth rate of the class exceeds 9.81. This improves on a previous lower bound of 9.47. Central to our proof is an examination of the asymptotic distributions of certain substructures in the Hasse graphs of the permutations. In this context, we consider occurrences of patterns in Łukasiewicz paths and prove that in the limit they exhibit a concentrated Gaussian distribution.",
keywords = "permutations, permutation classes, Av(3124), Łukasiewicz paths",
author = "David Bevan",
year = "2015",
month = "8",
day = "1",
doi = "10.1112/jlms/jdv020",
language = "English",
volume = "92",
pages = "105–122",
journal = "Journal of the London Mathematical Society",
issn = "0024-6107",
number = "1",

}

Permutations avoiding 1324 and patterns in Łukasiewicz paths. / Bevan, David.

In: Journal of the London Mathematical Society, Vol. 92, No. 1, 01.08.2015, p. 105–122.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Permutations avoiding 1324 and patterns in Łukasiewicz paths

AU - Bevan, David

PY - 2015/8/1

Y1 - 2015/8/1

N2 - The class Av(1324), of permutations avoiding the pattern 1324, is one of the simplest sets of combinatorial objects to define that has, thus far, failed to reveal its enumerative secrets. By considering certain large subsets of the class, which consist of permutations with a particularly regular structure, we prove that the growth rate of the class exceeds 9.81. This improves on a previous lower bound of 9.47. Central to our proof is an examination of the asymptotic distributions of certain substructures in the Hasse graphs of the permutations. In this context, we consider occurrences of patterns in Łukasiewicz paths and prove that in the limit they exhibit a concentrated Gaussian distribution.

AB - The class Av(1324), of permutations avoiding the pattern 1324, is one of the simplest sets of combinatorial objects to define that has, thus far, failed to reveal its enumerative secrets. By considering certain large subsets of the class, which consist of permutations with a particularly regular structure, we prove that the growth rate of the class exceeds 9.81. This improves on a previous lower bound of 9.47. Central to our proof is an examination of the asymptotic distributions of certain substructures in the Hasse graphs of the permutations. In this context, we consider occurrences of patterns in Łukasiewicz paths and prove that in the limit they exhibit a concentrated Gaussian distribution.

KW - permutations

KW - permutation classes

KW - Av(3124)

KW - Łukasiewicz paths

U2 - 10.1112/jlms/jdv020

DO - 10.1112/jlms/jdv020

M3 - Article

VL - 92

SP - 105

EP - 122

JO - Journal of the London Mathematical Society

T2 - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

SN - 0024-6107

IS - 1

ER -