# A bijection for loopless triangulations of a polygon with interior points

2 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Loopless triangulations of a polygon with $k$ vertices in $k+2n$ triangles (with interior points and possibly multiple edges) were enumerated by Mullin in 1965, using generating functions and calculations with the quadratic method. In this article we propose a simple bijective construction of Mullin's formula. The argument rests on \emph{conjugation of trees}, a variation of the cycle lemma designed for planar maps. In the much easier case of loopless triangulations of the sphere ($k=3$), we recover and prove correct an unpublished construction of the second author.
Mots-clés :
Type de document :
Communication dans un congrès
Foda, O. and Guttmann, T. International Conference on Formal Power Series and Algebraic Combinatorics - FPSAC'02, Jul 2002, Melbourne, Australie, Actes locaux de l'universite de Melbourne, 12 p, 2002
Domaine :
Liste complète des métadonnées

https://hal.inria.fr/inria-00100860
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:52:29
Dernière modification le : jeudi 10 mai 2018 - 02:06:23

### Identifiants

• HAL Id : inria-00100860, version 1

### Citation

Dominique Poulalhon, Gilles Schaeffer. A bijection for loopless triangulations of a polygon with interior points. Foda, O. and Guttmann, T. International Conference on Formal Power Series and Algebraic Combinatorics - FPSAC'02, Jul 2002, Melbourne, Australie, Actes locaux de l'universite de Melbourne, 12 p, 2002. 〈inria-00100860〉

### Métriques

Consultations de la notice