On simsun and double simsun permutations avoiding a pattern of length three

Wan Chen Chuang; Sen Peng Eu; Tung Shan Fu; Yeh Jong Pan

doi:10.3233/FI-2012-693

On simsun and double simsun permutations avoiding a pattern of length three

Wan Chen Chuang, Sen Peng Eu, Tung Shan Fu, Yeh Jong Pan

Research output: Contribution to journal › Article

2 Citations (Scopus)

Abstract

A permutation σ ε S _n is simsun if for all k, the subword of σ restricted to {1,... , k} does not have three consecutive decreasing elements. The permutation σ is double simsun if both σ and σ ^-1 are simsun. In this paper, we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.

Original language	English
Pages (from-to)	155-177
Number of pages	23
Journal	Fundamenta Informaticae
Volume	117
Issue number	1-4
DOIs	https://doi.org/10.3233/FI-2012-693
Publication status	Published - 2012
Externally published	Yes

Fingerprint

Keywords

double-simsun
increasing 1-2 tree
pattern-avoiding
Simsun permutation

ASJC Scopus subject areas

Information Systems
Computational Theory and Mathematics
Theoretical Computer Science
Algebra and Number Theory

Cite this

Chuang, W. C., Eu, S. P., Fu, T. S., & Pan, Y. J. (2012). On simsun and double simsun permutations avoiding a pattern of length three. Fundamenta Informaticae, 117(1-4), 155-177. https://doi.org/10.3233/FI-2012-693

@article{ceff63101d5f44e6ab47f62f09d8a590,

title = "On simsun and double simsun permutations avoiding a pattern of length three",

abstract = "A permutation σ ε S n is simsun if for all k, the subword of σ restricted to {1,... , k} does not have three consecutive decreasing elements. The permutation σ is double simsun if both σ and σ -1 are simsun. In this paper, we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.",

keywords = "double-simsun, increasing 1-2 tree, pattern-avoiding, Simsun permutation",

author = "Chuang, {Wan Chen} and Eu, {Sen Peng} and Fu, {Tung Shan} and Pan, {Yeh Jong}",

year = "2012",

doi = "10.3233/FI-2012-693",

language = "English",

volume = "117",

pages = "155--177",

journal = "Fundamenta Informaticae",

issn = "0169-2968",

publisher = "IOS Press",

number = "1-4",

}

TY - JOUR

T1 - On simsun and double simsun permutations avoiding a pattern of length three

AU - Chuang, Wan Chen

AU - Eu, Sen Peng

AU - Fu, Tung Shan

AU - Pan, Yeh Jong

PY - 2012

Y1 - 2012

N2 - A permutation σ ε S n is simsun if for all k, the subword of σ restricted to {1,... , k} does not have three consecutive decreasing elements. The permutation σ is double simsun if both σ and σ -1 are simsun. In this paper, we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.

AB - A permutation σ ε S n is simsun if for all k, the subword of σ restricted to {1,... , k} does not have three consecutive decreasing elements. The permutation σ is double simsun if both σ and σ -1 are simsun. In this paper, we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.

KW - double-simsun

KW - increasing 1-2 tree

KW - pattern-avoiding

KW - Simsun permutation

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

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

U2 - 10.3233/FI-2012-693

DO - 10.3233/FI-2012-693

M3 - Article

AN - SCOPUS:84863095778

VL - 117

SP - 155

EP - 177

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1-4

ER -

Access to Document

10.3233/FI-2012-693