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 Julian
West, and later proved by Doron Zeilberger. Goulden and West found a
bijection from such permutations to certain planar maps, and later
Cori, Jacquard and Schaeffer presented a bijection from these planar
maps to certain labeled plane trees.
We show that these labeled plane trees are in one-to-one
correspondence with permutations that avoid the generalized patterns
3-1-4-2 and 2-41-3. We do this by establishing a bijection, that
preserves 8 statistics, between the avoiders and the trees. Among the
statistics involved are descents, left-to-right maxima and
left-to-right minima for the permutations, and leaves and the
rightmost and leftmost paths for the trees.
In connection with this we conjecture the existence of a bijection
between avoiders and two-stack sortable permutations preserving at
least four permutation statistics.
This is joint work (in progress) with Anders Claesson and Sergey Kitaev.