Grammaire de Ramanujan et Arbres de Cayley

Dominique DUMONT et Armand RAMAMONJISOA E.E.S. Sciences, B.P. 906, Antananarivo-101, Madagascar

Dedicace d’un Dominique a l’autre : ”Le rapporteur a qualifié le présent article de ”foatesque”. C’est, me semble-t-il, non seulement la reconnaissance d’une évidente parenté d’esprit entre les élèves de Dominique Foata, y compris chez ceux de deuxieme génération comme Armand Ramamonjisoa qui n’ont pas la chance de le connaître directement, c’est cette constatation mais c’est aussi, et surtout, le meilleur compliment que ce rapporteur pouvait faire.”

Antananarivo, le 17 Août 1995, Dominique DUMONT.

Submitted : February 25, 1995 ; Accepted : July 25, 1995

Abstract. — We study three sequences of polynomials defined as successive derivatives with respect to a differential operator associated with a grammar (one of these sequences was originally introduced by Ramanujan). Combinatorial interpretations for these polynomials are found in terms of rooted trees and graphs of mappings from [n] to [n].

Introduction

Dans [Ra], [B], Ramanujan (et B. Berndt à sa suite) a introduit une suite-double d’entiers a(n, k) donnés par une récurrence simple, qui raffinent la suite (n^{n}). Dans cet article nous donnons d’abord de nouvelles définitions calculatoires pour ces entiers et pour des raffinements analogues des suites (n^{n−1}) et (n^{n−2}) (§ 1, § 2). Puis dans une deuxième partie nous en proposons des interprétations combinatoires, en introduisant sur les arbres les notions de cadet, arête simple, arête double et le paramètre statistique “arc” (§ 3). L’énoncé fondamental (dont les autres se déduisent aisément) est constitué par la proposition 5 (§ 4), dont nous donnons deux démonstrations : une démonstration détaillée et élémentaire (§ 5), qui présente l’avantage d’interpréter du même coup la grammaire de Ramanujan introduite au § 2 et les récurrences de type triangle de Pascal sur les coefficients ; puis une démonstration plus expéditive et plus savante (§ 7), qui nous a été suggérée par J. Zeng, combinant des composés partitionnels abélien et non abélien.

1. Inversions de séries

Rappelons la proposition suivante, qu’on démontre classiquement à l’aide de la formule d’inversion de Lagrange, ou par des méthodes combinatoires ([BLL], [B], [F], [Ri], [W]) :

PROPOSITION 1. — Soit y une série formelle en x sans terme constant. Alors on a l’équivalence

(1)  x = y e^{−y} ⟺ y = x + 2^{1} \frac{x^{2}}{2!} + 3^{2} \frac{x^{3}}{3!} + ⋯ + n^{n−1} \frac{x^{n}}{n!} + ⋯

On en déduit une autre inversion de série, sous la forme de la proposition 2 suivante.

PROPOSITION 2. — Soit z une série formelle en x sans terme constant. Alors on a équivalence entre les deux relations suivantes :

(2)  x = −(1 − z) Log(1 − z) = z − \frac{z^{2}}{2} − \frac{z^{3}}{6} − \frac{z^{4}}{12} − ⋯ − \frac{z^{n}}{n (n − 1)} − ⋯
(2′)  z = x + \frac{x^{2}}{2!} + 2^{2} \frac{x^{3}}{3!} + 3^{3} \frac{x^{4}}{4!} + ⋯ + n^{n} \frac{x^{n+1}}{(n + 1)!} + ⋯

En effet, posons z = 1 − e^{−y}, y étant la solution de x = y e^{−y}. On a donc x = −(1 − z) Log(1 − z). D’autre part, en différentiant la relation y = x e^{y}, on obtient y′ = e^{y} + x e^{y}y′. Par suite,

z′ = (1 − e^{−y})′ = e^{−y}y′ = 1 + xy′ = ∑_{n≥0} n^{n} \frac{x^{n}}{n!} ,

d’où le résultat après intégration.

Cette proposition 2 est liée à un problème de développement asymptotique pour une fonction implicite, étudié par Ramanujan [Ra] [B] [H], que nous énonçons ainsi : Si x Log x = x_{0} Log x_{0} + h (h petit), développer x au voisinage de x_{0}.

Ramanujan trouve le développement suivant, avec y_{0} = 1/(1 + Log x_{0}) :

x = x_{0} + y_{0}h − (y_{0}^{3})\frac{1}{x_{0}} \frac{h^{2}}{2!} + (y_{0}^{4} + 3y_{0}^{5})\frac{1}{x_{0}^{2}} \frac{h^{3}}{3!} − (2y_{0}^{5} + 10y_{0}^{6} + 15y_{0}^{7})\frac{1}{x_{0}^{3}} \frac{h^{4}}{4!} + ⋯,

où la suite de polynômes en y_{0} est donnée par une récurrence simple (cf (4) ci-dessous). Après une légère transformation, on peut reformuler le résultat de Ramanujan de la manière suivante, où il apparaît comme une extension de la proposition 2 :

PROPOSITION 3. — On a équivalence entre les deux relations suivantes :

(3) x = \frac{z}{a} − z − (1 − z) Log(1 − z) = \frac{z}{a} − \frac{z^{2}}{2} − \frac{z^{3}}{6} − \frac{z^{4}}{12} − ⋯ − \frac{z^{n}}{n(n − 1)} − ⋯
(3′) z = ax + a^{3} \frac{x^{2}}{2!} + (a^{4} + 3a^{5})\frac{x^{3}}{3!} + (2a^{5} + 10a^{6} + 15a^{7})\frac{x^{4}}{4!} + ⋯

+ (a(n, 1)a^{n+2} + a(n, 2)a^{n+3} + … + a(n, n)a^{2n+1})\frac{x^{n+1}}{(n + 1)!} + ⋯

où les nombres de Ramanujan a(n, k) sont définis par la récurrence

(4) a(n, k) = (n − 1) a(n − 1, k) + (n + k − 1) a(n − 1, k − 1),  a(1, 1) = 1,

et sont tels que :

(5)  ∑_{1≤k≤n} a(n, k) = n^{n}.

Nous donnerons au § 2 une démonstration de la proposition 3 (dans [B], le lecteur trouvera une autre preuve d’un énoncé équivalent).

Toujours à l’aide du changement de fonction y = − Log(1 − z), nous serons conduits à démontrer l’extension suivante de l’équivalence (1).

PROPOSITION 4. — Soit y une série formelle en x sans terme constant. Alors on a équivalence entre les deux relations suivantes :

(6) x = y e^{−y} + \frac{a − 1}{a}(e^{−y} − 1) = \frac{1}{a}[y − (a + 1)\frac{y^{2}}{2!} + (2a + 1)\frac{y^{3}}{3!} − (3a + 1)\frac{y^{4}}{4!} + ⋯]
(6′) y = ax + (a^{2} + a^{3})\frac{x^{2}}{2!} + (2a^{3} + 4a^{4} + 3a^{5})\frac{x^{3}}{3!} + ⋯

+ (b(n, 0)a^{n} + b(n, 1)a^{n+1} + … + b(n, n − 1)a^{2n−1})\frac{x^{n}}{n!} + ⋯

où les nombres b(n, k) sont donnés par la récurrence

(7)  b(n, k) = (n − 1) b(n − 1, k) + (n + k − 2) b(n − 1, k − 1),  b(1, 0) = 1,

et sont tels que la somme de leur n−ième ligne vaut n^{n−1} :

(8)  ∑_{0≤k≤n−1} b(n, k) = n^{n−1}.

§ 2. Grammaire de Ramanujan

Dans tout ce qui suit, y désigne donc la série formelle solution de

(6)  x = y e^{−y} + \frac{a − 1}{a}(e^{−y} − 1),

et on considère aussi la fonction auxiliaire z = 1 − e^{−y}. En différentiant par rapport à x l’équation (6), on obtient : 1 = −y e^{−y}y′ + \frac{1}{a}e^{−y}y′, soit

(9)  y′ = (\frac{a}{1 − ay} )e^{y},

équation différentielle qui, avec la condition initiale y(0) = 0, suffit à caractériser y, et surtout conduit à un algorithme de calcul de ses coefficients, comme nous allons le voir.

Notons que (9) implique que z′ = \frac{a}{1 − ay} . Introduisons deux nouvelles fonctions auxiliaires que, pour des raisons qui apparaîtront plus loin, nous notons par les deux lettres capitales A et S :

(10)  A = z′ = \frac{a}{1 − ay}
(11)  S = \frac{1}{1 − z} = e^{y}

Calculons les dérivées de ces deux fonctions :

A′ = (\frac{a}{1 − ay} )′ = (\frac{a}{1 − ay} )^{2}y′ = (\frac{a}{1 − ay} )^{3}e^{y} = A^{3}S,

S′ = (e^{y})′ = e^{y}y′ = AS^{2}.

En résumé, on obtient le système différentiel :

(12)  \{ \begin{matrix}y′ & = & AS & y(0) = 0 \\ z′ & = & A & z(0) = 0 \\ A′ & = & A^{3}S & A(0) = a \\ S′ & = & AS^{2} & S(0) = 1 \end{matrix}

Soit D l’opérateur différentiel

D = A^{3}S \frac{∂}{∂A} + AS^{2} \frac{∂}{∂S} ·

Dans le formalisme de W. Chen [Ch], D n’est autre que l’opérateur différentiel associé à la grammaire G = {A → A^{3}S, S → AS^{2}}, définie sur l’alphabet {A, S}, et ce sont ces deux règles de réécriture que nous appelons grammaire de Ramanujan.

On a, par récurrence sur n,

(13)  \{ \begin{matrix}y^{(n+1)} & = & D^{n}(AS) \\ z^{(n+1)} & = & D^{n}(A) \\ A^{(n)} & = & D^{n}(A) \\ S^{(n)} & = & D^{n}(S) \end{matrix}

Les membres de droite sont des polynômes en A et S. Voici d’abord les premières valeurs des polynômes dérivés successifs de A :

D^{0}(A) = A
D^{1}(A) = (A^{3})S
D^{2}(A) = (A^{4} + 3A^{5})S^{2}
D^{3}(A) = (2A^{5} + 10A^{6} + 15A^{7})S^{3}
⋯
D^{n}(A) = (a(n, 1)A^{n+2} + ⋯ + a(n, k)A^{n+k+1} + ⋯ + a(n, n)A^{2n+1})S^{n}

Le terme a(n, k)A^{n+k+1}S^{n} se déduit de deux termes de la ligne précédente :

AS^{2} \frac{∂}{∂S} [a(n − 1, k)A^{n+k}S^{n−1}] + A^{3}S \frac{∂}{∂A}[a(n − 1, k − 1)A^{n+k−1}S^{n−1}],

ce qui donne la récurrence (4) annoncée plus haut :

a(n, k) = (n − 1) a(n − 1, k) + (n + k − 1) a(n − 1, k − 1).

Voici à présent les premières valeurs des polynômes dérivés successifs de AS :

D^{0}(AS) = AS
D^{1}(AS) = (A^{2} + A^{3})S^{2}
D^{2}(AS) = (2A^{3} + 4A^{4} + 3A^{5})S^{3}
⋯
D^{n−1}(AS) = (b(n, 0)A^{n} + ⋯ + b(n, k)A^{n+k} + ⋯ + b(n, n − 1)A^{2n−1})S^{n}

Le terme b(n, k)A^{n+k}S^{n} se déduit de deux termes de la ligne précédente :

AS^{2} \frac{∂}{∂S} [b(n − 1, k)A^{n+k−1}S^{n−1}] + A^{3}S \frac{∂}{∂A}[b(n − 1, k − 1)A^{n+k−2}S^{n−1}],

ce qui donne la récurrence (10) annoncée plus haut :

b(n, k) = (n − 1) b(n − 1, k) + (n + k − 2) b(n − 1, k − 1).

Voici enfin les premières valeurs des polynômes dérivés successifs de S :

D^{0}(S) = S D^{1}(S) = (A)S^{2} D^{2}(S) = (2A^{2} + A^{3})S^{3} D^{3}(S) = (6A^{3} + 7A^{4} + 3A^{5})S^{4}

⋯

D^{n−1}(S) = (c(n, 0)A^{n−1} + ⋯ + c(n, k)A^{n+k−1} + ⋯ + c(n, n − 2)A^{2n−3})S^{n}

Le terme c(n, k)A^{n+k−1}S^{n} se déduit de deux termes de la ligne précédente :

AS^{2} \frac{∂}{∂S} [c(n − 1, k)A^{n+k−2}S^{n−1}] + A^{3}S \frac{∂}{∂A}[c(n − 1, k − 1)A^{n+k−3}S^{n−1}],

ce qui donne la récurrence (14) suivante :

(14) c(n, k) = (n − 1) c(n − 1, k) + (n + k − 3) c(n − 1, k − 1).

Pour obtenir les séries y (primitive de AS), A = z′, et S, il suffit d’après la formule de Taylor formelle, de porter x = 0 dans les identités (13), ce qui, avec les conditions initiales (12), donne les trois développements suivants, dont les deux premiers étaient annoncés plus haut :

(6)  y = ax + (a^{2} + a^{3})\frac{x^{2}}{2!} + (2a^{3} + 4a^{4} + 3a^{5})\frac{x^{3}}{3!} + ⋯
(3)  z′ = \frac{a}{1 − ay} = a + a^{3}x + (a^{4} + 3a^{5})\frac{x^{2}}{2!} + (2a^{5} + 10a^{6} + 15a^{7})\frac{x^{3}}{3!} + ⋯
(15)  e^{y} = 1 + ax + (2a^{2} + a^{3})\frac{x^{2}}{2!} + (6a^{3} + 7a^{4} + 3a^{5})\frac{x^{3}}{3!} + ⋯

Les coefficients des développements sont respectivement les entiers b(n, k), a(n, k) (ces derniers introduits par Ramanujan, cf. [Ra] [B] [H]) et c(n, k). Ainsi s’achève la démonstration des proposition 3 et 4 ci-dessus.

§ 3. Descendants et cadets dans les arbres de Cayley. Paramètre “arc”

Soit (A, r) un arbre de Cayley enraciné de taille n, c’est-à-dire le couple formé d’un arbre de Cayley A de sommets {1, 2, …, n} et d’un sommet distingué r de A qu’on appelle racine de l’arbre. On oriente les arêtes de l’arbre à partir de la racine (on aurait pu convenir de l’orientation contraire, l’arbre est alors le graphe sagittal d’une fonction acyclique, au sens de [F]). Pour distinguer la racine de l’arbre, on convient d’ajouter une arête (⟶ r).

On note A_{n}(→ r) l’ensemble des arbres A de taille n enracinés en r et A_{n}(→ .) = ⋃_{r∈[n]} A_{n}(→ r) la réunion de ces ensembles, de cardinal n^{n−1} (cf. [BLL], [F], [W]).

Soit A un élément de A_{n}(→ .), de racine r. On convient que l’arête (⟶ r) fait partie des arêtes de l’arbre. De ce fait, l’arbre enraciné possède n sommets et n arêtes.

Soit j un sommet fixé dans l’arbre A. Si un sommet k est tel que le chemin joignant r à k passe par j, on dit qu’il appartient à la descendance du sommet j. Cette descendance est un sous-arbre enraciné en j et on la note A(j). En particulier, si j est pendant, A(j) se réduit à j lui-même. En revanche, A(r) n’est autre que A tout entier (“en revanche” suppose ici qu’on se trouve dans un cas où n > 1).

Le plus petit sommet de A(j), noté c(j), s’appelle le cadet de la descendance du sommet j.

Par ailleurs le sommet j possède un père et un seul, c’est le sommet i qui est l’origine de l’unique arête dont j est une extrémité (Si j = r, on convient que ce père est 0). On distingue deux cas :

• Si c(j) > i, on dit que l’arête de i à j est simple, on la note dorénavant (i ⟶ j) et on dessine un arc allant de i vers j.

• Si c(j) < i, on dit que l’arête de i à j est double, on la note dorénavant (i ⟹ j) et on dessine deux arcs allant de i vers j.

Remarques.— Si une arête de i à j est décroissante (telle que i > j), alors elle est double. Si elle est croissante et si j est un sommet pendant, alors elle est simple. Mais si j n’est pas pendant, il peut se produire qu’une arête croissante soit double, il suffit qu’un descendant de j soit < i. Notons que l’arête (⟶ r) est toujours simple.

Si A est un arbre enraciné, on note som(A) le nombre de ses sommets. Si A ∈ A_{n}(→ .), som(A) = n). On note s(A) le nombre des arêtes simples et d(A) le nombre des arêtes doubles, et arc(A) le nombre des arcs de A. On a donc, pour un arbre de Cayley enraciné :

\begin{matrix}s(A) + d(A) = n, \\ s(A) + 2d(A) = arc(A). \end{matrix}

On considère aussi l’ensemble A_{n} des arbres de Cayley proprement dits (non enracinés), de cardinal n^{n−2}. Un arbre de Cayley A possède n sommets et n − 1 arêtes. Pour que les notions introduites ici (descendances, cadets) gardent un sens, nous orientons les arêtes de l’arbre à partir de la racine 1, mais nous supprimons l’arête (⟶ 1), parce qu’elle est invariable quand A décrit A_{n}, tandis que l’arête (⟶ r) varie quand A décrit A_{n}(→ .). Les autres définitions sont inchangées. Pour un arbre de Cayley A, on a donc

\begin{matrix}s(A) + d(A) = n − 1, \\ s(A) + 2d(A) = arc(A). \end{matrix}

§ 4. Enoncés combinatoires

Ces préliminaires étant posés, nous pouvons commencer par interpréter les relations de récurrence définissant deux des trois triangles de nombres définis plus haut.

PROPOSITION 5. — Les séries y et e^{y} énumèrent les arbres de Cayley enracinés (resp. les arbres de Cayley) selon le paramètre arc (nombre des arcs) :

(16)  y = ax + (a^{2} + a^{3})\frac{x^{2}}{2!} + ⋯ + ( ∑_{A∈A_{n}(→.)} a^{arc(A)})\frac{x^{n}}{n!} + ⋯

(17)  e^{y} = 1 + ax + (2a^{2} + a^{3})\frac{x^{2}}{2!} + ⋯ + ( ∑_{A∈A_{n+1}} a^{arc(A)})\frac{x^{n}}{n!} + ⋯

COROLLAIRE. — Le coefficient c(n, k) est le nombre d’arbres de Cayley de taille n + 1 possédant k arêtes doubles et b(n, k) est le nombre d’arbres de Cayley enracinés de taille n possédant k arêtes doubles.

§ 5. Interprétation combinatoire de la grammaire de Ramanujan et des récurrences (7) et (14).

Convention.— Soit A un arbre enraciné de taille n, et soit un sommet fixé i. Soit k = p + q son degré, c’est-à-dire le nombre des arêtes issues de i, comprenant p arêtes doubles et q arêtes simples. On définit un ordre sur ces k arêtes qui est l’ordre croissant des cadets des fils de i (non l’ordre croissant des fils eux-mêmes). On dessine donc en tournant dans le sens trigonométrique, d’abord les p arêtes doubles (i ⟹ j_{1}), (i ⟹ j_{2}), …, (i ⟹ j_{p}), puis les q arêtes simples (i ⟶ j_{p+1}), …, (i ⟶ j_{k}), de telle sorte que

c(j_{1}) < c(j_{2}) < … < c(j_{p}) < i < c(j_{p+1}) < … < c(j_{k}).

Notons que si toutes les arêtes sont simples (p = 0), alors c(i) = i. Si au contraire p > 1, alors c(i) = c(j_{1}). A présent, nous allons définir la restriction Ā d’un arbre enraciné A de taille n comme un arbre enraciné Ā de taille n − 1, et inversement les divers prolongements d’un arbre enraciné B de taille n − 1, c’est-à-dire la construction de ses antécédents par l’application restriction.

Restrictions. On distingue trois cas, selon le degré k du sommet n (notons qu’avec les conventions ci-dessus, on a toujours p = k et q = 0, car n est le sommet maximum). On désigne par i le père de n :

a) On suppose que le sommet n est pendant (k = 0). Alors Ā s’obtient à partir de A en supprimant simplement le sommet n et l’arête (i ⟶ n) qui conduit à n. Le reste est inchangé.

b) On suppose que k = 1, le sommet n a un fils unique j. Alors pour obtenir Ā à partir de A, on supprime n et (n ⟹ j). Il est clair que c(n) = c(j). Si c(n) > i, on remplace (i ⟶ n) par (i ⟶ j) (si n est racine, on remplace (⟶ n) par (⟶ j), et j devient racine). Si c(n) < i, on remplace (i ⟹ n) par (i ⟹ j). Le reste est inchangé.

c) On suppose que k ≥ 2, et on pose d = k − 1. Soient j_{1}, j_{2}, …, j_{d}, j_{k} les fils de n, rangés de telle sorte que les cadets respectifs aillent en croissant :

c(j_{1}) < c(j_{2}) < … < c(j_{d}) < c(j_{k}) < n.

Sommairement, la règle de construction de Ā est la suivante : on remplace n par son fils j_{k} (celui dans la descendance duquel se trouve le plus grand cadet). Plus précisément :

• on supprime le sommet n;

• Si c(n) > i, on remplace (i ⟶ n) par (i ⟶ j_{k}) (si n est racine, on remplace (⟶ n) par (⟶ j_{k}), et j_{k} devient racine). Si c(n) < i, on remplace (i ⟹ n) par (i ⟹ j_{k}) ;

• On supprime la dernière arête issue de n, à savoir (n ⟹ j_{k}), et on remplace n par son fils j_{k} dans les autres arêtes issues de n, qui deviennent donc (j_{k} ⟹ j_{1}), (j_{k} ⟹ j_{2}), …, (j_{k} ⟹ j_{d}). Ces arêtes sont doubles car les d premiers cadets sont inférieurs à c(j_{k}), lequel est ≤ j_{k}. Le reste est inchangé.

Rappelons que c(j_{k}) = j_{k} dans le cas où toutes les arêtes issues de j_{k} sont simples (en particulier dans le cas où j_{k} est pendant). Dans le cas contraire, il existe m arêtes doubles issues de j_{k}, avec m ≥ 1, que nous notons (j_{k} ⟹ k_{1}), …, (j_{k} ⟹ k_{m}), et on a c(j_{k}) = c(k_{1}) < j_{k}. Ces arêtes doubles se rangent, dans l’arbre Ā, après les d premières arêtes récupérées du sommet n, car on a :

c(j_{1}) < c(j_{2}) < ⋯ < c(j_{d}) < c(j_{k}) = c(k_{1}) < c(k_{2}) < ⋯

Exemple.— Dans la figure ci-dessous, l’arbre de gauche est obtenu par restriction de type (c) à partir de l’arbre de droite :

5  6 ⟹ 5
⇑  ⇑
⟶ 3 ⟹ 6 ⟹ 4 ⟹ 2  ⟶ 3 ⟹ 8 ⟹ 4 ⟹ 2
⇓  ⇓
7  7
⇓  ⇓
1  1

Prolongements. On distingue de même trois types de prolongements d’un arbre enraciné B de taille n − 1 vers un arbre enraciné de taille n :

a) Prolongement par dérivation d’un sommet de B. On choisit un sommet quelconque i de B, on ajoute le sommet n et l’arête (i ⟶ n). Il est clair que sur l’arbre A ainsi obtenu le sommet n est pendant, et que A redonne B par restriction de type a). Notons que dans le décompte des sommets et arêtes, l’arbre A possède un sommet de plus et une arête simple de plus que l’arbre B.

b) Prolongement par dérivation simple d’une arête de B. On choisit une arête quelconque de B, simple ou double, à savoir (i ⟶ j), ou (⟶ r), ou (i ⟹ j). On la remplace par (i ⟶ n) dans le premier cas, par (⟶ n) dans le deuxième cas, par (i ⟹ n) dans le troisième cas. On ajoute (n ⟹ j). Il est clair que sur l’arbre A ainsi obtenu, le sommet n est de degré 1, et que A redonne B par restriction de type b). Notons que dans le décompte des sommets et arêtes, l’arbre A possède un sommet de plus et une arête double de plus que l’arbre B.

c) Prolongement par dérivation composée d’une arête double de B. On choisit une arête double quelconque de B, à savoir (i ⟹ j_{d}). L’indice d signifie qu’elle est la d−ième arête issue de i, avec d ≥ 1. On remplace ces d premières arêtes (i ⟹ j_{1}), (i ⟹ j_{2}), …, (i ⟹ j_{d}) par (n ⟹ j_{1}), (n ⟹ j_{2}), …, (n ⟹ j_{d}), puis on ajoute une arête (n ⟹ i). Le reste est inchangé, en particulier les arêtes suivantes issues de i sont inchangées. On obtient ainsi un arbre A dont le degré du sommet n est d + 1, donc est ≥ 2. En outre, le cadet c(i) de i dans A est supérieur à c(j_{d}), donc parmi les fils de n, i est celui qui a le plus grand cadet. Donc A redonne B par restriction de type c). Notons que dans le décompte des sommets et arêtes, l’arbre A possède un sommet de plus et une arête double de plus que l’arbre B.

Exemple.— Dans la figure ci-dessus, l’arbre de droite est obtenu à partir de l’arbre de droite en procédant à une dérivation composée de l’arête (6 ⟹ 4).

Démonstration de la proposition 5.— Elle est vraie pour n = 1, car l’unique arbre enraciné de taille 1 est A = (⟶ 1), pour lequel som(A) = 1 et arc(A) = 1 (on compte l’arête simple (⟶ 1)), et qui correspond donc au monôme as.

A présent, supposons la proposition vraie pour n − 1. Le prolongement d’un arbre B consiste :

• soit à choisir un sommet et à le dériver, ce qui revient à remplacer ce sommet i par un ensemble comportant le sommet i lui-même, un nouveau sommet n, et une nouvelle arête (i ⟶ n), donc pour le monôme à remplacer une occurrence de la lettre s par as^{2}.

• soit à choisir un arc et à dériver l’arête qui lui correspond. Ainsi chaque arête simple est choisie une fois, pour un prolongement de type b), et chaque arête double deux fois, pour un prolongement de type b) et un de type c). Or dans les prolongements de type b) et c), la dérivation d’une arête revient dans le décompte à créer un nouveau sommet n et une nouvelle arête double, donc deux nouveaux arcs. L’arête dérivée, simple ou double, est remplacée. Pour le monôme, cela correspond au remplacement d’un arc par un ensemble comprenant cet arc même, un nouveau sommet et deux nouveaux arcs, donc par le remplacement d’une occurrence de la lettre a par a^{3}s.

En résumé, la dérivation d’un arc se traduit par D(a) = a^{3}s et la dérivation d’un sommet par D(s) = as^{2}, ce qui explique le choix des lettres A et S dans les définitions (10) et (11). En outre, on a, par récurrence sur n :

D^{n−1}(as) = ∑_{A∈A_{n}(→.)} a^{arc(A)}s^{som(A)}.

Les coefficients du polynôme énumérateur membre de droite siont donc les entiers b(n, k), ce qui démontre la première identité de la proposition 5.

La démonstration de la deuxième identité est identique, à la différence près qu’il faut supprimer l’arête (⟶ 1). Le monôme associé à l’arbre (1) est donc s, le monôme associé à l’arbre de taille 2, à savoir (1 ⟶ 2), est donc D(s) = as^{2}, et ainsi de suite.

On peut donner du corollaire une démonstration directe consistant à interpréter la récurrence (7). Pour construire les arbres de Cayley A enracinés de taille n possédant k arêtes doubles on doit :

• soit partir d’un arbre B de taille n − 1 possédant k arêtes doubles et dériver l’un de ses n − 1 sommets. On obtient ainsi les (n − 1) b(n − 1, k) arbres de Cayley A enracinés de taille n possédant k arêtes doubles dans lesquels le sommet n est pendant.

• soit partir d’un arbre B de taille n − 1 possédant k − 1 arêtes doubles et faire la dérivation simple de l’une de ses n − 1 arêtes. On obtient ainsi les (n − 1) b(n − 1, k − 1) arbres de Cayley A enracinés de taille n possédant k arêtes doubles dans lesquels le sommet n est de degré 1.

• soit partir d’un arbre B de taille n − 1 possédant k − 1 arêtes doubles et faire la dérivation composée de l’une de ses k − 1 arêtes doubles. On obtient ainsi les (k − 1) b(n − 1, k − 1) arbres de Cayley A enracinés de taille n possédant k arêtes doubles dans lesquels le sommet n est de degré > 1.

En rassemblant les trois cas, on aboutit à la récurrence. La preuve est analogue pour les arbres non enracinés.

§ 6. Applications de [n] dans [n] et interprétation des entiers a(n, k)

Rappels (sur lesquels le lecteur peut se référer à [F]).— Soit F_{n} l’ensemble des applications f de l’ensemble [n] = {1, 2, …, n} dans lui-même, qui est de cardinal n^{n}. On représente f par (et on l’identifie à) son graphe sagittal G_{f}, où une arête orientée joint i à j si et seulement si j = f(i). A chaque sommet i on associe la trajectoire T (i) des itérés de i par f, ou descendants, soit

T (i) = {i, f(i), f^{2}(i) = f(f(i)), f^{3}(i) = f(f(f(i))), …}.

S’il existe k ≥ 1 tel que f^{k}(i) = i, alors le sommet i est dit récurrent. On note R_{f} l’ensemble des sommets récurrents de f et T_{f} = [n] \ R_{f} l’ensemble des sommets transitoires pour f. On montre que f, restreinte à R_{f}, est une permutation σ_{f} de R_{f} sur lui-même, les trajectoires des sommets récurrents étant les cycles de cette permutation.

Si i est transitoire, on montre qu’en décrivant T (i) on trouve nécessairement des sommets récurrents (car la trajectoire ne peut être infinie, l’ensemble [n] étant fini). Soit r = f^{k}(i) le premier sommet récurrent dans T (i), en ce sens que l’entier k ≥ 1 est le plus petit entier tel que f^{k}(i) soit récurrent. Notons que les sommets suivants de T (i) (f(r), etc.) sont alors tous récurrents et forment le cycle T (r) auquel appartient r.

Soit φ l’application i ↦ φ(i) = r, où r est le premier sommet récurrent de T (i). Cette application φ est définie sur [n] tout entier et à valeurs dans R_{f}. En particulier si r est récurrent, il est clair que φ(r) = r. Etant donné un sommet récurrent r, on note A(→ r) le sous-graphe de G_{f} dont l’ensemble des sommets est φ^{−1}(r). On montre que A(→ r) est un arbre de Cayley enraciné en r, avec la convention qu’on oriente les arêtes vers la racine (et non plus à partir de la racine comme dans notre § 3).

On note π_{f} l’ensemble des arbres A(→ r), r décrivant R_{f}, autrement dit π_{f} correspond à la donnée de la partition de [n] associée à l’application φ et d’un arbre enraciné sur chaque bloc de cette partition. On montre que le triplet (R_{f}, σ_{f}, π_{f}) caractérise l’application f (le triplet permet de construire toutes les arêtes du graphe G_{f}).

Définitions.— Soit f une application de [n] dans [n]. Etant donné un sommet i, on note A(i) l’ascendance de i, c’est-à-dire l’ensemble des sommets k tels que i soit élément de T (k).

Dans le cas où i est un sommet transitoire, cette notion correspond exactement, à l’orientation près, à la définition de A(i) dans le paragraphe précédent : si φ(i) = r, alors i est un sommet de A(→ r), et A(i) est un sous-arbre de Cayley de A(→ r) enraciné en i.

Dans le cas où i = r est récurrent, A(r) se compose du cycle T (r) et de tous les arbres de Cayley enracinés sur les sommets de ce cycle (parmi lesquels figure A(→ r)), autrement dit A(r) n’est autre qu’une composante connexe toute entière du graphe G_{f}.

Le plus petit sommet de A(i), noté c(i), s’appelle le cadet de i.

Soit (i, j) une arête du graphe G_{f} (autrement dit f(i) = j).

• Si c(i) > j, on dit que l’arête (i, j) est simple, on la note dorénavant (i ⟶ j) et on dessine un arc allant de i vers j.

• Si c(i) ≤ j, on dit que l’arête (i, j) est double, on la note dorénavant (i ⟹ j) et on dessine deux arcs allant de i vers j.

Remarques.— Toute arête récurrente, c’est-à-dire toute arête d’un cycle T (r), est double, car r ∈ A(r), donc c(r) ≤ r.

Pour une arête transitoire, c’est-à-dire une arête d’un arbre A(→ r), la définition se confond avec celle du paragraphe précédent. La différence est que l’arbre A(→ r) ne comporte plus l’arête simple (⟶ r), le repérage de la racine r s’opérant dorénavant à l’aide du branchement sur le cycle de σ_{f}. De ce fait, il se peut que toutes les arêtes de A(→ r) soient doubles (par exemple si elles sont toutes croissantes).

On désigne par d(f) le nombre des arêtes doubles du graphe G_{f} et par arc(f) le nombre de ses arcs lorsqu’on remplace chaque arête simple par un arc et chaque arête double par deux arcs. Par suite, arc(f) = n + d(f).

Exemple.— Pour l’application suivante f : [14] → [14], on a d(f) = 10 et arc(f) = 24 :

14  3  9
↓  ⇓  ⇓
4 ⟹ 10 ⟶ 1 ⟹ 7 ⟵ 13  6 \overrightarrow{⟸} 12
⇑  ⇑  ⇓  ↑
5  2 ⟸ 8  11

Lorsqu’on dénombre les applications selon ce paramètre, on obtient le résultat suivant, dont nous donnerons deux énoncés équivalents :

PROPOSITION 6. — 1) La lettre y désignant toujours la série formelle introduite dans les propositions 4 et 5, on a

\frac{1}{1 − ay} = 1 + a^{2}x + (a^{3} + 3a^{4})\frac{x^{2}}{2!} + (2a^{4} + 10a^{5} + 15a^{6})\frac{x^{3}}{3!} + ⋯ + ( ∑_{f∈F_{n}} a^{arc(f)})\frac{x^{n}}{n!} + ⋯

2) Le nombre de Ramanujan a(n, k) est, pour 1 ≤ k ≤ n, le cardinal de l’ensemble des applications f : [n] ↦ [n] possédant k arêtes doubles, autrement dit des applications f pour lesquelles il existe k sommets i tels que le plus petit ascendant de i soit ≤ f(i).

D’après la proposition 3 et la définition ci-dessus de arc(f), les deux énoncés sont clairement équivalents. Le lecteur pourra sans peine mettre au point une démonstration du second énoncé analogue à celles du § 4, et trouvera une démonstration du premier énoncé dans le paragraphe suivant.

§ 7. Démonstration directe des propositions 5 et 6 par composés partitionnels

Une partie de ce paragraphe, plus précisément l’interprétation combinatoire de l’équation différentielle (9) qui conduit à une démonstration directe de la proposition 5, nous a été suggérée par Jiang Zeng.

Nous modifions légèrement les notations :

• A_{n+1} désigne ici l’ensemble des arbres de taille n + 1 ayant pour sommets les éléments de [0, n], les arêtes étant orientées à partir de 0.

• A_{n}(→ .) désigne comme précédemment l’ensemble des arbres enracinés de taille n, c’est-à-dire des couples (A, r) formés d’un arbre A sur [1, n] et d’un sommet distingué r ∈ [1, n] repéré par une arête (⟶ r).

• convenons en outre de noter A_{n+1}^{0}(→ .) l’ensemble des arbres enracinés de taille n+1, ayant pour sommets les éléments de [0, n], et dont le sommet 0 est une feuille (i.e. de degré sortant nul).

Si n = 0, l’ensemble A_{1}^{0}(→ .) se réduit à l’arbre (⟶ 0).

Si n ≥ 1, la racine r est distincte de 0, le sommet 0 a un père appelé sortie, noté s. Un élément de A_{n+1}^{0}(→ .) correspond donc à la donnée d’un triplet (A, r, s), où A est un arbre sur [n], et où r et s deux sommets distingués (non nécessairement distincts) de A, r étant la racine, repérée par une arête (⟶ r), et s la sortie, prolongée par une arête (s ⟹ 0). (C’est un vertébré dans la terminologie (due à A. Joyal) de la théorie de espèces, voir [BLL], [L]). Par suite :

card[A_{n+1}^{0}(→ .)] = n^{n}.

Nous définissons à présent les séries énumératrices Y (x, a)), S(x, a) et A(x, a) suivantes (par abus de notation, dans ces sommations les arbres sont toujours notés A, et non (A, r) ou (A, r, s)) :

Y (x, a) = ∑_{n≥1} ( ∑_{A∈A_{n}(→.)} a^{arc(A)})\frac{x^{n}}{n!}

S(x, a) = ∑_{n≥0} ( ∑_{A∈A_{n+1}} a^{arc(A)})\frac{x^{n}}{n!}
A(x, a) = ∑_{n≥0} ( ∑_{A∈A_{n+1}^{0}(→.)} a^{arc(A)})\frac{x^{n}}{n!}

Dans ces conditions, on a le résultat suivant :

PROPOSITION 7. — Les séries Y, S et A ainsi définies satisfont les identités suivantes :

(i) S(x, a) = exp(Y (x, a))

(ii) A(x, a) = \frac{a}{1 − aY (x, a)}

(iii) \frac{d}{dx}Y (x, a) = A(x, a)S(x, a).

Par suite, Y (x, a) s’identifie avec la série formelle y introduite dans la proposition 4 et solution de l’équation différentielle (9).

Démonstration.— Pour démontrer (i), Considérons un élément A de A_{n+1}. En supprimant le sommet 0, on obtient une partition π de [n] en k blocs, et un arbre enraciné A_{j} sur chaque bloc B_{j} de cette partition (1 ≤ j ≤ k).

Exemple.— Dans l’exemple du vertébré ci-dessous, de racine r = 8 et de sortie s = 6, on obtient la partition π = 1, 4, 5, 10, 14/2/3, 7, 13/6, 11/8/9, 12, six arbres de racines respectives 1, 2, 7, 6, 8, 12, et l’ordre linéaire 8, 2, 1, 7, 12, 6 sur ces racines.

14  5
↑  ⇑
⟶ 8 ⟹ 2 ⟹ 1 ⟶ 10 ⟹ 4
⇓
3 ⟸ 7 ⟹ 12 ⟹ 6 ⟹ 0
↓  ⇓  ↓
13  9  11

14  5  3
↑  ⇑  ⇑
⟶ 1 ⟶ 10 ⟹ 4  ⟶ 2  ⟶ 7 ⟶ 13
⟶ 6 ⟶ 11  ⟶ 8  ⟶ 12 ⟹ 9

En outre, on a :

som(A) − 1 = n = ∑_{j=1}^{k} som(A_{j}) ; arc(A) = ∑_{j=1}^{k} arc(A_{j}).

On en déduit l’identité (i) par composé partitionnel abélien [F].

Pour démontrer (ii), étant donné un élément A de A_{n+1}^{0}(→ .), avec n ≥ 1, considérons le chemin reliant la racine r au sommet 0, soit r_{1} = r, r_{2}, …, r_{l} = s, r_{l+1} = 0, chemin de longueur l ≥ 1, dont toutes les arêtes sont doubles puisque 0 est dans la descendance de chaque sommet de ce chemin. On supprime le sommet 0, l’arête (s ⟹ 0), et on remplace chaque arête double r_{j} ⟹ r_{j+1} (où 1 ≤ j ≤ l − 1) par une arête simple repérante (sans origine) ⟶ r_{j+1}. On obtient ainsi une partition π en l blocs, l arbres enracinés A_{1}, A_{2}, …, A_{l} de racines r_{1}, r_{2}, …, r_{l}, et un ordre total sur ces racines (i.e. une permutation, comme mot linéaire).

Exemple.— Dans l’exemple ci-après, on obtient la partition π = 1236/4/57, trois arbres de racines respectives 3, 4, 5, et l’ordre 4, 5, 3 sur ces racines.

6  6
↑  ↑
⟶ 4 ⟹ 5 ⟹ 3 ⟹ 0  ⟶ 3  ⟶ 4  ⟶ 5
↓  ⇓  ⇓  ↓
7  1 ⟶ 2  1 ⟶ 2  7

En outre, on a :

som(A) − 1 = n = ∑_{j=1}^{l} som(A_{j}) ; arc(A) = (l + 1) + ∑_{j=1}^{l} arc(A_{j}).

On en déduit l’identité (ii) par composé partitionnel non abélien [F]. Plus précisément, le terme a^{l+1}(Y (x, a))^{l} est la série énumératrice restreinte aux éléments de A_{n+1}^{0}(→ .) pour lesquels la distance de la racine à 0 est égale à l.

Remarque.— Si au lieu de prendre un ordre linéaire sur les racines r_{1}, r_{2}, …, r_{l}, on définit une permutation de ces racines décomposée en cycles, on obtient alors un élément f de F_{n} et on redémontre la proposition 6 (Notons que f possède un arc de moins que l’arbre enraciné A obtenu par l’ordre linéaire). Dans l’exemple ci-dessus, si l’on prend la permutation σ = (8, 2, 1, 7)(12, 6), qui correspond à l’ordre linéaire 8, 2, 1, 7, 12, 6 par la transformation fondamentale, on retrouve l’endo-function qui nous a servi d’exemple plus haut (le sens des flêches est simplement inversé à partir des racines).

Pour démontrer (iii), considérons un arbre A enraciné de taille n + 1, de sommets [0, n], dont r est la racine (notons qu’on peut avoir r = 0). Nous partitionnons le graphe A en deux sous-graphes : l’ascendance large de 0, notée Asc, et la descendance stricte de 0, notée Desc : le sous-graphe Desc (éventuellement vide) est A(0) \ {0}, à savoir la descendance de 0 moins 0 lui-même, c’est donc un composé partitionnel abélien d’arbres enracinés. Asc est le sous-graphe complémentaire de Desc dans A, c’est donc un arbre enraciné dans lequel le sommet 0 est pendant.

Exemple.— Voici un arbre enraciné sur [0, 9], et les sous-graphes Asc et Desc correspondants :

6  3 ⟶ 8 ⟹ 4  6  ⟶ 3 ⟶ 8 ⟹ 4
↑  ↑  ↑
⟶ 5 ⟹ 9 ⟹ 0 ⟶ 4 ⟹ 2  ⟶ 5 ⟹ 9 ⟹ 0  ⟶ 4 ⟹ 2
↓
1  ⟶ 1

On en déduit l’identité (iii) par convolution binomiale des séries A(x, a) et S(x, a).

Table des coefficients.

k  1  2  3  4  5  6
n  n^{n}
1  1  1
2  1  3  4
3  2  10  15  27
4  6  40  105 105  256
5  24 196 700 1260 945  3125
6  120 1148 5068 12600 17325 10395  46656

table des nombres a(n, k)

a(n, k) = (n − 1) a(n − 1, k) + (n + k − 1) a(n − 1, k − 1)

k  0  1  2  3  4  5
n  n^{n−1}
1  1  1
2  1  1  2
3  2  4  3  9
4  6  18 25  15  64
5  24 96 190 210 105  625
6  120 600 1526 2380 2205 945  7776

table des nombres b(n, k)

b(n, k) = (n − 1) b(n − 1, k) + (n + k − 2) b(n − 1, k − 1)

k  0  1  2  3  4  5
n  n^{n−2}
1  1  1
2  1  1
3  2  1  3
4  6  7  3  16
5  24 46  40  15  125
6  120 326 430 315 105  1296
7  720 2556 4536 4900 3150 945  16807

table des nombres c(n, k)

c(n, k) = (n − 1) c(n − 1, k) + (n + k − 3) c(n − 1, k − 1)

Bibliographie

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

[B] BERNDT B.C. — Ramanujan’s Notebooks, Part I, chap. 3 : Combinatorial Analysis and Series Inversions, p. 80-84. — Springer Verlag, 1985.

[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.

[F] FOATA D. — La série génératrice exponentielle dans les problèmes d’énumération.

— Presses Universitaires de Montréal, 1974.

[H] HOWARD F.T. — Explicit formulas for numbers of Ramanujan, Fibonacci Quarterly, t. 24, 1986, p. 168–175.

[L] LABELLE J. — Applications diverses de la théorie combinatoire des espèces de structures, Ann. Sci. Math. Québec, t. 7, 1983, p. 59–94.

[Ra] RAMANUJAN S. — Notebooks, vol. 1, chap. II, p. 35-36. — Tata Institute of Fundamental Research, Bombay, 1957.

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

[W] WILF H. — Generatingfunctionology. — Academic Press, 1990.