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

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 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

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

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