School of Physical Sciences
         ALGEBRA AND COMBINATORICS SEMINAR

      Tuesday 4 March 2008, 3pm in Room 67-641


  Pattern avoiding permutations and sorting with stacks

                  Murray Elder

           University of Queensland

Abstract
You have a mixed-up sequence of numbers 1..n, and want to put them in 
order by passing the sequence one-way though the stack. Knuth proved that 
you can do it iff the sequence does not contain a Middle -BIG - small 
subsequence. And so began the field of "pattern avoiding permutations", in 
this case the pattern to avoid is 231. Knuth showed that the number of such 
permutations of length n is the n-th Catalan number, and now we know that's  
true for every length 3 pattern.

I will introduce this interesting field and discuss some of my own work 
about what you get when you have more than one stack to play with.

All welcome.