Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Permutations sortable by n-4 passes through a stack

Steingrimsson, Einar (2010) Permutations sortable by n-4 passes through a stack. Annals of Combinatorics, 14. pp. 45-51.

[img]
Preview
PDF (Permutations sortable by n-4 passes through a stack) - Submitted Version
Download (103Kb) | Preview

    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 West, and later proved by Zeilberger. Goulden and West found a bijection from such permutations to nonseparable planar maps, and later, Jacquard and Schaeffer presented a bijection from these planar maps to certain labeled plane trees, called beta(1,0)-trees. Using generating trees, Dulucq, Gire and West showed that nonseparable planar maps are equinumerous with permutations avoiding the (classical) pattern 2413 and the barred pattern 41\bar{3}52; they called these permutations nonseparable. We give a new bijection between beta(1,0)-trees and permutations avoiding the dashed patterns 3-1-4-2 and 2-41-3. These permutations can be seen to be exactly the reverse of nonseparable permutations. Our bijection is built using decompositions of the permutations and the trees, and it translates seven statistics on the trees into statistics on the permutations. Among the statistics involved are ascents, left-to-right minima and right-to-left maxima for the permutations, and leaves and the rightmost and leftmost paths for the trees. In connection with this we give a nontrivial involution on the beta(1,0)-trees, which specializes to an involution on unlabeled rooted plane trees, where it yields interesting results. Lastly, we conjecture the existence of a bijection between nonseparable permutations and two-stack sortable permutations preserving at least four permutation statistics.

    Item type: Article
    ID code: 33798
    Keywords: enumerate permutations, stack, Electronic computers. Computer science
    Subjects: Science > Mathematics > Electronic computers. Computer science
    Department: Faculty of Science > Computer and Information Sciences
    Related URLs:
      Depositing user: Pure Administrator
      Date Deposited: 20 Oct 2011 14:16
      Last modified: 13 Mar 2012 11:31
      URI: http://strathprints.strath.ac.uk/id/eprint/33798

      Actions (login required)

      View Item

      Fulltext Downloads: