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 |
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
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 journal › Article
}
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 -