Indecomposable permutations, hypermaps and labeled Dyck paths

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:116

Article

Cori, Robert

关键词: Combinatorial maps;    Permutations;    Dyck paths;    Bijective proofs;    Enumeration;    Stirling numbers;   

DOI  :  10.1016/j.jcta.2009.02.008

来源: Elsevier

【 摘 要 】

Hypermaps were introduced as an algebraic tool for the representation of embeddings of graphs on an orientable surface. Recently a bijection was given between hypermaps and indecomposable permutations; this sheds new light on the subject by connecting a hypermap to a simpler object. In this paper, a bijection between indecomposable permutations and labeled Dyck paths is proposed, from which a few enumerative results concerning hypermaps and maps follow. We obtain for instance an inductive formula for the number of hypermaps with n darts, p vertices and q hyperedges: the latter is also the number of indecomposable permutations of S. with p cycles and q left-to-right maxima. The distribution of these parameters among all permutations is also considered. (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free