A bijection for triangulations of a polygon with interior points and multiple edges
Identifieur interne :
000737 ( PascalFrancis/Corpus );
précédent :
000736;
suivant :
000738
A bijection for triangulations of a polygon with interior points and multiple edges
Auteurs : Dominique Poulalhon ;
Gilles SchaefferSource :
-
Theoretical computer science [ 0304-3975 ] ; 2003.
RBID : Pascal:04-0048687
Descripteurs français
- Pascal (Inist)
- Théorie graphe,
Enumération,
Graphe planaire,
Arbre graphe,
Triangulation,
Décomposition,
Cycle,
Conception,
Carte,
Sphère,
Construction,
Arbre,
Polygone,
Bord,
Fonction génératrice,
Fonction quadratique,
Calcul,
Méthode,
Article,
Interprétation,
Décomposition bijective,
Formule Mullin.
English descriptors
- KwdEn :
- Article,
Bijective decomposition,
Calculation,
Construction,
Cycle,
Decomposition,
Design,
Edge,
Enumeration,
Generating function,
Graph theory,
Interpretation,
Maps,
Method,
Mullin formula,
Planar graph,
Polygon,
Quadratic function,
Sphere,
Tree,
Tree(graph),
Triangulation.
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 interpretation of Mullin's formula. The argument rests on the method of conjugacy classes 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.
Notice en format standard (ISO 2709)
Pour connaître la documentation sur le format Inist Standard.
| pA |
| A01 | 01 | 1 | | @0 0304-3975 |
|---|
| A02 | 01 | | | @0 TCSCDI |
|---|
| A03 | | 1 | | @0 Theor. comput. sci. |
|---|
| A05 | | | | @2 307 |
|---|
| A06 | | | | @2 2 |
|---|
| A08 | 01 | 1 | ENG | @1 A bijection for triangulations of a polygon with interior points and multiple edges |
|---|
| A09 | 01 | 1 | ENG | @1 Random generation of combinatorial objects and bijective combinatorics |
|---|
| A11 | 01 | 1 | | @1 POULALHON (Dominique) |
|---|
| A11 | 02 | 1 | | @1 SCHAEFFER (Gilles) |
|---|
| A12 | 01 | 1 | | @1 BARCUCCI (Elena) @9 ed. |
|---|
| A12 | 02 | 1 | | @1 DEL LUNGO (Alberto) @9 ed. |
|---|
| A14 | 01 | | | @1 LIX, École polytechnique @2 91128 Palaiseau @3 FRA @Z 1 aut. |
|---|
| A14 | 02 | | | @1 CNRS-LORIA, Campus Science, B.P. 239 @2 54506 Vandoeuvre @3 FRA @Z 2 aut. |
|---|
| A15 | 01 | | | @1 Dipartimento di Sistemi e Informatica, Università fi Firenze, Via Lombroso 6117 @2 Firenze @3 ITA @Z 1 aut. |
|---|
| A15 | 02 | | | @1 Dipartimento di Scienze Matematiche e Informatiche "Roberto Magari", Università di Siena, Via del Capitano 15 @2 Siena 53100 @3 ITA @Z 2 aut. |
|---|
| A20 | | | | @1 385-401 |
|---|
| A21 | | | | @1 2003 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A43 | 01 | | | @1 INIST @2 17243 @5 354000114434550100 |
|---|
| A44 | | | | @0 0000 @1 © 2004 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 16 ref. |
|---|
| A47 | 01 | 1 | | @0 04-0048687 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | 01 | 1 | | @0 Theoretical computer science |
|---|
| A66 | 01 | | | @0 NLD |
|---|
| C01 | 01 | | ENG | @0 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 interpretation of Mullin's formula. The argument rests on the method of conjugacy classes 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. |
|---|
| C02 | 01 | X | | @0 001A02B01C |
|---|
| C03 | 01 | X | FRE | @0 Théorie graphe @5 01 |
|---|
| C03 | 01 | X | ENG | @0 Graph theory @5 01 |
|---|
| C03 | 01 | X | SPA | @0 Teoría grafo @5 01 |
|---|
| C03 | 02 | X | FRE | @0 Enumération @5 02 |
|---|
| C03 | 02 | X | ENG | @0 Enumeration @5 02 |
|---|
| C03 | 02 | X | SPA | @0 Enumeración @5 02 |
|---|
| C03 | 03 | X | FRE | @0 Graphe planaire @5 03 |
|---|
| C03 | 03 | X | ENG | @0 Planar graph @5 03 |
|---|
| C03 | 03 | X | SPA | @0 Grafo planario @5 03 |
|---|
| C03 | 04 | X | FRE | @0 Arbre graphe @5 04 |
|---|
| C03 | 04 | X | ENG | @0 Tree(graph) @5 04 |
|---|
| C03 | 04 | X | SPA | @0 Arbol grafo @5 04 |
|---|
| C03 | 05 | X | FRE | @0 Triangulation @5 05 |
|---|
| C03 | 05 | X | ENG | @0 Triangulation @5 05 |
|---|
| C03 | 05 | X | SPA | @0 Triangulación @5 05 |
|---|
| C03 | 06 | X | FRE | @0 Décomposition @5 06 |
|---|
| C03 | 06 | X | ENG | @0 Decomposition @5 06 |
|---|
| C03 | 06 | X | SPA | @0 Descomposición @5 06 |
|---|
| C03 | 07 | X | FRE | @0 Cycle @5 17 |
|---|
| C03 | 07 | X | ENG | @0 Cycle @5 17 |
|---|
| C03 | 07 | X | SPA | @0 Ciclo @5 17 |
|---|
| C03 | 08 | X | FRE | @0 Conception @5 18 |
|---|
| C03 | 08 | X | ENG | @0 Design @5 18 |
|---|
| C03 | 08 | X | SPA | @0 Diseño @5 18 |
|---|
| C03 | 09 | X | FRE | @0 Carte @5 19 |
|---|
| C03 | 09 | X | ENG | @0 Maps @5 19 |
|---|
| C03 | 09 | X | SPA | @0 Mapa @5 19 |
|---|
| C03 | 10 | X | FRE | @0 Sphère @5 20 |
|---|
| C03 | 10 | X | ENG | @0 Sphere @5 20 |
|---|
| C03 | 10 | X | SPA | @0 Esfera @5 20 |
|---|
| C03 | 11 | X | FRE | @0 Construction @5 21 |
|---|
| C03 | 11 | X | ENG | @0 Construction @5 21 |
|---|
| C03 | 11 | X | SPA | @0 Construcción @5 21 |
|---|
| C03 | 12 | X | FRE | @0 Arbre @5 59 |
|---|
| C03 | 12 | X | ENG | @0 Tree @5 59 |
|---|
| C03 | 12 | X | SPA | @0 Arbol @5 59 |
|---|
| C03 | 13 | X | FRE | @0 Polygone @5 61 |
|---|
| C03 | 13 | X | ENG | @0 Polygon @5 61 |
|---|
| C03 | 13 | X | SPA | @0 Polígono @5 61 |
|---|
| C03 | 14 | X | FRE | @0 Bord @5 62 |
|---|
| C03 | 14 | X | ENG | @0 Edge @5 62 |
|---|
| C03 | 14 | X | SPA | @0 Borde @5 62 |
|---|
| C03 | 15 | X | FRE | @0 Fonction génératrice @5 63 |
|---|
| C03 | 15 | X | ENG | @0 Generating function @5 63 |
|---|
| C03 | 15 | X | SPA | @0 Función generatriz @5 63 |
|---|
| C03 | 16 | X | FRE | @0 Fonction quadratique @5 64 |
|---|
| C03 | 16 | X | ENG | @0 Quadratic function @5 64 |
|---|
| C03 | 16 | X | SPA | @0 Función cuadrática @5 64 |
|---|
| C03 | 17 | X | FRE | @0 Calcul @5 65 |
|---|
| C03 | 17 | X | ENG | @0 Calculation @5 65 |
|---|
| C03 | 17 | X | SPA | @0 Cálculo @5 65 |
|---|
| C03 | 18 | X | FRE | @0 Méthode @5 66 |
|---|
| C03 | 18 | X | ENG | @0 Method @5 66 |
|---|
| C03 | 18 | X | SPA | @0 Método @5 66 |
|---|
| C03 | 19 | X | FRE | @0 Article @5 67 |
|---|
| C03 | 19 | X | ENG | @0 Article @5 67 |
|---|
| C03 | 19 | X | SPA | @0 Artículo @5 67 |
|---|
| C03 | 20 | X | FRE | @0 Interprétation @5 68 |
|---|
| C03 | 20 | X | ENG | @0 Interpretation @5 68 |
|---|
| C03 | 20 | X | SPA | @0 Interpretación @5 68 |
|---|
| C03 | 21 | X | FRE | @0 Décomposition bijective @4 CD @5 96 |
|---|
| C03 | 21 | X | ENG | @0 Bijective decomposition @4 CD @5 96 |
|---|
| C03 | 22 | X | FRE | @0 Formule Mullin @4 CD @5 97 |
|---|
| C03 | 22 | X | ENG | @0 Mullin formula @4 CD @5 97 |
|---|
| N21 | | | | @1 033 |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 GASCom2001 @3 Siena ITA @4 2001-11-18 |
|---|
|
|---|
Format Inist (serveur)
| NO : | PASCAL 04-0048687 INIST |
|---|
| ET : | A bijection for triangulations of a polygon with interior points and multiple edges |
|---|
| AU : | POULALHON (Dominique); SCHAEFFER (Gilles); BARCUCCI (Elena); DEL LUNGO (Alberto) |
|---|
| AF : | LIX, École polytechnique/91128 Palaiseau/France (1 aut.); CNRS-LORIA, Campus Science, B.P. 239/54506 Vandoeuvre/France (2 aut.); Dipartimento di Sistemi e Informatica, Università fi Firenze, Via Lombroso 6117/Firenze/Italie (1 aut.); Dipartimento di Scienze Matematiche e Informatiche "Roberto Magari", Università di Siena, Via del Capitano 15/Siena 53100/Italie (2 aut.) |
|---|
| DT : | Publication en série; Congrès; Niveau analytique |
|---|
| SO : | Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2003; Vol. 307; No. 2; Pp. 385-401; Bibl. 16 ref. |
|---|
| LA : | Anglais |
|---|
| EA : | 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 interpretation of Mullin's formula. The argument rests on the method of conjugacy classes 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. |
|---|
| CC : | 001A02B01C |
|---|
| FD : | Théorie graphe; Enumération; Graphe planaire; Arbre graphe; Triangulation; Décomposition; Cycle; Conception; Carte; Sphère; Construction; Arbre; Polygone; Bord; Fonction génératrice; Fonction quadratique; Calcul; Méthode; Article; Interprétation; Décomposition bijective; Formule Mullin |
|---|
| ED : | Graph theory; Enumeration; Planar graph; Tree(graph); Triangulation; Decomposition; Cycle; Design; Maps; Sphere; Construction; Tree; Polygon; Edge; Generating function; Quadratic function; Calculation; Method; Article; Interpretation; Bijective decomposition; Mullin formula |
|---|
| SD : | Teoría grafo; Enumeración; Grafo planario; Arbol grafo; Triangulación; Descomposición; Ciclo; Diseño; Mapa; Esfera; Construcción; Arbol; Polígono; Borde; Función generatriz; Función cuadrática; Cálculo; Método; Artículo; Interpretación |
|---|
| LO : | INIST-17243.354000114434550100 |
|---|
| ID : | 04-0048687 |
|---|
Links to Exploration step
Pascal:04-0048687
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">A bijection for triangulations of a polygon with interior points and multiple edges</title>
<author><name sortKey="Poulalhon, Dominique" sort="Poulalhon, Dominique" uniqKey="Poulalhon D" first="Dominique" last="Poulalhon">Dominique Poulalhon</name>
<affiliation><inist:fA14 i1="01"><s1>LIX, École polytechnique</s1>
<s2>91128 Palaiseau</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Schaeffer, Gilles" sort="Schaeffer, Gilles" uniqKey="Schaeffer G" first="Gilles" last="Schaeffer">Gilles Schaeffer</name>
<affiliation><inist:fA14 i1="02"><s1>CNRS-LORIA, Campus Science, B.P. 239</s1>
<s2>54506 Vandoeuvre</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">04-0048687</idno>
<date when="2003">2003</date>
<idno type="stanalyst">PASCAL 04-0048687 INIST</idno>
<idno type="RBID">Pascal:04-0048687</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000737</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">A bijection for triangulations of a polygon with interior points and multiple edges</title>
<author><name sortKey="Poulalhon, Dominique" sort="Poulalhon, Dominique" uniqKey="Poulalhon D" first="Dominique" last="Poulalhon">Dominique Poulalhon</name>
<affiliation><inist:fA14 i1="01"><s1>LIX, École polytechnique</s1>
<s2>91128 Palaiseau</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Schaeffer, Gilles" sort="Schaeffer, Gilles" uniqKey="Schaeffer G" first="Gilles" last="Schaeffer">Gilles Schaeffer</name>
<affiliation><inist:fA14 i1="02"><s1>CNRS-LORIA, Campus Science, B.P. 239</s1>
<s2>54506 Vandoeuvre</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><series><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
<imprint><date when="2003">2003</date>
</imprint><seriesStmt><title level="j" type="main">Theoretical computer science</title>
<title level="j" type="abbreviated">Theor. comput. sci.</title>
<idno type="ISSN">0304-3975</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Article</term>
<term>Bijective decomposition</term>
<term>Calculation</term>
<term>Construction</term>
<term>Cycle</term>
<term>Decomposition</term>
<term>Design</term>
<term>Edge</term>
<term>Enumeration</term>
<term>Generating function</term>
<term>Graph theory</term>
<term>Interpretation</term>
<term>Maps</term>
<term>Method</term>
<term>Mullin formula</term>
<term>Planar graph</term>
<term>Polygon</term>
<term>Quadratic function</term>
<term>Sphere</term>
<term>Tree</term>
<term>Tree(graph)</term>
<term>Triangulation</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Théorie graphe</term>
<term>Enumération</term>
<term>Graphe planaire</term>
<term>Arbre graphe</term>
<term>Triangulation</term>
<term>Décomposition</term>
<term>Cycle</term>
<term>Conception</term>
<term>Carte</term>
<term>Sphère</term>
<term>Construction</term>
<term>Arbre</term>
<term>Polygone</term>
<term>Bord</term>
<term>Fonction génératrice</term>
<term>Fonction quadratique</term>
<term>Calcul</term>
<term>Méthode</term>
<term>Article</term>
<term>Interprétation</term>
<term>Décomposition bijective</term>
<term>Formule Mullin</term>
</keywords><front><div type="abstract" xml:lang="en">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 interpretation of Mullin's formula. The argument rests on the method of conjugacy classes 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.</div>
</front><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0304-3975</s0>
</fA01><fA02 i1="01"><s0>TCSCDI</s0>
</fA02><fA03 i2="1"><s0>Theor. comput. sci.</s0>
</fA03><fA05><s2>307</s2>
</fA05><fA08 i1="01" i2="1" l="ENG"><s1>A bijection for triangulations of a polygon with interior points and multiple edges</s1>
</fA08><fA09 i1="01" i2="1" l="ENG"><s1>Random generation of combinatorial objects and bijective combinatorics</s1>
</fA09><fA11 i1="01" i2="1"><s1>POULALHON (Dominique)</s1>
</fA11><fA11 i1="02" i2="1"><s1>SCHAEFFER (Gilles)</s1>
</fA11><fA12 i1="01" i2="1"><s1>BARCUCCI (Elena)</s1>
<s9>ed.</s9>
</fA12><fA12 i1="02" i2="1"><s1>DEL LUNGO (Alberto)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>LIX, École polytechnique</s1>
<s2>91128 Palaiseau</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="02"><s1>CNRS-LORIA, Campus Science, B.P. 239</s1>
<s2>54506 Vandoeuvre</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14><fA15 i1="01"><s1>Dipartimento di Sistemi e Informatica, Università fi Firenze, Via Lombroso 6117</s1>
<s2>Firenze</s2>
<s3>ITA</s3>
<sZ>1 aut.</sZ>
</fA15><fA15 i1="02"><s1>Dipartimento di Scienze Matematiche e Informatiche "Roberto Magari", Università di Siena, Via del Capitano 15</s1>
<s2>Siena 53100</s2>
<s3>ITA</s3>
<sZ>2 aut.</sZ>
</fA15><fA20><s1>385-401</s1>
</fA20><fA21><s1>2003</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA43 i1="01"><s1>INIST</s1>
<s2>17243</s2>
<s5>354000114434550100</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 2004 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>16 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>04-0048687</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><fA64 i1="01" i2="1"><s0>Theoretical computer science</s0>
</fA64><fA66 i1="01"><s0>NLD</s0>
</fA66><fC01 i1="01" l="ENG"><s0>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 interpretation of Mullin's formula. The argument rests on the method of conjugacy classes 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.</s0>
</fC01><fC02 i1="01" i2="X"><s0>001A02B01C</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Théorie graphe</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Graph theory</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Teoría grafo</s0>
<s5>01</s5>
</fC03><fC03 i1="02" i2="X" l="FRE"><s0>Enumération</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="X" l="ENG"><s0>Enumeration</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="X" l="SPA"><s0>Enumeración</s0>
<s5>02</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Graphe planaire</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>Planar graph</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Grafo planario</s0>
<s5>03</s5>
</fC03><fC03 i1="04" i2="X" l="FRE"><s0>Arbre graphe</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="X" l="ENG"><s0>Tree(graph)</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="X" l="SPA"><s0>Arbol grafo</s0>
<s5>04</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Triangulation</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Triangulation</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Triangulación</s0>
<s5>05</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Décomposition</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>Decomposition</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="SPA"><s0>Descomposición</s0>
<s5>06</s5>
</fC03><fC03 i1="07" i2="X" l="FRE"><s0>Cycle</s0>
<s5>17</s5>
</fC03><fC03 i1="07" i2="X" l="ENG"><s0>Cycle</s0>
<s5>17</s5>
</fC03><fC03 i1="07" i2="X" l="SPA"><s0>Ciclo</s0>
<s5>17</s5>
</fC03><fC03 i1="08" i2="X" l="FRE"><s0>Conception</s0>
<s5>18</s5>
</fC03><fC03 i1="08" i2="X" l="ENG"><s0>Design</s0>
<s5>18</s5>
</fC03><fC03 i1="08" i2="X" l="SPA"><s0>Diseño</s0>
<s5>18</s5>
</fC03><fC03 i1="09" i2="X" l="FRE"><s0>Carte</s0>
<s5>19</s5>
</fC03><fC03 i1="09" i2="X" l="ENG"><s0>Maps</s0>
<s5>19</s5>
</fC03><fC03 i1="09" i2="X" l="SPA"><s0>Mapa</s0>
<s5>19</s5>
</fC03><fC03 i1="10" i2="X" l="FRE"><s0>Sphère</s0>
<s5>20</s5>
</fC03><fC03 i1="10" i2="X" l="ENG"><s0>Sphere</s0>
<s5>20</s5>
</fC03><fC03 i1="10" i2="X" l="SPA"><s0>Esfera</s0>
<s5>20</s5>
</fC03><fC03 i1="11" i2="X" l="FRE"><s0>Construction</s0>
<s5>21</s5>
</fC03><fC03 i1="11" i2="X" l="ENG"><s0>Construction</s0>
<s5>21</s5>
</fC03><fC03 i1="11" i2="X" l="SPA"><s0>Construcción</s0>
<s5>21</s5>
</fC03><fC03 i1="12" i2="X" l="FRE"><s0>Arbre</s0>
<s5>59</s5>
</fC03><fC03 i1="12" i2="X" l="ENG"><s0>Tree</s0>
<s5>59</s5>
</fC03><fC03 i1="12" i2="X" l="SPA"><s0>Arbol</s0>
<s5>59</s5>
</fC03><fC03 i1="13" i2="X" l="FRE"><s0>Polygone</s0>
<s5>61</s5>
</fC03><fC03 i1="13" i2="X" l="ENG"><s0>Polygon</s0>
<s5>61</s5>
</fC03><fC03 i1="13" i2="X" l="SPA"><s0>Polígono</s0>
<s5>61</s5>
</fC03><fC03 i1="14" i2="X" l="FRE"><s0>Bord</s0>
<s5>62</s5>
</fC03><fC03 i1="14" i2="X" l="ENG"><s0>Edge</s0>
<s5>62</s5>
</fC03><fC03 i1="14" i2="X" l="SPA"><s0>Borde</s0>
<s5>62</s5>
</fC03><fC03 i1="15" i2="X" l="FRE"><s0>Fonction génératrice</s0>
<s5>63</s5>
</fC03><fC03 i1="15" i2="X" l="ENG"><s0>Generating function</s0>
<s5>63</s5>
</fC03><fC03 i1="15" i2="X" l="SPA"><s0>Función generatriz</s0>
<s5>63</s5>
</fC03><fC03 i1="16" i2="X" l="FRE"><s0>Fonction quadratique</s0>
<s5>64</s5>
</fC03><fC03 i1="16" i2="X" l="ENG"><s0>Quadratic function</s0>
<s5>64</s5>
</fC03><fC03 i1="16" i2="X" l="SPA"><s0>Función cuadrática</s0>
<s5>64</s5>
</fC03><fC03 i1="17" i2="X" l="FRE"><s0>Calcul</s0>
<s5>65</s5>
</fC03><fC03 i1="17" i2="X" l="ENG"><s0>Calculation</s0>
<s5>65</s5>
</fC03><fC03 i1="17" i2="X" l="SPA"><s0>Cálculo</s0>
<s5>65</s5>
</fC03><fC03 i1="18" i2="X" l="FRE"><s0>Méthode</s0>
<s5>66</s5>
</fC03><fC03 i1="18" i2="X" l="ENG"><s0>Method</s0>
<s5>66</s5>
</fC03><fC03 i1="18" i2="X" l="SPA"><s0>Método</s0>
<s5>66</s5>
</fC03><fC03 i1="19" i2="X" l="FRE"><s0>Article</s0>
<s5>67</s5>
</fC03><fC03 i1="19" i2="X" l="ENG"><s0>Article</s0>
<s5>67</s5>
</fC03><fC03 i1="19" i2="X" l="SPA"><s0>Artículo</s0>
<s5>67</s5>
</fC03><fC03 i1="20" i2="X" l="FRE"><s0>Interprétation</s0>
<s5>68</s5>
</fC03><fC03 i1="20" i2="X" l="ENG"><s0>Interpretation</s0>
<s5>68</s5>
</fC03><fC03 i1="20" i2="X" l="SPA"><s0>Interpretación</s0>
<s5>68</s5>
</fC03><fC03 i1="21" i2="X" l="FRE"><s0>Décomposition bijective</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fC03 i1="21" i2="X" l="ENG"><s0>Bijective decomposition</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fC03 i1="22" i2="X" l="FRE"><s0>Formule Mullin</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03><fC03 i1="22" i2="X" l="ENG"><s0>Mullin formula</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03><fN21><s1>033</s1>
</fN21><pR><fA30 i1="01" i2="1" l="ENG"><s1>GASCom2001</s1>
<s3>Siena ITA</s3>
<s4>2001-11-18</s4>
</fA30><server><NO>PASCAL 04-0048687 INIST</NO>
<ET>A bijection for triangulations of a polygon with interior points and multiple edges</ET>
<AU>POULALHON (Dominique); SCHAEFFER (Gilles); BARCUCCI (Elena); DEL LUNGO (Alberto)</AU>
<AF>LIX, École polytechnique/91128 Palaiseau/France (1 aut.); CNRS-LORIA, Campus Science, B.P. 239/54506 Vandoeuvre/France (2 aut.); Dipartimento di Sistemi e Informatica, Università fi Firenze, Via Lombroso 6117/Firenze/Italie (1 aut.); Dipartimento di Scienze Matematiche e Informatiche "Roberto Magari", Università di Siena, Via del Capitano 15/Siena 53100/Italie (2 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Theoretical computer science; ISSN 0304-3975; Coden TCSCDI; Pays-Bas; Da. 2003; Vol. 307; No. 2; Pp. 385-401; Bibl. 16 ref.</SO>
<LA>Anglais</LA>
<EA>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 interpretation of Mullin's formula. The argument rests on the method of conjugacy classes 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.</EA>
<CC>001A02B01C</CC>
<FD>Théorie graphe; Enumération; Graphe planaire; Arbre graphe; Triangulation; Décomposition; Cycle; Conception; Carte; Sphère; Construction; Arbre; Polygone; Bord; Fonction génératrice; Fonction quadratique; Calcul; Méthode; Article; Interprétation; Décomposition bijective; Formule Mullin</FD>
<ED>Graph theory; Enumeration; Planar graph; Tree(graph); Triangulation; Decomposition; Cycle; Design; Maps; Sphere; Construction; Tree; Polygon; Edge; Generating function; Quadratic function; Calculation; Method; Article; Interpretation; Bijective decomposition; Mullin formula</ED>
<SD>Teoría grafo; Enumeración; Grafo planario; Arbol grafo; Triangulación; Descomposición; Ciclo; Diseño; Mapa; Esfera; Construcción; Arbol; Polígono; Borde; Función generatriz; Función cuadrática; Cálculo; Método; Artículo; Interpretación</SD>
<LO>INIST-17243.354000114434550100</LO>
<ID>04-0048687</ID>
</server>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000737 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000737 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Corpus
|type= RBID
|clé= Pascal:04-0048687
|texte= A bijection for triangulations of a polygon with interior points and multiple edges
}}
| This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022 |  |
