• CARMA COLLOQUIUM
  • Speaker: Assoc Prof Murray Elder, CARMA, The University of Newcastle
  • Title: Stack sorting and pattern-avoiding permutations
  • Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 4:00 pm, Thu, 18th Aug 2011
  • Abstract:

    Given a mixed-up sequence of distinct numbers, say 4 2 1 5 7 3 6, can you pass them through an infinite stack (first-in-last-out) from right to left, and put them in order?

                                    2 1 5 7 3 6
                         |   |
                         | 4 |
                         |___|
    
                                    1 5 7 3 6
                         |   |
                         | 2 |
                         | 4 |
                         |___|
     
        1                           5 7 3 6
                         |   |
                         | 2 |
                         | 4 |
                         |___|
     
        1 2                         5 7 3 6
                         |   |
                         | 4 |
                         |___|
    
    umm….. This talk will be about this problem - when can you do it with one stack, two stacks (in series), an infinite and a finite capacity stack in series, etc etc? How many permutations of 1,2,...,n are there that can be sorted? The answer will lie in the "forbidden subpatterns" of permutations, and it turns out there is a whole theory of this, which I will try to describe.


  • [Permanent link]