Grammaires de William Chen et dérivations dans les arbres

et arborescences

Dominique DUMONT

Département de Mathématiques

Université Louis Pasteur,

7 rue René Descartes, 67084 Strasbourg

1.Introduction

Etant donné un alphabet fini ou infini X = {x_{1}, x_{2}, x_{3}, …}, et l’algèbre C[X] des polynômes commutatifs dans les lettres x_{i}, une grammaire est un ensemble de règles de réécritures des lettres de l’alphabet (substitution rules), c’est- à-dire une application G de X dans C[X] :

G = {x_{1} → G(x_{1}), x_{2} → G(x_{2}), x_{3} → G(x_{3}), …}

Notons que le plus souvent les G(x_{i}) sont des monômes, mais nous donnerons des exemples où ce sont des polynômes. (William Chen [Ch] se place dans un contexte plus général où les G(x_{i}) sont ce qu’il appelle des “formal functions”, qui peuvent être des séries formelles).

A une grammaire G on associe une dérivation D_{G}, notée plus simplement D, qui coïncide avec G sur les lettres (D(x_{i}) = G(x_{i})), s’étend aux monômes par application de la règle de Leibniz :

D(uv) = D(u)v + uD(v),

puis s’étend aux polynômes par linéarité. Il est clair que l’opérateur de dérivation D s’identifie à la somme (finie ou infinie) :

D = D(x_{1})\frac{∂}{∂x_{1}} + D(x_{2})\frac{∂}{∂x_{2}} + D(x_{3})\frac{∂}{∂x_{3}} + ⋯

mais nous utiliserons peu cette notation et lui préférerons la présentation flêchée de W. Chen, et cela pour deux raisons : d’une part la notation utilisant les dérivées partielles est lourde quand l’alphabet est infini (et l’apport principal de W. Chen consiste précisément à étudier des cas de ce type), d’autre part cette notation exprime un calcul purement formel alors que la grammaire introduit un calcul combinatoire. Par exemple le calcul formel

yz \frac{∂}{∂x} x^{3} = 3x^{2}yz

ne reflète qu’imparfaitement le calcul grammatical

xxx → (yz)xx + x(yz)x + xx(yz)

dans lequel chacune des trois lettres x est tour à tour réécrite yz, (ce qui conduit d’ailleurs naturellement à une extension d’un tel calcul au cas non commutatif, mais ce n’est pas notre objectif ici).

Etant données une grammaire G et la dérivation associée D, on s’intéresse à la suite des polynômes qui sont les dérivées successives d’une lettre, par exemple :

x_{1}, D(x_{1}), D(D(x_{1})), ⋯ D^{n}(x_{1}), ⋯

et à la série génératrice exponentielle Gen(x_{1}, t) de cette suite :

Gen(x_{1}, t) = x_{1} + D(x_{1})t + D^{2}(x_{1})\frac{t^{2}}{2!} + ⋯ + D^{n}(x_{1})\frac{t^{n}}{n!} + ⋯

On fait de même pour chaque lettre x_{i}. Une autre manière d’introduire ces séries génératrices est de considérer les fonctions y_{1}(t), y_{2}(t), y_{3}(t), ⋯ solutions du système différentiel

\begin{aligned}y′_{1}(t) & = D(y_{1}(t)),  y_{1}(0) = x_{1} \\ y′_{2}(t) & = D(y_{2}(t)),  y_{2}(0) = x_{2} \\ y′_{3}(t) & = D(y_{3}(t)),  y_{3}(0) = x_{3} \\ ⋯ & = ⋯ \end{aligned}

dans lequel D(y_{i}(t)) est la fonction obtenue en remplaçant dans le polynôme D(x_{i}) chaque lettre x_{j} par la fonction y_{j}(t) (et en faisant des produits et des sommes de fonctions). Dans ces conditions on a, par la règle de Leibniz, l’identité suivante pour n ≥ 0 :

y_{i}^{(n)}(t) = D^{n}(y_{i}(t)).

Par suite

y_{i}^{(n)}(0) = D^{n}(y_{i}(0)) = D^{n}(x_{i}),

ce qui montre que y_{i}(t) n’est autre que Gen(x_{i}, t). Nous ne faisons ici que rappeler un résultat classique qu’on trouve par exemple dans [BLL] (section 5.2)

On peut aussi introduire, à partir d’un polynôme p dans les lettres x_{i}, les polynômes dérivées successifs D^{n}(p) et leur série génératrice Gen(p, t). A ce sujet nous rappelons (W. Chen [Ch], prop. 3.2 et 3.4) que l’application p ↦ Gen(p, t) est un homomorphisme de l’algèbre différentielle (C[X], D) sur l’algèbre différentielle (C[[t]], \frac{d}{dt}), en ce sens que

\begin{aligned}Gen(pq, t) & = Gen(p, t)Gen(q, t), \\ Gen(D(p), t) & = \frac{d}{dt}Gen(p, t). \end{aligned}

Notre objectif dans cet article est de présenter sous cet angle un certain nombre d’exemples de suites de polynômes classiques, qui présentent essentiellement deux aspects, un aspect proprement “calculatoire”, et un aspect “combinatoire” en tant que polynômes énumérateurs.

Dans la Combinatoire de naguère, le lien entre les deux aspects s’opérait le plus souvent par le biais de relations de récurrences sur les suites d’entiers qui sont les coefficients des polynômes. Ainsi une même relation de récurrence sur des entiers s’interprète à la fois comme la traduction d’un calcul formel sur des polynômes ou des séries, et comme la traduction de dénombrements d’ensembles d’objets combinatoires.

Cette coïncidence des deux traductions apparaissait, et apparaît encore parfois, comme un peu mystérieuse. Aujourd’hui on tend à construire des théories explicatives. Par exemple quand on fait le lien entre le calcul de l’exponentielle d’une série formelle et la notion combinatoire de composé partitionnel [F], on aboutit à une identité telle que

exp(xt + \frac{t^{2}}{2!} ) = ∑_{n≥0}( ∑_{σ∈I_{n}} x^{fix(σ)})\frac{t^{n}}{n!}

où I_{n} désigne l’ensemble des involutions de [n]. La théorie permet de faire l’économie des coefficients des polynômes, en fait elle fournit l’interprétation combinatoire de ces coefficients sans qu’il soit besoin de faire appel ni à leur expression (close ou sommatoire), ni à leur récurrence, ni même à leur notation.

Cette approche, qui vise à expliciter des liens “fondamentaux” entre calcul et combinatoire, a été reprise et développée par d’autres écoles, notamment à travers la théorie des espèces de structures de l’école québecquoise [BLL]. On y définit un ensemble de concepts qui fournissent un cadre explicatif général pour un grand nombre de cas particuliers déjà connus, et permet de formuler des théorèmes généraux.

Notre ambition ici se bornera à dresser une liste d’exemples de grammaires. Chacune de ces grammaires engendre par dérivations successives une suite de polynômes. Or on constate que ces polynômes sont énumérateurs sur certains objets combinatoires. Par exemple ils énumèrent certaines structures arborescentes selon les arêtes ou les sommets pondérés par les lettres de l’alphabet. Le lien avec la grammaire provient de ce que dans tout “prolongement” d’un objet de taille n − 1 en un objet “dérivé” de taille n, l’insertion du nouveau sommet étiqueté n se traduit sur le polynôme énumérateur des sommets ou arêtes par une règle de réécriture d’une certaine lettre.

En outre cette même grammaire permet aussi de rendre compte d’un certain calcul sur les séries formelles. Elle constitue de ce fait un point de jonction entre combinatoire et calcul qui permet de se passer des coefficients entiers. Nous nous situons donc bien ici dans la démarche de pensée qui se trouve à l’origine des théories sur les fondements de la Combinatoire énumérative. Notons à ce propos que le point de vue “grammatical” des règles de réécritures littérales, tel qu’il a été présenté par William Chen, est de toute évidence fortement relié aux concepts d’“arborescence enrichie” et d’“éclosion combinatoire” introduits par l’école québecquoise (cf. [BLL]). Cependant nous ne chercherons pas ici à faire le lien avec cette théorie générale, notre ambition n’étant que de fournir nombre d’exemples qui plaident en faveur du “point de vue grammatical”, exemples souvent peu connus, et nouveaux pour certains.

Nous distinguerons deux parties dans notre exposé, selon que l’alphabet de base est fini ou infini.

2. Exemples où l’alphabet X est fini

2.1. Polynômes eulériens. — Etant donnée une permutation σ de [n], une arête de cycle est un couple (i, σ(i)). C’est une montée de cycle si i < σ(i), une descente de cycle si i > σ(i), une boucle si i = σ(i).

Commençons par le polynôme énumérateur des permutations circulaires (pour n ≥ 2) selon les montées et descentes de cycles :

A_{n}(x, y) = ∑_{σ∈C_{n}} x^{mc(σ)}y^{dc(σ)}.

Par exemple on a, pour n = 3, deux éléments de C_{3}. A σ = (123) correspond le monôme x^{2}y, et à σ = (132) correspond le monôme xy^{2}, d’où A_{3}(x, y) = x^{2}y +xy^{2}. Pour passer de A_{n−1}(x, y) à A_{n}(x, y), on observe qu’une insertion de n dans le cycle d’une permutation circulaire τ de [n − 1] correspond au choix d’une arête (i, τ(i)) (montée ou descente) de τ, puis au remplacement de celle-ci par une montée (i, n) et une descente (n, d(i)) pour σ. Sur le polynôme énumérateur cela revient à réécrire l’une des lettres x ou y du monôme selon la grammaire

G = {x → xy, y → xy}.

En considérant toutes les insertions possibles, on obtient :

A_{n}(x, y) = DA_{n−1}(x, y),

où D est la dérivation associée à cette grammaire. Voici les premières valeurs des polynômes eulériens (donnés ici sous leur forme homogène et symétrique) :

\begin{aligned}A_{1}(x, y, z) & = z \\ A_{2}(x, y) & = xy \\ A_{3}(x, y) & = x^{2}y + xy^{2} \\ A_{4}(x, y) & = x^{3}y + 4x^{2}y^{2} + xy^{3} \\ A_{5}(x, y) & = x^{4}y + 11x^{3}y^{2} + 11x^{2}y^{3} + xy^{4} \end{aligned}

Nous avons écrit A_{1}(x, y, z) = z car dans le cas n = 1 on a une boucle, et en fait la grammaire que nous avons utilisée est

G = {x → xy, y → xy, z → xy}.

2.2 Polynômes de Roselle

La grammaire précédente doit être complétée si l’on veut obtenir le polynôme énumérateur de l’ensemble des permutations selon les trois statistiques : montées, descentes, boucles. Considérons la grammaire suivante :

G = {x → xy, y → xy, z → xy, e → ez},

Initialisons en e et en dérivons selon l’opérateur D associé à cette grammaire. Les polynômes E_{n}(x, y, z) = D^{n}(e) ont pour premières valeurs :

\begin{aligned}E_{0}(x, y, z) & = e \\ E_{1}(x, y, z) & = ez \\ E_{2}(x, y, z) & = e(xy + z^{2}) \\ E_{3}(x, y, z) & = e(x^{2}y + xy^{2} + 3xyz + z^{3}) \\ E_{4}(x, y, z) & = e(x^{3}y + 7x^{2}y^{2} + xy^{3} + 4x^{2}yz + 4xy^{2}z + 6xyz^{2} + z^{4}) \end{aligned}

Il est clair que

E_{n}(x, y, z) = e ∑_{σ∈S_{n}} x^{mc(σ)}y^{dc(σ)}z^{b(σ)}.

Dans cette écriture, la lettre e désigne la place vide destinée à être à la fois occupée par la boucle (n, n) (en cas d’insertion de ce type) et reconduite (dans la même hypothèse), d’où e ⟶ ez. Notons que les polynômes E_{n}(x, y, 0), qui énumèrent les dérangements selon les montées et descentes de cycles, ont été étudiés par Roselle [Ro]. Par ailleurs posons :

E(t) = ∑_{n≥0} \frac{1}{e}E_{n}(x, y, z)\frac{t^{n}}{n!} et A(t) = ∑_{n≥1} A_{n}(x, y)\frac{t^{n}}{n!} .

La théorie du composé partitionnel fournit immédiatement l’identité

E(t) = exp(A(t)).

Mais nous pouvions également obtenir ce résultat en observant que E(t) = \frac{1}{e}Gen(e, t), d’où

E′(t) = \frac{1}{e}Gen(ez, t) = \frac{1}{e}Gen(e, t)Gen(z, t) = E(t)A′(t).

2.3. Arborescences croissantes de type (0, 1, 2) (ou arbres d’André)

Soit f une application de {2, 3, … n} dans {1, 2, … n − 1} qui satisfait les deux conditions suivantes :

(C1) pour tout i ∈ {2, 3, … n}, f(i) < i;

(C2) pour tout j ∈ {1, 2, … n − 1}, 0 ≤ card(f^{−1}(j)) ≤ 2.

On trace une arête orientée croissante j → i chaque fois que i est antécédent de j (f(i) = j), et on obtient ainsi un arbre E qu’on appelle un arbre d’André, d’après [FS]. C’est une arborescence dont les sommets sont {1, 2, 3, … n}, dont les n − 1 arêtes sont croissantes, et tel que chaque sommet possède 0, 1 ou 2 fils. Il est clair que la donnée de l’arbre d’André E est équivalente à celle de f vérifiant (C1) et (C2). On désigne par E_{n} l’ensemble des arbres d’André E de taille n, et on considère le polynôme énumérateur

E_{n}(x, y) = ∑_{E∈E_{n}} x^{ext(E)}y^{un(E)},

où ext(E) désigne le nombre d’extrémités de E, c’est-à-dire de sommets sans fils, et un(E) le nombre de sommets unaires, c’est-à-dire ayant un seul fils (on ne met pas de lettre z pour les sommets binaires, sauf si l’on veut homogénéiser le polynôme).

Pour passer d’un arbre E de taille n − 1 à un arbre F de taille n, il faut choisir une extrémité e ou un sommet unaire u de E et faire e → n ou u → n. Dans le premier cas, on remplace une lettre x par xy, dans le second cas on remplace une lettre y par x (puisqu’on ne compte pas le sommet binaire créé, mais seulement l’extrémité créée). Par suite

E_{n}(x, y) = DE_{n−1}(x, y), avec G = {x → xy, y → x}

Voici les premières valeurs des polynômes d’André E_{n}(x, y) :

\begin{aligned}E_{1}(x, y) & = x \\ E_{2}(x, y) & = xy \\ E_{3}(x, y) & = xy^{2} + x^{2} \\ E_{4}(x, y) & = xy^{3} + 4x^{2}y \\ E_{5}(x, y) & = xy^{4} + 11x^{2}y^{2} + 4x^{3} \end{aligned}

Montrons que E_{n}(1, 1) est le n−ième nombre d’Euler (sécant ou tangent). Posons

Y (t) = Gen(y, t) = y + ∑_{n≥1} E_{n}(x, y)\frac{t^{n}}{n!} .

On a, d’après l’homomorphisme d’algèbres différentielles rappelé dans l’introduction :

Y′(t) = Gen(x, t)
Y′′(t) = Gen(xy, t)
= Gen(x, t)Gen(y, t)
= Y′(t)Y (t),

d’où Y′′(x, y; t) = Y (x, y; t)Y′(x, y : t), avec Y (x, y; 0) = y et Y′(x, y; 0) = x. On peut intégrer cette équation générale, mais nous nous intéressons plus particulièrement au cas où x = y = 1, et il est bien connu qu’alors la solution de cette équation est

Y (1, 1; t) = \frac{1}{cos t} + tg t

d’où le résultat classique [FS].

2.4. Arbres binaires croissants.. — Un arbre binaire croissant A de taille n est un couple A = (E, φ), où E est un arbre d’André de taille n et φ une application de l’ensemble des n − 1 arêtes de l’arbre dans l’ensemble “gauche-droite” {g, d}, avec pour seule restriction que les deux arêtes issues d’un sommet binaire sont l’une, gauche, et l’autre, droite.

L’arête issue d’un sommet unaire elle étant soit gauche, soit droite, il existe non pas un, mais deux prolongements d’une extrémité e en une arête e → n, tandis qu’il existe toujours un seul prolongement d’un sommet unaire u en une arête u → n (cette nouvelle arête sera gauche si la première arête issue de u était droite, et inversement). Par conséquent, si

P_{n}(x, y) = ∑_{A∈A_{n}} x^{ext(A)}y^{un(A)}

est le polynôme énumérateur des arbres binaires croissants selon les mêmes paramètres, on a

P_{n}(x, y) = D^{n}(y), avec G = {x → 2xy, y → x}, soit :

\begin{aligned}P_{1}(x, y) & = x \\ P_{2}(x, y) & = 2xy \\ P_{3}(x, y) & = 4xy^{2} + 2x^{2} \\ P_{4}(x, y) & = 8xy^{3} + 16x^{2}y \\ P_{5}(x, y) & = 16xy^{4} + 88x^{2}y^{2} + 16x^{3} \end{aligned}

Notons que si l’on homogénéise les polynômes en prenant les n sommets :

\begin{aligned}E_{n}(x, y, z) & = ∑_{E∈E_{n}} x^{ext(E)}y^{un(E)}z^{bin(E)}, \\ P_{n}(x, y, z) & = ∑_{A∈A_{n}} x^{ext(A)}y^{un(A)}z^{bin(A)} \end{aligned}

il est clair qu’alors P_{n}(x, y, z) = E_{n}(x, 2y, 2z). En outre il existe une bijection classique entre arbres binaires croissants et permutations, consistant intuitivement à projeter sur l’axe horizontal les sommets de l’arbre pour obtenir un ordre linéaire définissant la permutation. Cette bijection fait correspondre aux sommets binaires de l’arbre les creux du mot de la permutation (σ(i − 1) > σ(i) < σ(i + 1), d’où l’interprétation combinatoire de P_{n}(1, 1, z) comme énumérateurs des creux sur les permutations.

3. Exemples de grammaires où l’alphabet X est infini

3.1. Grammaire de Faa di Bruno et polynômes de Bell. — Ce paragraphe est essentiellement dû à Chen [Ch]. Sur l’alphabet X = {x_{1}, x_{2}, x_{3}, …, y_{0}, y_{1}, y_{2}, y_{3}, …} on définit la grammaire de Faa di Bruno comme

G = {x_{1} → x_{2}, x_{2} → x_{3}, x_{3} → x_{4} …
y_{0} → y_{1}x_{1}, y_{1} → y_{2}x_{1}, y_{2} → y_{3}x_{1} …}

On considère la suite D^{n}(y_{0}) associée :

\begin{aligned}D^{0}(y_{0}) & = y_{0} \\ D^{1}(y_{0}) & = y_{1}x_{1} \\ D^{2}(y_{0}) & = y_{1}x_{2} + y_{2}x_{1}^{2} \\ D^{3}(y_{0}) & = y_{1}x_{3} + y_{2}(3x_{1}x_{2}) + y_{3}x_{1}^{3} \\ D^{4}(y_{0}) & = y_{1}x_{4} + y_{2}(4x_{1}x_{3} + 3x_{2}^{2}) + y_{3}(6x_{1}^{2}x_{2}) + y_{4}x_{1}^{4} \end{aligned}

Ces polynômes ont deux interprétations fondamentales : calculatoire et combinatoire.

Sur le plan du calcul il s’agit de la composition de deux séries génératrices exponentielles, ou, ce qui revient au même, du calcul des dérivées successives d’une fonction de fonction. Soient

\begin{aligned}x(t) & = x_{1}t + x_{2} \frac{t^{2}}{2!} + ⋯ + x_{n} \frac{t^{n}}{n!} + ⋯ \\ y(x) & = y_{0} + y_{1}x + y_{2} \frac{x^{2}}{2!} + ⋯ + y_{n} \frac{x^{n}}{n!} + ⋯ \end{aligned}

deux séries. Comme la première est sans terme constant, il est possible de la substituer à la variable de la seconde. On considère donc

y(x(t)) = y_{0} + y_{1}x(t) + y_{2} \frac{x(t)^{2}}{2!} + ⋯ + y_{n} \frac{x(t)^{n}}{n!} + ⋯

et en développant y(x(t)) selon les puissances croissantes de t, on obtient précisément :

y(x(t)) = y_{0} + y_{1}x_{1}t + (y_{1}x_{2} + y_{2}x_{1}^{2})\frac{t^{2}}{2!} + (y_{1}x_{3} + y_{2}(3x_{1}x_{2}) + y_{3}x_{1}^{3})\frac{t^{3}}{3!}

+ ⋯ + D^{n}(y_{0})\frac{t^{n}}{n!} + …

En effet, notons x^{(k)}(t), puis plus simplement x_{k}(t), la dérivée k−ième de x(t). De même, notons y^{(k)}(x(t)), puis plus simplement y_{k}(t), la fonction obtenue en substituant x(t) à x dans y^{(k)}(x). On a alors les dérivées successives :

\begin{aligned}\frac{d}{dt}y(x(t)) & = y′(x(t))x′(t) = y_{1}(t)x_{1}(t) \\ \frac{d^{2}}{dt^{2}} y(x(t)) & = y′(x(t))x′′(t) + y′′(x(t))x′(t)^{2} = y_{1}(t)x_{2}(t) + y_{2}(t)x_{1}^{2}(t) \\ \frac{d^{3}}{dt^{3}} y(x(t)) & = y_{1}(t)x_{3}(t) + y_{2}(t)(3x_{1}(t)x_{2}(t)) + y_{3}(t)x_{1}^{3}(t) \end{aligned}

Il est clair que

\begin{aligned}\frac{d}{dt}x_{k}(t) & = x_{k+1}(t), \\ \frac{d}{dt}y_{k}(t) & = \frac{d}{dt}y^{(k)}(x(t)) = y^{(k+1)}(x(t)) · x′(t) = y_{k+1}(t)x_{1}(t). \end{aligned}

Par suite

\frac{d^{n}}{dt^{n}} y(x(t)) = D^{n}(y_{0}(t))

d’où le résultat en prenant t = 0.

Pour l’interprétation combinatoire, on introduit l’ensemble Π_{n} des partitions π de [n]. Etant donnée une partition π de [n], on note b_{i}(π) le nombre de blocs de π de cardinal i, et b(π) = b_{1}(π) + b_{2}(π) + ⋯ + b_{n}(π) le nombre total de ses blocs. Alors on a :

D^{n}(y_{0}) = ∑_{π∈Π_{n}} y_{b(π)}x_{1}^{b_{1}(π)}x_{2}^{b_{2}(π)} ⋯ x_{n}^{b_{n}(π)}.

Exemple.— Voici, pour n = 3, les cinq partitions π suivies de leurs monômes respectifs m(π) entre parenthèses :

/123/(y_{1}x_{3}) /1/23/(y_{2}x_{1}x_{2}) /2/13/(y_{2}x_{1}x_{2})
/3/12/(y_{2}x_{1}x_{2}) /1/2/3/(y_{3}x_{1}^{3})

Démonstration.— Si π est une partition de [n] et π̄ la partition de [n − 1] obtenue en supprimant n de son bloc dans π, on dit que π̄ est la restriction de π et que π est un prolongement de π̄. Comparons alors m(π̄) et m(π). Si l’on prolonge π̄ en π en insérant n dans un bloc de cardinal i de π̄, alors il suffit de remplacer une lettre x_{i} de m(π̄) par x_{i+1} pour obtenir m(π). Mais si l’on prolonge π̄ en π en créant un nouveau bloc {n} alors, en posant k = b(π̄), il faut remplacer la lettre y_{k} de m(π̄) par y_{k+1}x_{1} pour obtenir m(π). Par suite

D(m(π̄)) = ∑_{π} m(π),

où la somme est étendue à tous les prolongements π de π̄. En prenant toutes les π̄, chaque π est obtenue une fois, comme prolongement de sa restriction :

D( ∑_{π̄∈Π_{n−1}} m(π̄)) = ∑_{π∈Π_{n}} m(π),

d’où le résultat par induction sur n.

Rappelons pour conclure qu’on note souvent

D^{n}(y_{0}) = ∑_{1≤k≤n} y_{k}B_{n}, k(x_{1}, x_{2}, …, x_{n}),

les B_{n,k} s’appelant les polynômes de Bell. En prenant tous les y_{k} égaux à 1, on obtient la fonction génératrice bien connue :

exp(x(t)) = ∑_{n≥0}( ∑_{1≤k≤n} B_{n}, k(x_{1}, x_{2}, …, x_{n}))\frac{t^{n}}{n!}

3.2. Grammaire de Polya et et polynômes indicateurs de cycles Appelons grammaire de Polya la grammaire suivante :

G = {x_{1} → x_{2}, x_{2} → 2x_{3}, x_{3} → 3x_{4} …
y_{0} → y_{1}x_{1}, y_{1} → y_{2}x_{1}, y_{2} → y_{3}x_{1} …}

On considère la suite D^{n}(y_{0}) associée :

\begin{aligned}D^{0}(y_{0}) & = y_{0} \\ D^{1}(y_{0}) & = y_{1}x_{1} \\ D^{2}(y_{0}) & = y_{1}x_{2} + y_{2}x_{1}^{2} \\ D^{3}(y_{0}) & = y_{1}(2x_{3}) + y_{2}(3x_{1}x_{2}) + y_{3}x_{1}^{3} \\ D^{4}(y_{0}) & = y_{1}(6x_{4}) + y_{2}(8x_{1}x_{3} + 3x_{2}^{2}) + y_{3}(6x_{1}^{2}x_{2}) + y_{4}x_{1}^{4} \end{aligned}

Les polynômes obtenus sont les polynômes indicateurs de cycles des permutations, étudiés par Polya. Plus précisément, soit σ une permutation de [n], c_{i}(σ) le nombre de cycles de σ de longueur i, et c(σ) le nombre total de ses cycles. Alors on a :

D^{n}(y_{0}) = ∑_{σ∈§_{n}} y_{c(σ)}x_{1}^{c_{1}(σ)}x_{2}^{c_{2}(σ)} ⋯ x_{n}^{c_{n}(σ)}.

La démonstration est la même que pour les partitions, à cela près qu’il y a, non pas une, mais i manières de prolonger une σ̄ en une σ en insérant n dans un cycle de longueur i de σ̄, et qu’il faut donc remplacer une lettre x_{i} de m(σ̄) par ix_{i+1} pour obtenir la somme de tous les m(σ) correspondant à ces prolongements.

3.3. — Equation y′ = f(y) et polynôme des degrés des sommets d’une arborescence croissante

Dans ce paragraphe, on considère la grammaire suivante :

G = {x_{0} → x_{1}x_{0}, x_{1} → x_{2}x_{0}, x_{2} → x_{3}x_{0}, x_{3} → x_{4}x_{0}, …}

Les dérivées successives de x_{0} sont alors :

\begin{aligned}D^{0}(x_{0}) & = x_{0} \\ D^{1}(x_{0}) & = x_{0}x_{1} \\ D^{2}(x_{0}) & = x_{0}x_{1}^{2} + x_{0}^{2}x_{2} \\ D^{3}(x_{0}) & = x_{0}x_{1}^{3} + 4x_{0}^{2}x_{1}x_{2} + x_{0}^{3}x_{3} \\ D^{4}(x_{0}) & = x_{0}x_{1}^{4} + 11x_{0}^{2}x_{1}^{2}x_{2} + 4x_{0}^{3}x_{2}^{2} + 7x_{0}^{3}x_{1}x_{3} + x_{0}^{4}x_{4} \end{aligned}

Pour cet exemple aussi nous allons dégager une interprétation calculatoire et une interprétation combinatoire.

Etant donnée la série exponentielle

f(t) = x_{0} + x_{1}t + x_{2} \frac{t^{2}}{2!} + ⋯ + x_{n} \frac{t^{n}}{n!} + ⋯,

on cherche la solution de l’équation différentielle

y′ = f(y), y(0) = 0.

y′ = x_{0} + x_{1}y + x_{2} \frac{y^{2}}{2!} + ⋯ + x_{k} \frac{y^{k}}{k!} + ⋯, y(0) = 0.

Alors cette solution est donnée par la série

y = x_{0}t + x_{0}x_{1} \frac{t^{2}}{2!} + (x_{0}x_{1}^{2} + x_{0}^{2}x_{2})\frac{t^{3}}{3!} + ⋯ + D^{n−1}(x_{0})\frac{t^{n}}{n!} + ⋯,

où D est la dérivation associée à la grammaire ci-dessus.

En effet, dérivons l’égalité y′(t) = f(y(t)). Notons f_{k}(t) la fonction f^{(k)}(y(t)), c’est-à-dire la fonction obtenue en substituant y(t) à y dans f^{(k)}(y). On a donc y′(t) = f(y(t)) = f_{0}(t). En outre,

f′_{k}(t) = \frac{d}{dt}f^{(k)}(y(t)) = f_{k+1}(t)y′(t) = f_{k+1}(t)f_{0}(t) (k ≥ 0).

Or y′(t) = f_{0}(t). Par induction sur n, on en déduit que y^{(n)}(t) = D^{n−1}(f_{0}(t)), d’où le résultat en portant t = 0, puisque f_{0}(0) = f(y(0)) = f(0) = x_{0}.

Nous en venons à présent à l’interprétation combinatoire. A une application f de {1, 2, …, n} dans {0, 1, 2, …, n − 1} telle que pour tout i, f(i) < i correspond l’arborescence croissante obtenue en traçant une arête orientée croissante j → i chaque fois que i est antécédent de j (f(i) = j). Contrairement au cas des arbres d’André, la multiplicité d’un sommet, c’est-à-dire le nombre de ses fils, n’est pas bornée (elle est, pour une arborescence de taille n, comprise entre 0 et n). On désigne par m_{i}(F) le nombre de sommets de F de multiplicité égale à i. Dans ces conditions, si l’on pose

E_{n}(x_{0}, x_{1}, … x_{n}) = ∑_{F ∈F_{n}} x_{0}^{m_{0}(F)}x_{1}^{m_{1}(F)} ⋯ x_{n}^{m_{n}(F)}

alors ce polynôme n’est autre que le polynôme D^{n}(x_{0}) ci-dessus. En effet, on prolonge un arbre G de taille n − 1 en un arbre F de taille n en créant une arête s → n à partir d’un sommet quelconque s de G. Si ce sommet s est de multiplicité i dans G, il est représenté dans le monôme de G par la lettre x_{i}, qu’il faut donc remplacer par x_{i+1}x_{0} pour obtenir le monôme de F.

On trouve une autre démonstration, basée essentiellement sur un composé partitionnel, dans [BLL], section 5 : on supprime le sommet 0 et ses arêtes, on obtient alors une partition de [n] en blocs, et un arbre sur chaque bloc. Si y est la série énumératrice complète, le coefficient de \frac{t^{n}}{n!} dans le développement de x_{k} \frac{y^{k}}{k!} est le polynôme énumérateur des arbres de taille n dans lesquels le sommet 0 est de multiplicité k. En sommant sur k, on trouve l’égalité entre développements de f(y) et de y′.

Remarquons que les exemples considérés plus haut en 2.1 et 2.3 s’obtiennent comme cas particuliers. D’une part, on retrouve les polynômes eulériens en faisant x_{1} = x_{2} = x_{3} = ⋯:

E_{n}(x_{0}, x_{1}, x_{1}, x_{1}, ⋯) = A_{n}(x_{0}, x_{1}),

d’autre part on retrouve les arbres d’André en interdisant les multiplicités ≥ 3 : les polynômes d’André homogènes

E_{n}(x_{0}, x_{1}, x_{2}, 0, 0, ⋯) = E_{n}(x_{0}, x_{1}, x_{2})

ont donc pour fonction génératrice la solution de l’équation de Ricatti générale

y′ = x_{0} + x_{1}y + x_{2} \frac{y^{2}}{2!} ·

3.4. Equation y = f(xy), grammaire de Lagrange, polynôme des degrés des sommets d’une arborescence, ou des poids d’une fonction de parking

Etant donnée une série formelle de type exponentiel :

f(x) = a_{0} + a_{1}x + a_{2}x^{2}/2! + ⋯ + a_{n}x^{n}/n! + ⋯,

on considère la solution y de l’équation y = f(xy) :

(1)  y = a_{0} + a_{1}xy + a_{2}(xy)^{2}/2! + ⋯ + a_{n}(xy)^{n}/n! + · · · .

Cette équation implicite définit une série formelle y unique, comme le montre l’algorithme naturel suivant :

y = a_{0} + ⋯
y = a_{0} + a_{1}x(a_{0} + ⋯) = a_{0} + a_{0}a_{1}x + ⋯
y = a_{0} + a_{1}x(a_{0} + a_{0}a_{1}x + ⋯) + a_{2}(x(a_{0} + ⋯))^{2}/2! + ⋯
y = a_{0} + a_{0}a_{1}x + (2a_{0}a_{1}^{2} + a_{0}^{2}a_{2}) x^{2}/2! + ⋯
⋯
y = a_{0} + a_{0}a_{1}x + (2a_{0}a_{1}^{2} + a_{0}^{2}a_{2}) x^{2}/2! + ⋯
+ P_{n}(a_{0}, a_{1}, …, a_{n}) x^{n}/n! + ⋯

où il apparaît clairement, par récurrence sur n, que le coefficient de x^{n}/n! est un polynôme P_{n}, homogène de degré n + 1 dans les lettres a_{0}, a_{1}, ⋯ a_{n}. Nous n’expliciterons pas davantage cet algorithme de type “recherche du point fixe”, car le calcul des polynômes P_{n} se complique très vite.

Notre objectif est de trouver une grammaire G sur l’alphabet des a_{i} telle que

P_{n} = D(P_{n−1}),

ce qui donnera une récurrence beaucoup plus simple.

Pour cela, nous allons utiliser l’interprétation combinatoire des polynômes P_{n}, qui est classique (plus précisément, elle dérive immédiatement des classiques interprétations combinatoires de la formule d’inversion de Lagrange, cf. par exemple [BLL]).

Soit A une arborescence de racine 0 et de n arêtes, construite sur les n + 1 sommets {0, 1, 2, …, n} (c’est-à-dire un arbre de Cayley enraciné en 0). On note A_{n} l’ensemble de ces arborescences.

Tout sommet i de A (0 ≤ i ≤ n) possède un degré d_{i} (degré sortant), qui est le nombre d’arêtes issues de i. A l’arborescence A, on associe le monôme m(A) défini par

m(A) = a_{d_{0}}a_{d_{1}}a_{d_{2}} ⋯ a_{d_{n}}.

Exemple.— Soit n = 9. Considérons l’arborescence A suivante :

0

↙ ↘
3  9
↓  ↙ ↓ ↘
6 1 4 7
↙ ↘  ↓
2  5  8

Il est clair que d_{0} = 2, d_{1} = 0, d_{2} = 0, d_{3} = 1, …, d_{9} = 3. Par suite,

m(A) = a_{2}a_{0}a_{0}a_{1}a_{0}a_{0}a_{2}a_{1}a_{0}a_{3} = a_{0}^{5}a_{1}^{2}a_{2}^{2}a_{3}.

Dans m(A), la puissance de a_{0} est le nombre de sommets pendants, la puissance de a_{1} est le nombre de sommets ayant un fils, etc. On a alors

P_{n} = ∑_{A∈A_{n}} m(A).

Rappelons rapidement la démonstration de ce résultat. Posons :

y = ∑_{n≥0} ∑_{A∈A_{n}} m(A).

On a alors

a_{k}(xy)^{k}/k! = ∑_{n≥0} ∑_{A∈A_{n};d_{0}=k} m(A).

En effet, une arborescence telle que d_{0} = k se construit à partir d’une partition de [n] en k blocs et d’une arborescence sur chacun de ces blocs, à quoi l’on ajoute le sommet 0 et les k arêtes reliant 0 aux racines respectives des k arborescences.

En sommant sur k, on en déduit que y satisfait l’équation fonctionnelle y = f(xy).

A partir de l’interprétation combinatoire, nous allons montrer que y est également l’unique solution de l’équation

(2)  y′ = y D_{+}(y), y(0) = a_{0},

où D_{+} est l’opérateur différentiel associé à la grammaire d’augmentation

{a_{0} → a_{1}, a_{1} → a_{2}, …, a_{i} → a_{i+1}, …}.

Il est équivalent de montrer que la suite P_{n} satisfait la récurrence de type binomial :

(3)  P_{n+1} = ∑_{k=0}^{n} \binom{n}{k}D_{+}(P_{k}) P_{n−k},  P_{0} = a_{0}.

Nous appelons arborescence augmentée (A, p →) le couple formé d’une arborescence A et d’une arête pendante (p →) issue de l’un de ses sommets p (pendante en ce sens qu’elle n’aboutit pas à un sommet étiqueté). Par suite, le degré d_{p} augmente de 1 quand on passe à l’arborescence augmentée. En considérant tous les choix possibles de p, puis l’ensemble A_{k,·→} de toutes les arborescences augmentées possédant (k + 1) sommets et (k + 1) arêtes (dont une pendante), on a :

D_{+}(m(A)) = ∑_{p} m(A, p →),  D_{+}(P_{k}) = ∑_{(A,p→)∈A_{k,·→}} m(A, p →)

A présent, on partitionne de manière unique une arborescence A de A_{n+1} en deux composantes comme suit : on désigne par p le père du sommet 1, par C la sous-arborescence de A de racine 1, et par (B, p →) l’arborescence augmentée qui est le complémentaire de C dans A, de sorte qu’on a

m(A) = m(B, p →)m(C).

Réciproquement, on choisit dans l’ensemble {2, 3, …, n + 1} les n − k sommets qui seront les descendants de 1 , on leur ajoute 1 et on construit une arborescence C de racine 1 et de n − k arêtes sur l’ensemble obtenu. Puis sur l’ensemble complémentaire dans [0, n + 1] on construit une arborescence augmentée (B, p →) de racine 0 et de (k + 1) arêtes (dont une pendante). En réunissant les deux, on obtient une arborescence A de A_{n+1}.

En sommant sur k, on déduit la récurrence de type binomial (3). Cette récurrence représente un premier progrès dans la simplification des calculs (par rapport à l’algorithme du point fixe).

Nous allons à présent trouver une grammaire engendrant ces polynômes. A cet effet, nous définissons une suite de fonctions (y_{n}) par la récurrence

y_{0} = y, y_{1} = D_{+}(y_{0}), ⋯ y_{n} = D_{+}(y_{n−1}).

L’opérateur différentiel D_{+} opérant sur les variables a_{i}, il commute avec la dérivation ordinaire par rapport à x, on a donc

y′_{0} = y_{0}y_{1}, y′_{1} = D_{+}(y′_{0}) = D_{+}(y_{0}y_{1}) = y_{0}y_{2} + y_{1}^{2}, ⋯ y′_{n} = D_{+}(y′_{n−1}).

On voit que y′_{n} est un polynôme dans les y_{0}, y_{1}, ... y_{n+1}, plus précisément, c’est, d’après la formule de Leibniz :

y′_{n} = D_{+}^{n}(y_{0}y_{1}) = ∑_{k=0}^{n} \binom{n}{k}y_{k}y_{p+1−k}.

A présent nous définissons comme suit la grammaire de Lagrange sur l’alphabet des a_{i} :

G = {a_{0} → a_{0}a_{1}, a_{1} → D_{+}(a_{0}a_{1}) = a_{0}a_{2} + a_{1}^{2}, …

a_{n} → D_{+}^{n}(a_{0}a_{1}) = ∑_{k=0}^{n} \binom{n}{k}a_{k}a_{n+1−k}, …\},

et notons D l’opérateur différentiel associé à cette grammaire autrement dit

D = (a_{0}a_{1})∂/∂a_{0} + (a_{0}a_{2} + a_{1}^{2})∂/∂a_{1} + ⋯ + (∑_{k=0}^{n} \binom{n}{k}a_{k}a_{n+1−k})∂/∂a_{n} + ⋯

Nous allons montrer que G est bien la grammaire que nous recherchons, en ce sens qu’on a :

P_{n} = D^{n}(a_{0}).

Pour cela, faisons opérer la grammaire de Lagrange sur les y_{i} (à la place des a_{i}), et vérifions que le calcul des dérivées successives de y_{0} en fonction des y_{i} coïncide avec le calcul selon la grammaire G des dérivées successives de y_{0} quand on considère ces dérivées comme des polynômes dans les y_{i}, autrement dit :

y_{0}^{(n)} = D(y_{0}^{(n−1)}), d’où y_{0}^{(n)} = D^{n}(y_{0}).

La vérification est immédiate : on a bien y′_{0} = y_{0}y_{1} = D(y_{0}), d’où y′′_{0} = y_{0}y′_{1} + y′_{0}y_{1} = y_{0}D_{+}(y_{0}y_{1}) + (y_{0}y_{1})y_{1} = D^{2}(y_{0}), et ainsi de suite d’après l’identité y′_{i} = D_{+}^{i}(y_{0}y_{1}) montrée ci-dessus.

En portant x = 0 dans cette identité, et en tenant compte de y_{n}(0) = a_{n}, on déduit

y^{(n)}(0) = P_{n} = D^{n}(a_{0})

Les premières valeurs sont :

P_{0} = a_{0}
P_{1} = a_{0}a_{1}
P_{2} = (a_{0}a_{1})\frac{∂}{∂a_{0}} (a_{0}a_{1}) + (a_{0}a_{2} + a_{1}^{2})\frac{∂}{∂a_{1}} (a_{0}a_{1})
= 2a_{0}a_{1}^{2} + a_{0}^{2}a_{2}
P_{3} = (a_{0}a_{1})\frac{∂}{∂a_{0}} (P_{2}) + (a_{0}a_{2} + a_{1}^{2})\frac{∂}{∂a_{1}} (P_{2}) + (a_{0}a_{3} + 3a_{1}a_{2})\frac{∂}{∂a_{2}} (P_{2})
= (a_{0}a_{1})(2a_{1}^{2} + 2a_{0}a_{2}) + (a_{0}a_{2} + a_{1}^{2})(4a_{0}a_{1}) + (a_{0}a_{3} + 3a_{1}a_{2})(a_{0}^{2})
= 6a_{0}a_{1}^{3} + 9a_{0}^{2}a_{1}a_{2} + a_{0}^{3}a_{3}

On trouve ensuite :

P_{4} = 24a_{0}a_{1}^{4} + 72a_{0}^{2}a_{1}^{2}a_{2} + 16a_{0}^{3}a_{1}a_{3} + 12a_{0}^{3}a_{2}^{2} + a_{0}^{4}a_{4}, etc.

Donnons encore une interprétation (ou une preuve) combinatoire du résultat. P_{n} désigne à présent le polynôme énumérateur, et nous allons montrer la récurrence :

P_{n} = D(P_{n−1}), P_{0} = a_{0}.

Soit A un élément de A_{n}. On définit sa restriction Ā, élément de A_{n−1}, de la manière suivante (on désigne par i le père de n) :

• si d_{n} = 0, le sommet n est pendant, on le supprime ainsi que l’arête qui conduit de i à n.

• si d_{n} > 0, on supprime n et ses fils deviennent fils de i. Dans l’exemple ci-dessus, 1, 4 et 7 deviennent fils de 0, donc Ā est l’arborescence

1 ← 0
↙ ↓ ↘
3 4 7
↓  ↓
6  8
↙ ↘
2  5

Réciproquement, soit B un élément de A_{n−1}. Pour prolonger B en une arborescence A élément de A_{n} telle que B = Ā, on doit :

- choisir un sommet i de B qui devient le père de n dans A.

- choisir une partie K (éventuellement vide) de l’ensemble des fils de i dans B qui deviennent les fils de n dans A, les autres restant fils de i.

Supposons que i possède p fils, donc il correspond dans m(B) à une occurrence de la lettre a_{p}. Si l’on choisit K de cardinal k, ce qui peut se faire de \binom{p}{k} manières, alors dans A le nouveau sommet n possède k fils et le sommet i possède (p − k + 1) fils, le monôme m(A) se déduit donc de m(B) en remplaçant une lettre a_{p} par un produit a_{k}a_{p−k+1}. L’ensemble des prolongements possibles du sommet i de degré p correspond donc sur la lettre qui le représente à la règle de substitution de la grammaire G :

a_{p} → ∑_{k=0}^{n} \binom{p}{k}a_{k}a_{p+1−k}.

En considérant l’ensemble des sommets i possibles dans B, on en déduit que D(m(B)) est la somme des monômes m(A), pour A prolongeant B. En sommant sur toutes les arborescences on obtient la récurrence caractérisant les polynômes P_{n}, la condition initiale P_{0} = a_{0} se vérifiant immédiatement sur l’arborescence réduite au sommet 0, et aussi P_{1} = a_{0}a_{1} sur l’arbre 0 → 1.

Exemple.— L’arborescence Ā ci-dessus a pour monôme m(Ā) = a_{0}^{5}a_{1}^{2}a_{2}a_{4}. Pour retrouver l’arborescence A il faut choisir le sommet 0, pour lequel p = 4, puis la partie K = {1, 4, 7} de cardinal k = 3, ce qui revient à substituer à a_{4} le produit a_{3}a_{2}, ce qui redonne bien m(A).

Signalons encore une autre interprétation combinatoire des polynômes P_{n}, en termes de fonctions de parking. Rappelons [FR] [Fr] qu’une application φ de [n] dans [n] est appelée fonction de parking s’il existe une permutation σ de S_{n} la majorant :

∀i ∈ [n], φ(i) ≤ σ(i).

On considère φ comme un mot de longueur n sur l’alphabet {0, 1, 2, …, n} :

φ = φ(1)φ(2) ⋯ φ(n).

Soit 0 ≤ j ≤ n. On note d_{j} la multiplicité de j dans φ, c’est-à-dire le nombre d’occurrences de l’entier j dans le mot φ, et on fait correspondre à φ le monôme dans les a_{i} obtenu comme suit :

w(φ) = a_{d_{0}}a_{d_{1}}a_{d_{2}} ⋯ a_{d_{n}}.

Dans w(φ), la puissance de a_{0} est le nombre d’entiers de {0, 1, 2, …, n} qui n’apparaissent pas dans φ, la puissance de a_{1} est le nombre d’entiers qui apparaissent une fois, etc. Comme la 0−ième ligne du graphe cartésien de φ est toujours vide, d_{0} = 0, et w(φ) contient toujours la lettre a_{0}.

Exemple.— n = 8, φ = 14114218, w(φ) = a_{0}a_{4}a_{1}a_{0}a_{2}a_{0}a_{0}a_{0}a_{1} = a_{0}^{5}a_{1}^{2}a_{2}a_{4}.

Dans ces conditions, on désigne par Φ_{n} l’ensemble des fonctions de parking de longueur n, et on a :

P_{n} = ∑_{φ∈Φ_{n}} w(φ).

Une preuve repose sur la bijection suivante (qui est l’une de celles existantes [Fr]) entre A_{n} et Φ_{n}. Soit A un élément de A_{n}. Les fils de chaque sommet sont rangés de gauche à droite dans l’ordre croissant. En outre, on définit les positions des sommets de 1 à n + 1 quand on décrit l’arbre dans l’ordre préfixe (depth first) en partant de la racine : 0 est en position 1, puis le plus petit fils de 0 est en position 2, etc., le dernier sommet atteint est un sommet pendant en position n+1. La fonction pos est donc une bijection de {0, 1, 2, …, n} sur [n + 1].

On définit alors φ(i) comme la position du père de i (pour 1 ≤ i ≤ n) :

φ(i) = pos(père(i)).

Il est clair que φ est une fonction de parking, car pour trouver la permutation majorante il suffit de poser σ(i) = pos(i) − 1, et on a bien φ(i) ≤ σ(i). On montre également que cette transformation A ↦ φ est une bijection. En outre, il est clair qu’on a l’égalité m(A) = w(φ), d’où le résultat. Exemple.— Soit n = 9. Si A est l’arbre pris en exemple dans le paragraphe 2, alors φ = 631632681 lui correspond par cette bijection, et σ = 631742895. On a w(φ) = m(A) = a_{0}^{5}a_{1}^{2}a_{2}^{2}a_{3}.

Remarque.— Lorsqu’on considère l’équation fonctionnelle y = f(xy) dans le cas où f est une série génératrice ordinaire (et non exponentielle), la solution est le langage de Lukasiewicz (cf. par exemple [Co]). Les interprétations combinatoires sont analogues, on peut considérer les arborescences ordonnées d’une part (ou “de Catalan”, dans lesquelles on impose par exemple que les fils de chaque sommet sont rangés dans l’ordre croissant quand on tourne dans le sens trigonométrique), les fonctions de parking croissantes d’autre part (c’est-à-dire les fonctions sousexcédantes croissantes), et reprendre les mêmes statistiques.

Le langage de Lukasiewicz est évidemment lié aux polynômes P_{n}. Mais ses propriétés relèvent essentiellement de la combinatoire algébrique du monoïde libre (factorisations de mots), il ne semble pas directement définissable par une grammaire et un opérateur différentiel, sauf à faire le détour par nos polynômes P_{n}.

Bibliographie

[BLL] BERGERON F., Labelle G., Leroux P. — Théorie des espèces et combinatoire des structures arborescentes. — LACIM, Montréal, 1994.

[Ca] CARLITZ L.. — A note on the Lagrange expansion formula, Buletinul Institutului Politehnic din Iaşi, Secţia 1, Matematicǎ, t. 17, 1971, p. 39–44.

[Ch] CHEN W.Y.C. — Context-free Grammars, Differential Operators and Formal Power Series, Actes Coll. Séries formelles et Combinatoire algébrique, LABRI, Bordeaux, 1991, p. 144–159.

[Co] CORI R. (Lothaire). — Words and Trees in “Encyclopedia of Mathematics”.

— Addison Wesley, 1983.

[F] FOATA D. — La série génératrice exponentielle dans les problèmes d’énumération. — Presses Universitaires de Montréal, 1974.

[FR] FOATA D, Riordan J. — Mappings of Acyclic and Parking Functions, Aequationes mathematicae, t. 10, 1974, p. 10–22.

[FS] FOATA D, Schützenberger M.-P. — Nombres d’Euler et permutations alternantes in “A Survey of Combinatorial Theory” (chapter 16). — J.N. Srivastava et als, eds, 1973.

[Fr] FRANCON J. — Acyclic and Parking Functions, J. of Combinatorial Theory, t. 18, 1975, p. 27–35.

[Ri] RIORDAN J. — Combinatorial Identities. — Robert E. Krieger Publishing Company, New York, 1979.

[Ro] ROSELLE. — Permutations by number of rises and successions, Proc. Amer. Math. Soc., t. 19, 1968, p. 8–16.

[W] WILF H.S. — Generatingfunctionology. — Acad. Press, 1990.