Decompositions and statistics for β(1,0)-trees and nonseparable permutations

Research output: Contribution to journalArticle

6 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)313–328
Number of pages16
JournalAdvances in Applied Mathematics
Volume42
Issue number3
Early online date26 Nov 2008
DOIs
Publication statusPublished - Mar 2009

Fingerprint

Nonseparable
Permutation
Statistics
Decomposition
Decompose
Bijection
Planar Maps
Trees (mathematics)
Sorting
Computer science
Involution
Pattern-avoiding Permutation
Generating Trees
Permutation Statistics
Ascent
Reverse
Leaves
Computer Science

Keywords

  • stack sorting
  • trees
  • pattern avoidance
  • decompositions
  • nonseparable
  • planar maps
  • involution bijection
  • statistics
  • beta(1,0)-trees
  • permutations

Cite this

@article{aa212e5a2734494198fac1d1aabb537d,
title = "Decompositions and statistics for β(1,0)-trees and nonseparable permutations",
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.",
keywords = "stack sorting , trees, pattern avoidance, decompositions, nonseparable, planar maps, involution bijection, statistics, beta(1,0)-trees, permutations",
author = "Anders Claesson and Sergey Kitaev and Einar Steingrimsson",
year = "2009",
month = "3",
doi = "10.1016/j.aam.2008.09.001",
language = "English",
volume = "42",
pages = "313–328",
journal = "Advances in Applied Mathematics",
issn = "0196-8858",
publisher = "Academic Press Inc.",
number = "3",

}

Decompositions and statistics for β(1,0)-trees and nonseparable permutations. / Claesson, Anders; Kitaev, Sergey; Steingrimsson, Einar.

In: Advances in Applied Mathematics, Vol. 42, No. 3, 03.2009, p. 313–328.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Decompositions and statistics for β(1,0)-trees and nonseparable permutations

AU - Claesson, Anders

AU - Kitaev, Sergey

AU - Steingrimsson, Einar

PY - 2009/3

Y1 - 2009/3

N2 - 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.

AB - 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.

KW - stack sorting

KW - trees

KW - pattern avoidance

KW - decompositions

KW - nonseparable

KW - planar maps

KW - involution bijection

KW - statistics

KW - beta(1,0)-trees

KW - permutations

U2 - 10.1016/j.aam.2008.09.001

DO - 10.1016/j.aam.2008.09.001

M3 - Article

VL - 42

SP - 313

EP - 328

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

IS - 3

ER -