The permutation classes Av(1234,2341) and Av(1243,2314)

Research output: Contribution to journalArticle

Abstract

We investigate the structure of the two permutation classes defined by the sets of forbidden patterns {1234, 2341} and {1243, 2314}. By considering how the Hasse graphs of permutations in these classes can be built from a sequence of rooted source graphs, we determine their algebraic generating functions. Our approach is similar to that of “adding a slice”, used previously to enumerate various classes of polyominoes and other combinatorial structures. To solve the relevant functional equations, we make extensive use of the kernel method.
LanguageEnglish
Pages3–20
Number of pages18
JournalAustralasian Journal of Combinatorics
Volume64
Publication statusPublished - 29 Feb 2016

Fingerprint

Permutation
Polyominoes
Algebraic function
Kernel Methods
Graph in graph theory
Slice
Functional equation
Generating Function
Class

Keywords

  • permutation classes
  • kernel method
  • Hasse graphs

Cite this

@article{ce91c19cafd7484d9facfa5159ad03f6,
title = "The permutation classes Av(1234,2341) and Av(1243,2314)",
abstract = "We investigate the structure of the two permutation classes defined by the sets of forbidden patterns {1234, 2341} and {1243, 2314}. By considering how the Hasse graphs of permutations in these classes can be built from a sequence of rooted source graphs, we determine their algebraic generating functions. Our approach is similar to that of “adding a slice”, used previously to enumerate various classes of polyominoes and other combinatorial structures. To solve the relevant functional equations, we make extensive use of the kernel method.",
keywords = "permutation classes, kernel method, Hasse graphs",
author = "David Bevan",
year = "2016",
month = "2",
day = "29",
language = "English",
volume = "64",
pages = "3–20",
journal = "Australasian Journal of Combinatorics",
issn = "1034-4942",
publisher = "University of Queensland Press",

}

The permutation classes Av(1234,2341) and Av(1243,2314). / Bevan, David.

In: Australasian Journal of Combinatorics, Vol. 64, 29.02.2016, p. 3–20.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The permutation classes Av(1234,2341) and Av(1243,2314)

AU - Bevan, David

PY - 2016/2/29

Y1 - 2016/2/29

N2 - We investigate the structure of the two permutation classes defined by the sets of forbidden patterns {1234, 2341} and {1243, 2314}. By considering how the Hasse graphs of permutations in these classes can be built from a sequence of rooted source graphs, we determine their algebraic generating functions. Our approach is similar to that of “adding a slice”, used previously to enumerate various classes of polyominoes and other combinatorial structures. To solve the relevant functional equations, we make extensive use of the kernel method.

AB - We investigate the structure of the two permutation classes defined by the sets of forbidden patterns {1234, 2341} and {1243, 2314}. By considering how the Hasse graphs of permutations in these classes can be built from a sequence of rooted source graphs, we determine their algebraic generating functions. Our approach is similar to that of “adding a slice”, used previously to enumerate various classes of polyominoes and other combinatorial structures. To solve the relevant functional equations, we make extensive use of the kernel method.

KW - permutation classes

KW - kernel method

KW - Hasse graphs

UR - https://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p003.pdf

M3 - Article

VL - 64

SP - 3

EP - 20

JO - Australasian Journal of Combinatorics

T2 - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

SN - 1034-4942

ER -