Affiliations: Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung 811, Taiwan, ROC, [email protected]; [email protected] | Mathematics Faculty, National Pingtung Institute of Commerce, Pingtung 900, Taiwan, ROC, [email protected] | Department of Computer Science and Information Engineering, Tajen University, Pingtung 907, Taiwan, ROC, [email protected]
Note: [] Address for correspondence: Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung 811, Taiwan, ROC
Note: [] Research partially supported by NSC grants 98-2115-M-390-002 (S.-P. Eu), 99-2115-M-251-001 (T.-S. Fu), and 99-2115-M-127-001 (Y.-J. Pan).
Abstract: A permutation σ ∈ $\frak{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, pattern-avoiding, increasing 1-2 tree
