The permutation class Av(4213,2143)

Research output: Contribution to journalArticle

Abstract

We determine the structure of permutations avoiding the patterns 4213 and 2143. Each such permutation consists of the skew sum of a sequence of plane trees, together with an increasing sequence of points above and an increasing sequence of points to its left. We use this characterisation to establish the generating function enumerating these permutations. We also investigate the properties of a typical large permutation in the class and prove that if a large permutation that avoids 4213 and 2143 is chosen uniformly at random, then it is more likely than not to avoid 2413 as well.
LanguageEnglish
Article number#10
Number of pages14
JournalDiscrete Mathematics and Theoretical Computer Science
Volume18
Issue number2
StatePublished - 4 Apr 2017

Fingerprint

Permutation
Monotonic increasing sequence
Skew
Generating Function
Likely
Class

Keywords

  • permutation classes
  • permutation avoidance
  • permutation patterns
  • generalised grid classes.

Cite this

@article{63d1362e852b4ab8a37ab736dda24064,
title = "The permutation class Av(4213,2143)",
abstract = "We determine the structure of permutations avoiding the patterns 4213 and 2143. Each such permutation consists of the skew sum of a sequence of plane trees, together with an increasing sequence of points above and an increasing sequence of points to its left. We use this characterisation to establish the generating function enumerating these permutations. We also investigate the properties of a typical large permutation in the class and prove that if a large permutation that avoids 4213 and 2143 is chosen uniformly at random, then it is more likely than not to avoid 2413 as well.",
keywords = "permutation classes, permutation avoidance, permutation patterns, generalised grid classes.",
author = "David Bevan",
year = "2017",
month = "4",
day = "4",
language = "English",
volume = "18",
journal = "Discrete Mathematics and Theoretical Computer Science",
issn = "1365-8050",
publisher = "Maison de l'informatique et des mathematiques discretes",
number = "2",

}

The permutation class Av(4213,2143). / Bevan, David.

In: Discrete Mathematics and Theoretical Computer Science, Vol. 18, No. 2, #10, 04.04.2017.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The permutation class Av(4213,2143)

AU - Bevan,David

PY - 2017/4/4

Y1 - 2017/4/4

N2 - We determine the structure of permutations avoiding the patterns 4213 and 2143. Each such permutation consists of the skew sum of a sequence of plane trees, together with an increasing sequence of points above and an increasing sequence of points to its left. We use this characterisation to establish the generating function enumerating these permutations. We also investigate the properties of a typical large permutation in the class and prove that if a large permutation that avoids 4213 and 2143 is chosen uniformly at random, then it is more likely than not to avoid 2413 as well.

AB - We determine the structure of permutations avoiding the patterns 4213 and 2143. Each such permutation consists of the skew sum of a sequence of plane trees, together with an increasing sequence of points above and an increasing sequence of points to its left. We use this characterisation to establish the generating function enumerating these permutations. We also investigate the properties of a typical large permutation in the class and prove that if a large permutation that avoids 4213 and 2143 is chosen uniformly at random, then it is more likely than not to avoid 2413 as well.

KW - permutation classes

KW - permutation avoidance

KW - permutation patterns

KW - generalised grid classes.

UR - http://dmtcs.episciences.org/volume/view/id/155

M3 - Article

VL - 18

JO - Discrete Mathematics and Theoretical Computer Science

T2 - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

SN - 1365-8050

IS - 2

M1 - #10

ER -