Permutations with forbidden subsequences and nonseparable planar maps (Q1917517)

A permutation \(\pi\) in \(S_n\), the symmetric group on \(\{1,2, \dots, n\}\), contains a subsequence of type \(\tau \in S_k\) iff there exist \(1 \leq i_{\tau 1} < i_{\tau 2} < \cdots < i_{\tau k} \leq n\) such that \(\pi i_1 < \pi i_2 < \cdots < \pi i_k\); \(S_n (\tau_1, \tau_2)\) denotes the set of permutations in \(S_n\) which contain neither of \(\tau_1, \tau_2\). A permutation \(\tau \in S_k\) is barred if one element fixed by \(\tau\) is distinguished. In this paper a permutation \(\pi \in S_n\) is denoted by the string \(\pi (1) \pi (2) \dots \pi (n)\); a barred permutation \(\tau \in S_k\) is represented by a string with a bar above the distinguished fixed point. Author J. West, in his M.I.T. Ph.D. thesis, and in [Sorting twice through a stack, Theor. Comput. Sci. 117, No. 1-2, 303-313 (1993; Zbl 0797.68041)] has defined a property of \(k\)-stack-sortability in terms of transformability into the identity permutation through \(k\) iterations of a certain recursively defined stack operation. He has characterized the 2-stack-sortable permutations in \(S_n\) in terms of forbidden subsequences as \(S_n (2341,3 \overline {5}241)\), and has conjectured that their numbers is \({2(3n)! \over (n + 1)! (2n + 1)!}\), known to be the number of rooted non-separable planar maps on \(n + 1\) edges (cf. \textit{W. T. Tutte} [A census of planar maps, Can. J. Math. 15, 249-271 (1963; Zbl 0115.17305)], \textit{W. T. Tutte} and the reviewer [On the enumeration of rooted non-separable planar maps, ibid. 16, 572-577 (1964; Zbl 0119.38804)]). A computer-aided ``proof'' of this conjecture has been published by \textit{D. Zeilberger} [Discrete Math. 102, No. 1, 85-93 (1992; Zbl 0754.05006)]. The present work begins a combinatorial proof of West's conjecture. From the authors' abstract and introduction: We obtain a generating tree of non-separable planar rooted maps and show that this tree is the generating tree of a family of permutations. The distribution of these permutations is then obtained. (...) The proof is completed in [\textit{S. Dulucq}, \textit{S. Gire} and \textit{O. Guibert}, A combinatorical proof of J. West's conjecture, Discrete Mathematics, to appear]; the remaining steps in the proof are sketched in Section 3 of this paper.