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

Research Institute for Symbolic Computation

Research output: Working paper and reports › Preprint

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.

Original language	English
Place of Publication	Hagenberg
Publisher	RISC
Number of pages	13
DOIs	https://doi.org/10.48550/arXiv.1309.7117
Publication status	Published - 2013

Publication series

Name	arXiv.org
No.	1309.7117

Fields of science

101001 Algebra
101002 Analysis
101 Mathematics
102 Computer Sciences
102011 Formal languages
101009 Geometry
101013 Mathematical logic
101020 Technical mathematics
101025 Number theory
101012 Combinatorics
101005 Computer algebra
101006 Differential geometry
101003 Applied geometry
102025 Distributed systems

JKU Focus areas

Computation in Informatics and Mathematics

Access to Document

10.48550/arXiv.1309.7117

Cite this

@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 -

Using functional equations to enumerate 1324-avoiding permutations

Abstract

Publication series

Fields of science

JKU Focus areas

Access to Document

Other files and links

Cite this