A combinatorial proof of J. West's conjecture

DOI10.1016/S0012-365X(98)80005-8MaRDI QIDQ1584296zbMATH OpenOpenAlexWikidataFDO

Authors Serge Dulucq, Sophie Gire, Olivier Guibert

Publication date 2 November 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(98)80005-8

zbMATH Keywords

planar mapstwo-stack sortable permutationsWest's conjecture

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Combinatorics in computer science (68R05)

Recommendations

• Permutations with forbidden subsequences and nonseparable planar maps
• Restricted non-separable planar maps and some pattern avoiding permutations
• Enumeration of permutations with restricted subsequences
• 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)\)!)
• Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations

Cites work

• A Census of 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)\)!)
• Asymptotic values for degrees associated with strips of Young diagrams
• Enumeration of Non-Separable Planar Maps
• Forbidden subsequences
• Generating trees and forbidden subsequences
• Generating trees and the Catalan and Schröder numbers
• scientific article; zbMATH DE number 3489159 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Non-commutative rational power series and algebraic generating functions
• On the enumeration of planar maps
• On the Enumeration of Rooted Non-Separable Planar Maps
• Permutations with forbidden subsequences and nonseparable planar maps
• Planar Maps are Well Labeled Trees
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Restricted permutations
• Some combinatorial properties of Schubert polynomials
• Sorting twice through a stack
• Stack sortable permutations
• The number of Baxter permutations

Cited in

(34)

• Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
• 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)\)!)
• A bijective census of nonseparable planar maps
• Symmetry and unimodality in \(t\)-stack sortable permutations
• 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers
• Permutations with forbidden subsequences and nonseparable planar maps
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Stack words, standard tableaux and Baxter permutations
• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps
• Troupes, cumulants, and stack-sorting
• Polyurethane toggles
• Stack-sorting preimages of permutation classes
• Counting 3-stack-sortable permutations
• Preimages under the stack-sorting algorithm
• Restricted non-separable planar maps and some pattern avoiding permutations
• Finitely labeled generating trees and restricted permutations
• A geometric form for the extended patience sorting algorithm
• A combinatorial proof of a result of Gessel and Greene
• Fighting fish and two-stack sortable permutations
• Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
• Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Flip-sort and combinatorial aspects of pop-stack sorting
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• On linear transformations preserving the Pólya frequency property
• Combinatorial generation via permutation languages. I: Fundamentals
• Enumeration of permutations with restricted subsequences
• Sorting with networks of data structures
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
• Pop-stack sorting and its image: permutations with overlapping runs
• A direct bijection between two-stack sortable permutations and fighting fish (extended abstract)
• Combinatorics of rectangulations: old and new bijections
• A bijection between non-separable planar maps and fighting fish

This page was built for publication: A combinatorial proof of J. West's conjecture

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