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

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.