Équations fonctionnelles liant la série génératrice des cartes planaires à celle des mots de Dyck

Didier Arques ; Isabelle Jacques ; Karine Orieux

Séminaire lotharingien de combinatoire, Tome 27 (1991)

Résumé

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.