Une relation fonctionnelle nouvelle sur les cartes planaires pointées. (French) Zbl 0571.05001

Arques, Didier

J. Comb. Theory, Ser. B 39, 27-42 (1985).

A new functional relation, the unique solution of which is the generating function of rooted planar maps, is shown. This new relation in conjunction with the well-known relation established by Tutte, enables the easy derivation of a system of parametric equations for the desired generating function. As a consequence, one infers a closed formula counting the rooted planar maps as a function of their number of vertices and faces. The geometrical nature of the decomposition used in the derivation of this functional relation leads to the definition of a natural notion of the inner map of a rooted planar map. Some questions related to this notion are treated.

Reviewer: Ph.Vincke

MSC:

05A15	Exact enumeration problems, generating functions
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

functional relation; generating function; rooted planar maps; inner map

References:

[1]	Cori, R, Un code pour LES graphes planaires et ses applications, () · Zbl 0313.05115
[2]	Cori, R; Richard, J, Enumération des graphes planaires à l’aide des séries formelles en variables non commutatives, Discrete math., 2, 115-162, (1972) · Zbl 0247.05140
[3]	Cori, R; Vauquelin, B, Planar maps are well labeled trees, Canad. J. math., 33, No. 5, 1023-1042, (1981) · Zbl 0415.05020
[4]	Goulden, I.P; Jackson, D.M, Combinatorial enumeration, () · Zbl 0687.05003
[5]	Lehman, A.B, A bijective census of rooted planar maps, (), unpublished
[6]	Tutte, W.T, A census of slicings, Canad. J. math., 14, 708-722, (1962) · Zbl 0111.35202
[7]	Tutte, W.T, A census of planar maps, Canad. J. math., 15, 249-271, (1963) · Zbl 0115.17305
[8]	Tutte, W.T, On the enumeration of planar maps, Bull. amer. math. soc., 74, 64-74, (1968) · Zbl 0157.31101