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

Department of Mathematics

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

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

Keywords

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

ASJC Scopus subject areas

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

Access to Document

10.3233/FI-2012-693

Fingerprint Dive into the research topics of 'On simsun and double simsun permutations avoiding a pattern of length three'. Together they form a unique fingerprint.

Cite this

@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 = "Simsun permutation, double-simsun, increasing 1-2 tree, pattern-avoiding",

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 - Simsun permutation

KW - double-simsun

KW - increasing 1-2 tree

KW - pattern-avoiding

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 -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this