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 | |
Publication status | Published - 2012 |
Externally published | Yes |
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