  The subject of pattern avoiding permutations has its roots in computer
science, namely in the problem of sorting a permutation through a stack. A
formula for the number of permutations of length n that can be sorted by
passing it twice through a stack (where the letters on the stack have to be in
increasing order) was conjectured by West, and later proved by Zeilberger.
Goulden and West found a bijection from such permutations to nonseparable
planar maps, and later, Jacquard and Schaeffer presented a bijection from these
planar maps to certain labeled plane trees, called beta(1,0)-trees. Using
generating trees, Dulucq, Gire and West showed that nonseparable planar maps
are equinumerous with permutations avoiding the (classical) pattern 2413 and
the barred pattern 41\bar{3}52; they called these permutations nonseparable. We
give a new bijection between beta(1,0)-trees and permutations avoiding the
dashed patterns 3-1-4-2 and 2-41-3. These permutations can be seen to be
exactly the reverse of nonseparable permutations. Our bijection is built using
decompositions of the permutations and the trees, and it translates seven
statistics on the trees into statistics on the permutations. Among the
statistics involved are ascents, left-to-right minima and right-to-left maxima
for the permutations, and leaves and the rightmost and leftmost paths for the
trees. In connection with this we give a nontrivial involution on the
beta(1,0)-trees, which specializes to an involution on unlabeled rooted plane
trees, where it yields interesting results. Lastly, we conjecture the existence
of a bijection between nonseparable permutations and two-stack sortable
permutations preserving at least four permutation statistics.
