×

Permutations with forbidden subsequences and nonseparable planar maps. (English) Zbl 0853.05047

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. W. T. Tutte [A census of planar maps, Can. J. Math. 15, 249-271 (1963; Zbl 0115.17305)], 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 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 [S. Dulucq, S. Gire and 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.

MSC:

05C30 Enumeration in graph theory
05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
05-04 Software, source code, etc. for problems pertaining to combinatorics
05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
68P10 Searching and sorting
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brown, W. G., Enumeration of nonseparable planar maps, Can. J. Math., 15, 526-545 (1963) · Zbl 0115.40901
[2] Brown, W. G.; Tutte, W. T., On the enumeration of rooted nonseparable planar maps, Can. J. Math., 16, 572-577 (1964) · Zbl 0119.38804
[3] Cori, R., Un code pour les graphes planaires et ses applications, Astérisque, 27 (1975), Soc. Math. de France · Zbl 0313.05115
[4] Cori, R.; Vauquelin, B., Planar maps are well labeled trees, Can. J. Math., 33, 1023-1042 (1981) · Zbl 0415.05020
[5] S. Dulucq, S. Gire and O. Guibert, A combinatorial proof of J. West’s conjecture, Discrete Math., to appear.; S. Dulucq, S. Gire and O. Guibert, A combinatorial proof of J. West’s conjecture, Discrete Math., to appear. · Zbl 0957.05007
[6] Flajolet, P., The evolution of two stacks is bounded space and random walks in a triangle, (Gruska, J.; Rovan, B.; Wiedermann, J., MFCS’86. MFCS’86, Lecture Notes in Mathematics, vol. 233 (1986), Springer: Springer Berlin) · Zbl 0602.68029
[7] Knuth, D. E., (The art of computer programming, Vol. 1 (1973), Addison-Wesley: Addison-Wesley Reading), 238-239
[8] Kreweras, G., Sur les éventails de segments, Cahiers BURO, Paris, 15, 1-41 (1970)
[9] Lehman, A. B.; Walsh, T. S., Counting rooted maps by genus I and II, J. Combin. Theory B, 13, 192-218 (1972) · Zbl 0228.05108
[10] Lehman, A. B.; Walsh, T. S., Counting rooted maps by genus III: nonseparable maps, J. Combin. Theory B, 18, 222-259 (1975) · Zbl 0299.05110
[11] Mullin, R. C., The enumeration of Hamiltonian polygons in triangular maps, Pacific J. Math., 16, 139-145 (1966) · Zbl 0137.43001
[12] Simion, R.; Schmidt, F., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.05002
[13] Stankova, Z., Forbidden subsequences, Discrete Math., 132, 291-316 (1994) · Zbl 0810.05011
[14] Tutte, W. T., A census of plnar maps, Can. J. Math., 15, 249-271 (1963) · Zbl 0115.17305
[15] Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc., 74, 249-271 (1968) · Zbl 0115.17305
[16] West, J., Permutations with restricted subsequences and stack-sortable permutations, (Ph.D. thesis (1990), M.I.T)
[17] West, J., Sorting twice through a stack, (Proc. of 3rd Conf. on Formal power series and algebraic combinatorics. Proc. of 3rd Conf. on Formal power series and algebraic combinatorics, Bordeaux 1991. Proc. of 3rd Conf. on Formal power series and algebraic combinatorics. Proc. of 3rd Conf. on Formal power series and algebraic combinatorics, Bordeaux 1991, Theoret. Comput. Sci., 117 (1993)), 303-313 · Zbl 0797.68041
[18] Zeilberger, D., A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/\(((n + 1)\)!\((2n + 1)\)!), Discrete Math., 102, 85-93 (1992) · Zbl 0754.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.