Abstract:

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 rooted nonseparable 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 7 statistics, between the avoiders and the trees.

This is joint work (in progress) with Sergey Kitaev and Einar Steingrímsson.