Séminaire Lotharingien de Combinatoire, B27e (1991), 20
pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1992, 473/S-27, p.
5-24.]
Didier Arques, Isabelle Jacques and
Karine Orieux
Équations fonctionnelles liant la série génératrice des cartes planaires
à celle des mots de Dyck
Abstract.
For any graph with edges weighted by formal variables, we consider the
following "linear evolution" problem. For each n (time) and
for x and y
(vertices of the graph), H(n,x,y)
is, at time 0 the unity value on x, and at
time n+1 the sum of the H(n,x,z)
weighted by the variables associated
to the
edges (z,y) going in y.
There are two different forms of the unique solution of this problem,
leading to an identity closely related to the underlying graph. The
first form is
usual and comes from linear algebra. The second form, very different and
using continued fractions of Dyck, is obtained by a totally new
approach issued from evolution problems. A
particular case of this problem in the case of graph Z,
gives the well known
three terms recurrence.
An application in the combinatorics of maps is then proposed,
using as underlying graph the
infinite tree, associated to the family of rooted planar maps (well
labeled trees), weighted by appropriately chosen formal variables. We
then establish a set of functional relations for rooted planar
maps and well labeled trees, one of them links the generating series
of rooted planar maps with the
generating series of Dyck words.
The following version is available: