๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Bijective Census of Nonseparable Planar Maps

โœ Scribed by Benjamin Jacquard; Gilles Schaeffer

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
703 KB
Volume
83
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

โœฆ Synopsis

Bijections are obtained between nonseparable planar maps and two different kinds of trees: description trees and skew ternary trees. A combinatorial relation between the latter and ternary trees allows bijective enumeration and random generation of nonseparable planar maps. The involved bijections take account of the usual combinatorial parameters and give a bijective proof of formulae established by Brown and Tutte. These results, combined with a bijection due to Goulden and West, give a purely combinatorial enumeration of two-stack-sortable permutations.

๐Ÿ“œ SIMILAR VOLUMES

Raney Paths and a Combinatorial Relation
Raney Paths and a Combinatorial Relationship between Rooted Nonseparable Planar Maps and Two-Stack-Sortable Permutations
โœ I.P. Goulden; J. West ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 673 KB

An encoding of the set of two-stack-sortable permutations (TSS) in terms of lattice paths and ordered lists of strings is obtained. These lattice paths are called Raney paths. The encoding yields combinatorial decompositions for two complementary subsets of TSS, which are the analogues of previously

The number of loopless planar maps
The number of loopless planar maps
โœ Edward A. Bender; Nicholas C. Wormald ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 124 KB

We derive a simple formula for the number of rooted loopless planar maps with a given number of edges and a given valency of the root vertex.