Permutations with forbidden subsequences and nonseparable planar maps
type: Item
instance of: scholarly article
title: Permutations with forbidden subsequences and nonseparable planar maps
zbMATH Open document ID: 0853.05047
DOI: 10.1016/0012-365X(95)00130-O
author: Julian West
author: Serge Dulucq
author: Sophie Gire
published in: Discrete Mathematics
publication date: 1996-12-09T00:00:00Z
review text: 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 …
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05-04
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 897598
zbMATH Keywords: permutation
zbMATH Keywords: barred permutation
zbMATH Keywords: stack
zbMATH Keywords: forbidden subsequences
zbMATH Keywords: planar maps
zbMATH Keywords: West's conjecture
zbMATH Keywords: generating tree
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Enumeration of Non-Separable Planar Maps
cites work: On the Enumeration of Rooted Non-Separable Planar Maps
cites work: Q4071773
cites work: Planar Maps are Well Labeled Trees
cites work: A combinatorial proof of J. West's conjecture
cites work: Q3738554
cites work: Q4057549
cites work: Counting rooted maps by genus. I
cites work: Counting rooted maps by genus. III: Nonseparable maps
cites work: The enumeration of Hamiltonian polygons in triangular maps
cites work: Restricted permutations
cites work: Forbidden subsequences
cites work: A Census of Planar Maps
cites work: Sorting twice through a stack
cites work: 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)\)!)
Recommended article: A combinatorial proof of J. West's conjecture
Recommended article: Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
Recommended article: Enumeration of permutations with restricted subsequences
Recommended article: Restricted non-separable planar maps and some pattern avoiding permutations
Recommended article: Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
Recommended article: A simplicial complex of 2-stack sortable permutations
Recommended article: 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)\)!)
Recommended article: Counting 3-stack-sortable permutations
Recommended article: Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps
Recommended article: Q3344015
description: scientific article; zbMATH DE number 897598