Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations (Q1924222): Difference between revisions

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 conjecture, Discrete Math., to appear]. ``The encoding'' mentioned above ``yields combinatorial decompositions for two complementary subsets of \({\mathcal T}SS\), which are the analogues of previously known decompositions'' due to the reviewer [Enumeration of non-separable planar maps, Can. J. Math. 15, 526-545 (1963; Zbl 0115.40901)], refining a result of Tutte's census cited above, ``for the set of nonseparable rooted planar maps \(({\mathcal N}S)\). This provides a combinatorial relationship between \({\mathcal T}SS\) and \({\mathcal N}S\), and hence a bijection is determined between these sets that is different, simpler, and more refined than the previously known bijections.'' (Quotations are from the authors' abstract).