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 journalArticle

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 languageEnglish
Pages (from-to)155-177
Number of pages23
JournalFundamenta Informaticae
Volume117
Issue number1-4
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint

Permutation
Bijection
Subword
Enumeration
Consecutive

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

On simsun and double simsun permutations avoiding a pattern of length three. / Chuang, Wan Chen; Eu, Sen Peng; Fu, Tung Shan; Pan, Yeh Jong.

In: Fundamenta Informaticae, Vol. 117, No. 1-4, 2012, p. 155-177.

Research output: Contribution to journalArticle

Chuang, Wan Chen ; Eu, Sen Peng ; Fu, Tung Shan ; Pan, Yeh Jong. / On simsun and double simsun permutations avoiding a pattern of length three. In: Fundamenta Informaticae. 2012 ; Vol. 117, No. 1-4. pp. 155-177.
@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 -