RANEY PATHS AND A COMBINATORIAL RELATIONSHIP BETWEEN ROOTED NONSEPARABLE PLANAR MAPS AND 2-STACK-SORTABLE PERMUTATIONS

An encoding of the set of two-stack-sortable permutations (TJJ) in ter ms of lattice paths and ordered lists of strings is obtained. These la ttice paths are called Raney paths. The encoding yields combinatorial decompositions for two complementary subsets of TJJ. which are the ana logues of previously known decompositions for the set of nonseparable rooted planar maps (NJ). This provides a combinatorial relationship be tween TJJ and NJ and, hence, a bijection is determined between these s ets that is different, simpler, and more refined than the previously k nown bijection. (C) 1996 Academic Press, Inc.