Finite transition matrices for permutations avoiding pairs of length four patterns

Darla Kremer; Wai Chee SHIU

doi:10.1016/S0012-365X(03)00042-6

Finite transition matrices for permutations avoiding pairs of length four patterns

Darla Kremer^*, Wai Chee SHIU

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

21 Citations (Scopus)

Abstract

We show that the four classes of pattern avoiding permutations, S _n(1234,3214), S _n(4123,3214), S _n(2341,2143) and S _n(1234,2143) are enumerated by the formula (4 ^n-1+2)/3. In an electronic appendix we provide finite transition matrices for the number |S _n(u,v)| of permutations avoiding pairs (u,v) of length four patterns where u contains the subsequence 123 and v contains the subsequence 321 as well as a transition matrix for |S _n(1234,43215)|.

Original language	English
Pages (from-to)	171-183
Number of pages	13
Journal	Discrete Mathematics
Volume	268
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(03)00042-6
Publication status	Published - 6 Jul 2003

Scopus Subject Areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

User-Defined Keywords

Forbidden subsequences
Pattern avoiding permutations
Restricted permutations

Access to Document

10.1016/S0012-365X(03)00042-6

Cite this

@article{ddb0f5a84d274d45879f375580f0e5aa,

title = "Finite transition matrices for permutations avoiding pairs of length four patterns",

abstract = "We show that the four classes of pattern avoiding permutations, S n(1234,3214), S n(4123,3214), S n(2341,2143) and S n(1234,2143) are enumerated by the formula (4 n-1+2)/3. In an electronic appendix we provide finite transition matrices for the number |S n(u,v)| of permutations avoiding pairs (u,v) of length four patterns where u contains the subsequence 123 and v contains the subsequence 321 as well as a transition matrix for |S n(1234,43215)|.",

keywords = "Forbidden subsequences, Pattern avoiding permutations, Restricted permutations",

author = "Darla Kremer and SHIU, {Wai Chee}",

year = "2003",

month = jul,

day = "6",

doi = "10.1016/S0012-365X(03)00042-6",

language = "English",

volume = "268",

pages = "171--183",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Finite transition matrices for permutations avoiding pairs of length four patterns

AU - Kremer, Darla

AU - SHIU, Wai Chee

PY - 2003/7/6

Y1 - 2003/7/6

N2 - We show that the four classes of pattern avoiding permutations, S n(1234,3214), S n(4123,3214), S n(2341,2143) and S n(1234,2143) are enumerated by the formula (4 n-1+2)/3. In an electronic appendix we provide finite transition matrices for the number |S n(u,v)| of permutations avoiding pairs (u,v) of length four patterns where u contains the subsequence 123 and v contains the subsequence 321 as well as a transition matrix for |S n(1234,43215)|.

AB - We show that the four classes of pattern avoiding permutations, S n(1234,3214), S n(4123,3214), S n(2341,2143) and S n(1234,2143) are enumerated by the formula (4 n-1+2)/3. In an electronic appendix we provide finite transition matrices for the number |S n(u,v)| of permutations avoiding pairs (u,v) of length four patterns where u contains the subsequence 123 and v contains the subsequence 321 as well as a transition matrix for |S n(1234,43215)|.

KW - Forbidden subsequences

KW - Pattern avoiding permutations

KW - Restricted permutations

UR - http://www.scopus.com/inward/record.url?scp=84867934467&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(03)00042-6

DO - 10.1016/S0012-365X(03)00042-6

M3 - Article

AN - SCOPUS:84867934467

SN - 0012-365X

VL - 268

SP - 171

EP - 183

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Finite transition matrices for permutations avoiding pairs of length four patterns

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this