Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
type: Item
instance of: scholarly article
title: Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
zbMATH Open document ID: 0864.05044
author: Yanyan Li
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-11-24T00:00:00Z
review text: A permutation \(\pi\) of the set of strings \(\omega\) of distinct characters from the alphabet of positive integers not exceeding a maximum of \(n\), which is attained, is defined recursively by \(\pi(\varepsilon)=\varepsilon\); and, when \(\omega=\tau_1n\tau_2\) (where \(\tau_1\) and \(\tau_2\) are substrings over the alphabet \(\{1,2,\dots,n-1\}\), \(\pi(\omega)=\pi(\tau_1)\pi(\tau_2)n\). A string \(\sigma\) of length \(n\) in the symbols \(1,2,\dots,n\) with repetitions is two-stack-sortable if \(\pi^2(\sigma)\) is the string \(12\dots n\). ``An encoding of the set of two-stack-sortable permutations \(({\mathcal T}SS)\) in terms of lattice paths and ordered lists of strings is obtained. These lattice paths are called Raney paths'' because this is the level-free subset of the set of paths used by \textit{G. N. Raney} [Functional composition patterns and power series reversion, Trans. Am. Math. Soc. 94, 441-451 (1960; Zbl 0131.01402)]. The second author, in his 1990 M.I.T. Ph.D. thesis, conjectured that the number of two-stack-sortable strings of length \(n\) is \({2\over(n+1)(2n+1)}{3n\choose n}\); observing that this is the number of rooted planar non-separable maps with \(n+1\) edges, as determined by \textit{W. T. Tutte} [A census of planar maps, Can. J. Math. 15, 249-271 (1963; Zbl 0115.17305)], he proposed that a proof might be found by exploiting a bijection between non-separable maps and strings. A computer-assisted ``proof'' of his conjecture, using other methods, was found by \textit{D. Zeilberger} [Discrete Math. 102, No. 1, 85-93 (1992; Zbl 0754.05006)]. A combinatorial proof of the conjecture is being published in a pair of papers, the first by \textit{S. Dulucq}, \textit{S. Gire} and the second author [Permutations with forbidden subsequences and nonseparable planar maps, Discrete Math. 153, No. 1-3, 85-103 (1996; Zbl 0853.05047)], and the second by \textit{S. Dulucq}, \textit{S. Gire} and \textit{O. Guibert} [A combinatorial proof of J. West's conje…
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05-04
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 934978
zbMATH Keywords: permutation
zbMATH Keywords: lattice paths
zbMATH Keywords: Raney paths
zbMATH Keywords: two-stack-sortable strings
zbMATH Keywords: non-separable maps
reviewed by: William G. Brown
MaRDI profile type: Publication
OpenAlex ID: W2032192467
DOI: 10.1006/JCTA.1996.0074
Recommended article: A combinatorial proof of J. West's conjecture
Recommended article: Permutations with forbidden subsequences and nonseparable planar maps
Recommended article: Multi-static enumeration of two-stack sortable permutations
Recommended article: Enumeration of permutations with restricted subsequences
Recommended article: Restricted non-separable planar maps and some pattern avoiding permutations
Recommended article: 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)\)!)
Recommended article: Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
Recommended article: Sorting with two ordered stacks in series.
Recommended article: A simplicial complex of 2-stack sortable permutations
Recommended article: Q3344015
description: scientific article; zbMATH DE number 934978