Tuesday, October 10, 3:00PM
Lieb, Room 319
Stevens Institute of Technology
Abstract
I will discuss my recent work in the field of "pattern avoiding
permutations". A permutation p_1,p_2,...,p_n of 1,2,...,n is said to
contain a subpattern (213 say) if some p_{i_1},p_{i_2},p_{i_3} occur
with p_{i_2}
Knuth proved that if you pass a mixed-up permutation through a single
infinite stack, then it can be sorted back to 1,2,...,n if and only if
it does not contain a 213 subpattern. It follows that the number of
such permutations is Catalan.
I will give an overview of the recent results about pattern-avoiding
permutations, and give my result about sorting permutations with two
stacks in series.