Using functional equations to enumerate 1324-avoiding permutations

Fredrik Johansson; Brian Nakamura

doi:10.48550/arXiv.1309.7117

Using functional equations to enumerate 1324-avoiding permutations

Fredrik Johansson
, Brian Nakamura

Institut für Symbolisches Rechnen

Publikation: Preprints, Working Paper und Forschungsberichte › Vorabpublikation

Abstract

We consider the problem of enumerating permutations with exactly r occurrences of the pattern 1324 and derive functional equations for this general case as well as for the pattern avoidance (r=0) case. The functional equations lead to a new algorithm for enumerating length n permutations that avoid 1324. This approach is used to enumerate the 1324-avoiders up to n=31. We also extend those functional equations to account for the number of inversions and derive analogous algorithms.

Originalsprache	Englisch
Erscheinungsort	Hagenberg
Herausgeber	RISC
Seitenumfang	13
DOIs	https://doi.org/10.48550/arXiv.1309.7117
Publikationsstatus	Veröffentlicht - 2013

Publikationsreihe

Name	arXiv.org
Nr.	1309.7117

Wissenschaftszweige

101001 Algebra
101002 Analysis
101 Mathematik
102 Informatik
102011 Formale Sprachen
101009 Geometrie
101013 Mathematische Logik
101020 Technische Mathematik
101025 Zahlentheorie
101012 Kombinatorik
101005 Computeralgebra
101006 Differentialgeometrie
101003 Angewandte Geometrie
102025 Verteilte Systeme

JKU-Schwerpunkte

Computation in Informatics and Mathematics

Zugriff auf Dokument

10.48550/arXiv.1309.7117

Andere Dateien und Links

http://arxiv.org/abs/1309.7117

Dieses zitieren

@techreport{1d2d6dbbcea6491e92b4b8626eb94376,

title = "Using functional equations to enumerate 1324-avoiding permutations",

abstract = "We consider the problem of enumerating permutations with exactly r occurrences of the pattern 1324 and derive functional equations for this general case as well as for the pattern avoidance (r=0) case. The functional equations lead to a new algorithm for enumerating length n permutations that avoid 1324. This approach is used to enumerate the 1324-avoiders up to n=31. We also extend those functional equations to account for the number of inversions and derive analogous algorithms.",

author = "Fredrik Johansson and Brian Nakamura",

year = "2013",

doi = "10.48550/arXiv.1309.7117",

language = "English",

series = "arXiv.org",

publisher = "RISC",

number = "1309.7117",

type = "WorkingPaper",

institution = "RISC",

}

TY - UNPB

T1 - Using functional equations to enumerate 1324-avoiding permutations

AU - Johansson, Fredrik

AU - Nakamura, Brian

PY - 2013

Y1 - 2013

N2 - We consider the problem of enumerating permutations with exactly r occurrences of the pattern 1324 and derive functional equations for this general case as well as for the pattern avoidance (r=0) case. The functional equations lead to a new algorithm for enumerating length n permutations that avoid 1324. This approach is used to enumerate the 1324-avoiders up to n=31. We also extend those functional equations to account for the number of inversions and derive analogous algorithms.

AB - We consider the problem of enumerating permutations with exactly r occurrences of the pattern 1324 and derive functional equations for this general case as well as for the pattern avoidance (r=0) case. The functional equations lead to a new algorithm for enumerating length n permutations that avoid 1324. This approach is used to enumerate the 1324-avoiders up to n=31. We also extend those functional equations to account for the number of inversions and derive analogous algorithms.

UR - http://arxiv.org/abs/1309.7117

U2 - 10.48550/arXiv.1309.7117

DO - 10.48550/arXiv.1309.7117

M3 - Preprint

T3 - arXiv.org

BT - Using functional equations to enumerate 1324-avoiding permutations

PB - RISC

CY - Hagenberg

ER -