MIT Combinatorics Seminar

Stack sorting, trees and pattern avoidance

Einar Steingrímsson  (Reykjavík University)

Wednesday, May 02, 2007    4:15 pm    Room 2-136


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.