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

DOI10.1016/J.AAM.2008.09.001zbMATH Open1175.05006arXiv0801.4037OpenAlexW1982094376MaRDI QIDQ1012156FDOQ1012156

Authors: Anders Claesson, Sergey Kitaev, Einar Steingrímsson 

Publication date: 14 April 2009

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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�ar{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.

Full work available at URL: https://arxiv.org/abs/0801.4037

Recommendations

• Restricted non-separable planar maps and some pattern avoiding permutations
• Permutations with forbidden subsequences and nonseparable planar maps
• Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels
• Enumeration of permutations with restricted subsequences
• A combinatorial proof of J. West's conjecture

zbMATH Keywords

treesinvolutionbijectionnonseparablestack sortingplanar mapsbeta(0,1)-treelabeled plane treepattern avoidance permutationspermutations statistics

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• A Census of Planar Maps
• A bijective census of nonseparable planar maps
• Generalized permutation patterns and a classification of the Mahonian statistics
• Classification of bijections between 321- and 132-avoiding permutations
• Generalized pattern avoidance
• On the Enumeration of Rooted Non-Separable Planar Maps
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• Multi-static enumeration of two-stack sortable permutations
• A combinatorial proof of J. West's conjecture
• Permutations with forbidden subsequences and nonseparable planar maps
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Enumeration of Non-Separable Planar Maps
• Baxter permutations and plane bipolar orientations

Cited In (13)

• An involution on \(\beta (1,0)\)-trees
• Combinatorial generation via permutation languages. I: Fundamentals
• A combinatorial proof of J. West's conjecture
• On pattern avoiding indecomposable permutations
• The rise-contact involution on Tamari intervals
• Permutations with forbidden subsequences and nonseparable planar maps
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Enumeration of fixed points of an involution on \(\beta(1,0)\)-trees
• Refined Wilf-equivalences by Comtet statistics
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• A trinity of duality: non-separable planar maps, \(\beta(1,0)\)-trees and synchronized intervals
• Restricted non-separable planar maps and some pattern avoiding permutations
• Tree traversals and permutations

This page was built for publication: Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1012156)