A combinatorial proof of J. Westʹs conjecture Original Research Article

We give what we believe to be the first combinatorial proof of J. Westʹs conjecture that is to say we show that two-stack sortable permutations are in correspondence with rooted nonseparable planar maps. The generating tree of a set of permutations with forbidden subsequences and its characterization by a rewriting system are used to obtain this correspondence. Other results on the number of two-stack sortable permutations with given classical parameters are presented.