JOURNÉES SUR LES MÉTHODES EN MATHÉMATIQUES

Institut Henri Poincaré, Paris 2–3 avril 2003

UNE MÉTHODE COMBINATOIRE POUR L’ÉTUDE DES FONCTIONS SPÉCIALES

Dominique FOATA (Strasbourg)

R^{}ÉSUM^{}É. — La méthode du composé partitionnel, introduite en mathématiques combinatoires dans les années soixante-dix, a permis d’établir de nombreuses identités classiques sur les fonctions spéciales. On décrit ici cette méthode et l’on montre comment elle s’est écartée radicalement des méthodes utilisées jusque là en analyse.

ABSTRACT. — The “composé partitionnel” method that was introduced in Combinatorial Mathematics in the seventies was used to derive several classical identities on Special Functions. It is shown how the method, which is further described below, has moved away altogether from the other methods traditionally used in analysis.

Au cours des ces journées, Michel Serfati nous a aimablement demandé de mettre en lumière les méthodes qui nous paraissent essentielles dans le développement présent de notre propre spécialité mathématique. Vaste programme pour la Combinatoire ! Donner, en effet, un aperçu de toutes les méthodes mises au point dans cette discipline aujourd’hui serait une tâche impossible, tant formidable a été son essor dans la seconde moitié du vingtième siècle.

Pour mesurer cette explosion, je me suis tourné vers le serveur Math-Science de la Société Américaine de Mathématique et retenu les noms des revues mentionnant le nom “Combinatorics” ou celui de “Discrete”. Les premières revues spécialisées dans ce domaine (comme dans les autres domaines des mathématiques) sont apparues au milieu des années soixante. Auparavant, les mathématiciens publiaient dans des revues, dites généralistes, essentiellement éditées par les sociétés mathématiques des différents pays.

1980 Mathematics Subject Classification, Primary 05A15 ; Secondary 33A65.

Key words and phrases. Composé partitionnel, exponential formula, Hermite polynomials, Mehler formula, involutionary graphs.

Mots clés. Composé partitionnel, formule exponentielle, polynômes d’Hermite, formule de Mehler, graphes involutionnaires.

DOMINIQUE FOATA

Le tableau de la Fig. 1 reproduit, pour chaque année, le nombre de revues spécialisées en combinatoire. La courbe montrant cette explosion est encore plus parlante. On constate que le phénomène explosif est encore dans sa phase ascendante. On devrait tout de même atteindre prochainement le point d’inflexion, les phénomènes humains, souvent exponentiels à leurs débuts, suivent à leur maturité une courbe logistique. L’édition des revues spécialisées n’y échappera pas.

Notons que les deux premières revues de combinatoire qui sont apparues, à savoir en 1966, sont le Journal of Combinatorial Theory. Series A et Series B, lorsque la société Academic Press a édité les revues aujourd’hui bien connues, comme le Journal of Algebra, le Journal of Number Theory, …

année  1966 1976 1986 1996 2002

No. revues Combin. 2 5 15 27 41

Nombre de revues de Combinatoire publiées

[figure: 1970; 1975; 1980; 1985; 1990; 1995; 2000; 10; 20; 30; 40]

Fig. 1

MÉTHODE COMBINATOIRE POUR LES FONCTIONS SPÉCIALES

Dresser donc le catalogue des méthodes est une tâche impossible. On peut, à la rigueur, comme l’avait fait magistralement le regretté Gian-Carlo Rota [Ro96], faire le point sur l’état actuel de la discipline. Pour s’en tenir aux méthodes, qu’il faut bien décrire avec quelques détails, on est amené à faire un choix, forcément réducteur et partial. C’est ce que je me propose de faire. Je vais ainsi parler d’une technique combinatoire, popularisée dans les années 70-80, qui a révolutionné la manière d’établir de nombreuses identités sur les fonctions spéciales et montrer comment cette approche s’écarte fondamentalement des méthodes classiques utilisées en analyse.

Les polynômes orthogonaux hypergéométriques (Hermite, Laguerre, Jacobi, Meixner, …), tout particulièrement, satisfont des identités dites remarquables, qui sont indispensables à l’analyste. Pour démontrer ces identités, on utilise les techniques classiques de l’analyse complexe, représentation intégrale, manipulation des séries, …, en faisant appel à des formules closes d’intégrales ou de sommation des séries. Le fait d’obtenir au bout d’un calcul, même élégant, une expression close, tient souvent du miracle. Anticipons sur ce qui va suivre et invitons le lecteur à regarder l’identité (1.5), dite de Mehler, qui donne une expression “close” pour la série exponentielle des produits de deux polynômes d’Hermite. Si l’on prend le produit de trois polynômes, plus aucune formule manipulable ne peut être obtenue, mais si l’on prend un produit bien particulier (voir (1.6)), la sommation est possible, comme nous allons l’expliquer.

L’approche combinatoire se veut justement de donner une explication à ce miracle. En effet, les fonctionnelles de ces polynômes classiques sont très particulières, ou “spéciales” et les polynômes ont des coefficients rationnels, souvent même entiers et mieux encore entiers positifs. Si on fait apparaître ces coefficients comme des compteurs ou des valeurs prises par des statistiques définies sur des structures discrètes, ayant de bonnes propriétés géométriques, il s’agit d’utiliser cette géométrie pour montrer que les deux membres de l’identité sont simplement deux comptages obtenus par deux voies différentes. L’identité est alors une banale conséquence de cette étude géométrique.

Si le modèle trouvé pour ces structures discrètes est suffisamment riche, il fournit aussi des extensions, que les analystes à leur tour sont susceptibles d’utiliser. Mon but est d’illustrer cette démarche avec l’étude des polynômes d’Hermite et de certaines identités les concernant.

Dans le prochain paragraphe, on trouve les éléments de base sur les polynômes d’Hermite, ainsi que les deux identités qui sont étudiées plus particulièrement, celle de Mehler et son extension multilinéaire. Au paragraphe 2, est donné un aperçu sur les méthodes utilisées en analyse pour établir l’identité de Mehler.

Avec les paragraphes suivants, on entre dans l’étude combinatoire. On vérifie, tout d’abord, que les polynômes d’Hermite sont les fonctions génératrices des involutions des intervalles [ n] = {1, 2, …, n} par un certain poids. On constate, ensuite, que la formule de Mehler et son extension multilinéaire sont de la forme a = exp b, où a et b sont des séries.

Il s’agit alors, lorsque b est interprétée comme la fonction génératrice de certaines structures, de montrer que a est la fonction génératrice d’autres structures liées aux précédentes. Une étude combinatoire de l’identité exponentielle a = exp b est ainsi nécessaire ; elle est faite au paragraphe 4. On donne ensuite la démonstration combinatoire de la formule de Mehler. Cette approche combinatoire suggère une extension multilinéaire naturelle traitée au paragraphe 6. Nous terminons par quelques remarques et références.

L’esquisse des démonstrations analytiques données au paragraphe 2 peut laisser croire que celles-ci sont concises. C’est vrai, pour la plupart. N’oublions pas, cependant, qu’elles reposent sur tout un savoir-faire antérieur, qui fait partie de la culture du mathématicien. Si cette culture englobait aussi les aspects combinatoires sur les comptages de permutations et sur l’identité exponentielle, la démonstration de la formule de Mehler (1.5) donnée ici serait absorbée par tout auditoire à l’aide de deux transparents superposés ! Force est donc de donner des éléments de base, comme fait dans les paragraphes 3 et 4, mais ceux-ci prennent de la place !

1. Les polynômes d’Hermite

Ces polynômes, notés (H_{n}(x)) (n ≥ 0), qui sont orthogonaux par rapport à la fonctionnelle e^{−x^{2}/2} sur ] − ∞, +∞[, peuvent être définis à l’aide de leur fonction génératrice exponentielle

(1.1)  ∑_{n≥0} \frac{u^{n}}{n!} H_{n}(x) = exp(ux − \frac{u^{2}}{2} ).

Notons que l’autre normalisation prise pour les polynômes d’Hermite consiste à prendre le développement de exp(2xu − u^{2}) ; voir, par exemple [Er53, p. 194, Le72, p. 60, Ra60, p. 187, Sz39, p. 105]. La présente normalisation, popularisée par Jackson [Ja41], se prête plus commodément à un traitement combinatoire.

Développons l’exponentielle du membre de droite de (1.1) et cherchons le coefficient de u^{n}/n! dans les deux membres. On obtient alors l’expression suivante pour les polynômes d’Hermite :

(1.2)  H_{n}(x) = ∑_{0≤2k≤n}(−1)^{k} x^{n−2k} \frac{n!}{1^{n−2k} (n − 2k)! 2^{k} k!}.

Les premières valeurs sont ainsi : H_{0}(x) = 1 ; H_{1}(x) = x; H_{2}(x) = x^{2} − 1 ; H_{3}(x) = x^{3} − 3x; H_{4}(x) = x^{4} − 6x + 3 ; H_{5}(x) = x^{5} − 10x^{3} + 15x.

Notons encore, voir par exemple, [Le72, p. 60 et 63], que l’on peut déduire de (1.1) la formule dite de Rodrigues

(1.3)  H_{n}(x) = (−1)^{n}e^{x^{2}/2} \frac{d^{n}}{dx^{n}} e^{−x^{2}/2},

d’ailleurs prise souvent comme définition des polynômes d’Hermite. Enfin, par dérivations successives de l’intégrale

∫_{0}^{+∞} e^{−u^{2}/2} cos ux du = \sqrt{\frac{π}{2}} e^{−x^{2}/2},

on obtient la forme intégrale des polynômes d’Hermite

(1.4)  H_{n}(x) = \frac{(−i)^{n}e^{x^{2}/2}}{\sqrt{2π}} ∫_{−∞}^{+∞} e^{−(u^{2}/2)+i ux}u^{n} du,

utile, comme pour beaucoup de fonctions spéciales, dans de nombreux calculs analytiques. Nous en verrons un exemple plus loin.

La formule bilinéaire de Mehler

(1.5) ∑_{n≥0} \frac{u^{n}}{n!} H_{n}(x) H_{n}(y) = (1 − u^{2})^{−1/2} exp(\frac{2uxy − u^{2}(x^{2} + y^{2})}{2(1 − u^{2})}),

dont la démonstration fera l’objet d’une comparaison entre analyse et combinatoire, a servi à établir que l’analogue du noyau de Poisson (cf. [As70]) des polynômes d’Hermite est positif, c’est-à-dire

∑_{n≥0} \frac{u^{n}}{n!} H_{n}(x) H_{n}(y) ≥ 0,

quelles que soient les valeurs de u, x, y.

Cette comparaison s’étendra aussi à l’extension multilinéaire

(1.6) ∑_{(ν_{i,j})} \frac{∏_{i<j} ρ_{i,j}^{ν_{i,j}}}{∏_{i<j} ν_{i,j}!} H_{s_{1}}(x_{1}) ⋯ H_{s_{m}}(x_{m})

= (det ρ)^{−1/2} exp(−\frac{1}{2} ∑_{i,j}(ρ_{i,j}^{−} − δ_{i,j})x_{i}x_{j}),

dont les ingrédients sont les suivants : d’abord, m ≥ 2 est un entier fixé, puis x_{1}, x_{2}, …, x_{m} sont m variables commutatives et ρ = (ρ_{i,j}) (1 ≤ i, j ≤ m) est une matrice symétrique de variables commutatives telle que ρ_{i,i} = 1 (1 ≤ i ≤ m) ; soit ρ^{−1} = (ρ_{i,j}^{−}) la matrice inverse de ρ. La sommation est alors sur toutes les matrices symétriques (ν_{i,j}) (1 ≤ i, j ≤ m, i ≠ j), à coefficients entiers positifs et enfin s_{j} := ∑_{1≤i≤m, i≠j} ν_{i,j} (1 ≤ j ≤ m).

2. Les démonstrations analytiques

Pour la formule de Mehler (1.5), il y a d’abord les démonstrations, disons élementaires, où l’on développe les deux membres de l’identité en série et où on utilise les formules classiques de sommation des séries, comme l’identité de Pfaff-Saalschütz. [On doit à Askey [As75a] d’avoir signalé que cette identité se trouve déjà démontrée dans un mémoire de Pfaff [Pf97], antérieur de 93 ans à l’article de Saalschütz [Sa90] auquel on se réfère habituellement.] C’est l’une des démonstrations proposées par Watson [Wa33]. Une démonstration encore plus élémentaire est obtenue par Rainville [Ra60, p. 196–198], qui n’utilise effectivement que les formules (1.1) et (1.2), en faisant des sommations appropriées.

Mentionnons aussi le principe de spécialisation, qui consiste à prendre une formule bilinéaire sur les polynômes de Laguerre, appelée identité de Hille-Hardy (voir [Er53], formule (20), p. 189) et à la particulariser pour les polynômes d’Hermite, ceux-ci étant des spécialisations des précédents. C’est la première démonstration de Watson [Wa33] et celle conseillée par Szegö (voir [Sz39], Ex. 23, p. 380).

Les autres démonstrations, en dehors de l’approche originale d’Erdélyi [Er39], utilisent la forme intégrale (1.4). Cette méthode est déjà implicite chez Mehler [Me66, p. 173–174]. On la trouve dans [Wa33] et [Le72, p. 63– 64]. On part du membre de gauche de (1.5) et on exprime les polynômes d’Hermite à l’aide de (1.4), soit

∑_{n≥0} \frac{t^{n}}{n!} H_{n}(x) H_{n}(y)

= \frac{e^{x^{2}/2+y^{2}/2}}{2π} ∑_{n≥0} \frac{(−1)^{n}}{n!} t^{n} ∫_{−∞}^{+∞}∫_{−∞}^{+∞} e^{u^{2}/2−v^{2}/2+iux+ivy} (uv)^{n} du dv.

Tout en justifiant la permutation des signes de sommation et d’intégrale, le membre de droite devient :

\frac{e^{x^{2}/2+y^{2}/2}}{2π} ∫_{−∞}^{+∞}∫_{−∞}^{+∞} e^{u^{2}/2−v^{2}/2+iux+ivy−uvt} du dv.

On calcule l’intégrale par itération, en utilisant la formule (close !)

∫_{−∞}^{+∞} e^{−a^{2}u^{2}/2−bu} du = \frac{\sqrt{2π}}{a} e^{b^{2}/(2a^{2})}

et l’on obtient le membre de droite de (1.4).

3. Involutions

Comme il est bien connu ou rapidement vérifié (voir, par exemple, [Ri58, p. 67]), le nombre de permutations de l’intervalle [ n] = {1, 2, …, n} ayant exactement k_{1} cycles de longueur 1 (dits points fixes), k_{2} cycles de longueur 2 (dits transpositions), k_{3} cycles de longueur 3, …, k_{n} cycles de longueur n, les entiers k_{i} satisfaisant 1 · k_{1} + 2 · k_{2} + 3 · k_{3} + ⋯ + n · k_{n} = n, est égal à

C(k_{1}, k_{2}, k_{3}, ⋯, k_{n}) = \frac{n!}{1^{k_{1}}k_{1}! 2^{k_{2}}k_{2}! 3^{k_{3}}k_{3}! … n^{k_{n}}k_{n}!}.

On reconnaît, dans la fraction apparaissant dans le membre de droite de l’identité (1.2) le coefficient C(n − 2k, k, 0, …, 0) (0 ≤ 2k ≤ n), c’està-dire, le nombre d’involutions de l’intervalle [ n] = {1, 2, …, n} ayant exactement k transpositions et (n − 2k) points fixes (et donc aucun cycle d’ordre supérieur).

Soit alors Inv_{n} l’ensemble de toutes les involutions de [ n]. Pour tout σ ∈ Inv_{n}, notons trans(σ) et fix(σ) le nombre des transpositions et des points fixes de σ, respectivement et posons

(3.1)  μ(σ) := (−1)^{trans(σ)} x^{fix(σ)}.

La formule (1.2) peut encore s’écrire :

(3.2)  H_{n}(x) = μ{Inv_{n}} := ∑_{σ∈Inv_{n}} μ(σ).

En d’autres termes, le polynôme d’Hermite H_{n}(x) peut être vu comme la fonction génératrice de l’ensemble Inv_{n} suivant le nombre de points fixes et de transpositions, c’est-à-dire la fonction génératrice des involutions σ de [ n] par le poids μ(σ) = (−1)^{trans σ} x^{fix σ}.

Identifions chaque involution σ de l’intervalle [ n] à son graphe, ayant n sommets étiquetés 1, 2, …, n. Les seules composantes connexes du graphe sont les boucles, de poids x, ou les cycles de longueur 2, de poids − 1, comme montré dans la Fig. 2.

[figure: i; •; •; •; j; k] Fig. 2

L’identité (1.1) peut donc se récrire :

(3.3)  ∑_{n≥0} μ\{Inv_{n}\}\frac{u^{n}}{n!} = exp(μ( •1) + \frac{1}{2} μ(• \overline{}\overline{}• 1 2)).

Pour n ≥ 1, notons Invc_{n} l’ensemble des involutions de [ n], dont le graphe est connexe [en abrégé : les involutions connexes]. On a évidemment :

Invc_{1} = \{ •1\},  Invc_{2} = \{• \overline{}\overline{}• 1 2\},  Invc_{n} = ∅ (n ≥ 3),

de sorte que (1.1) peut encore se récrire

(3.4)  ∑_{n≥0} μ\{Inv_{n}\}\frac{u^{n}}{n!} = exp(∑_{n≥1} μ\{Invc_{n}\}\frac{u^{n}}{n!} ).

Cette dernière identité s’interprète en disant que la fonction génératrice exponentielle des polynômes générateurs des involutions sur les intervalles [ n] est égale à l’exponentielle de la fonction génératrice exponentielle des polynômes générateurs des involutions connexes sur les mêmes intervalles.

Les formules (1.5) et (1.6) se présentent aussi sous la forme a = exp b, où a et b sont des séries. Si donc b est la fonction génératrice de structures finies, disons Y_{n} (n ≥ 1) (comme les Invc_{n} précédemment), il importe de donner des conditions suffisantes pour que a apparaisse comme la fonction génératrice d’autres structures liées aux Y_{n}. Ceci fait l’objet du prochain paragraphe.

4. L’identité exponentielle

La formule (3.4) apparaît comme une variation de l’identité exponentielle :

(4.1)  ∑_{n≥0} μ\{Y_{n}^{(+)}\}\frac{u^{n}}{n!} = exp(∑_{n≥1} μ\{Y_{n}\}\frac{u}{n!}).

Dans cette identité, la suite Y = (Y_{n}) (n ≥ 1) est une suite d’ensembles finis ; à chaque entier n ≥ 1, chaque y ∈ Y_{n} et chaque sous-ensemble I de ℕ \ {0}, de cardinal n, est associée une variable notée (y, I). On suppose que les variables (y, I) commutent. Pour chaque entier n ≥ 1, le composé partitionnel de Y, de degré n est défini comme étant l’ensemble, noté Y_{n}^{(+)}, de tous les monômes (y_{1}, I_{1})(y_{2}, I_{2}) … (y_{r}, I_{r}), ayant la propriété que l’ensemble {I_{1}, I_{2}, …, I_{r}} est une partition de l’intervalle [ n]. La suite Y^{(+)} = (Y_{n}^{(+)}) (n ≥ 1) est appelé le composé partitionnel de Y.

Soit μ une application envoyant les monômes en les variables (y, I) dans une algèbre Ω de polynômes. On dit qu’elle est multiplicative si les deux conditions suivantes sont satisfaites :

(i) pour toute paire de monômes w, w′, on a : μ(ww′) = μ(w)μ(w′) ; (ii) pour toute variable (y, I), tel que y ∈ Y_{n} (et donc tel que I est de

cardinal n), on a μ(y, I) = μ(y, [ n] ).

Si maintenant y appartient à Y_{n}, on définit : μ(y) := μ(y, [ n]), de sorte que si w = (y_{1}, I_{1})(y_{2}, I_{2}) … (y_{r}, I_{r}) appartient à Y_{n}^{(+)}, on a la propriété multiplicative :

μ(w) = μ(y_{1})μ(y_{2}) … μ(y_{r}).

Théorème 4.1. Soient Y^{(+)} le composé partitionnel de la suite Y et μ une fonction multiplicative. Alors la formule exponentielle (4.1) est vérifiée.

La démonstration de ce théorème peut être trouvée dans [Fo74], mais on peut aussi bien l’établir directement en développant l’exponentielle et en interprétant les calculs à la lumière des précédentes définitions sur le composé partitionnel.

5. La formule de Mehler ; l’approche combinatoire

Comme on a vu précédemment, toute involution de [ n] est composée de points fixes et de transpositions. Par exemple, l’involution σ = (2)(5)(7)(1, 3)(4, 6) peut se récrire :

σ = (1, {2}) (1, {5}) (1, {7}) ((1, 2), {1, 3}) ((1, 2), {4, 6}).

Cet exemple montre que la suite des involutions de [ n] (n = 0, 1, …) n’est autre que le composé partitionnel de la suite

Invc_{1} = {(1)}, Invc_{2} = {(1, 2)}, Invc_{n} = ∅ (n ≥ 3).

Par ailleurs, la fonction μ, définie en (3.1) est bien multiplicative. On a donc immédiatement l’identité (3.4). Ainsi, l’identité (1.1) qui définissait les polynômes d’Hermite n’est autre que l’identité exponentielle pour le composé partitionnel de la suite des involutions connexes.

Voyons maintenant comment on peut faire rentrer la formule de Mehler dans ce cadre exponentiel. Pour chaque couple d’involutions (σ, τ) ∈ Inv_{n} × Inv_{n}, posons cette fois

(5.1)  μ(σ, τ) := (−1)^{trans σ}x^{fix σ} (−1)^{trans τ} y^{fix τ} ,

de sorte que le produit de deux polynômes d’Hermite peut se récrire

H_{n}(x)H_{n}(y) = ∑ μ(σ, τ) ((σ, τ) ∈ Inv_{n} × Inv_{n}),

que l’on exprime pour simplifier comme

H_{n}(x)H_{n}(y) = μ{Inv_{n} × Inv_{n}}

et le membre gauche de (1.5) comme

∑_{n≥0} μ\{Inv_{n} × Inv_{n}\}\frac{u^{n}}{n!} .

Le facteur (1 − u^{2})^{−1/2} du membre de droite pouvant aussi s’exprimer à l’aide d’une exponentielle, on peut récrire la formule de Mehler :

∑_{n≥0} μ\{Inv_{n} × Inv_{n}\}\frac{u^{n}}{n!}

= exp(∑_{n≥1} \frac{u^{2n}}{2n} + (∑_{n≥0} xyu^{2n+1} − \frac{x^{2} + y^{2}}{2} u^{2n+2})).

(5.2) = exp( ∑_{n impair} xy n! \frac{u^{n}}{n!} + ∑_{n≥2 pair}((n−1)!− \frac{x^{2} + y^{2}}{2} n! )\frac{u^{n}}{n!} ).

On retrouve bien l’identité exponentielle, mais pour démontrer la formule de Mehler, il faut trouver des ensembles finis Y_{n} tels que Y_{n}^{(+)} = Inv_{n} × Inv_{n} et une fonction μ qui redonne (5.1), lorsqu’un couple d’involutions (σ, τ) s’exprime comme un monôme en les variables (y, I).

Or, considérons deux graphes d’involutions d’un même ensemble de n éléments, matérialisés par des gros points “•.” On n’a pas écrit les étiquettes des points pour ne pas surcharger la figure. Les points fixes sont représentés par des boucles et les transpositions simplement par des arêtes joignant deux points. La première a les boucles et les arêtes en trait continu (cf. Fig. 3), la seconde les a en trait pointillé (cf. Fig. 4).

\begin{matrix}• & • & • & • & • & • & • \\ • & • & • & • & • & • & • \\ • & • & • & • & • & • & • \\ • & • & • & • & • & • & • \end{matrix}

Fig. 3

• - - - - •  • - - - - •  • - - - - •  •
•  • - - - - •  • - - - - •  •  •
•  • - - - - •  • - - - - •  •  •
•  • - - - - •  • - - - - •  •  •

Fig. 4

Superposons ces deux graphes l’un sur l’autre, en faisant coïncider les gros points, par exemple à l’aide de deux transparents où les traits continus et pointillés sont remplacés par des traits de différente couleur. On obtient un nouveau graphe, où chaque point est de valence 2 et naturellement incident à deux arêtes ou boucles de trait continu et pointillé. Voir Fig. 5.

\begin{matrix}• & - - - - • & • & - - - - • & • & - - - - • & • \\ • & • & - - - - • & • & - - - - • & • & • \\ • & • & - - - - • & • & - - - - • & • & • \\ • & • & - - - - • & • & - - - - • & • & • & \end{matrix}Fig. 5

On observe, de plus, que le graphe obtenu est composé de quatre types de sous-graphes connexes. Il y a d’abord les cycles, forcément de longueur paire, où les couleurs (trait continu ou trait pointillé) des arêtes alternent. Il y en a deux dans le graphe de la Fig. 5, l’un à deux sommets, l’autre à dix sommets (cf. Fig. 6). Soit A_{n} l’ensemble de ces cycles ayant n sommets (et forcément n arêtes) numérotés 1, 2, …, n.

\begin{matrix}• & • & - - - - • & • & - - - - • \\ • & • & - - - - • & • & - - - - • \end{matrix} Fig. 6

Il y a ensuite les chaînes dont les deux extrémités ont des boucles de même couleur. Ces chaînes ont forcément un nombre pair de sommets. D’abord, celles qui finissent par des boucles en trait continu. Il y en a une seule dans le graphe de la Fig. 5, à savoir

• - - - - •  • - - - - •

Fig. 7

Il y a aussi les chaînes finissant par des boucles en trait pointillé. Il y en a une seule dans le graphe de la Fig. 5, à savoir

•  • - - - - •  • - - - - •  •

Fig. 8

Il y a enfin les chaînes finissant par une boucle en trait continu et une boucle en trait pointillé. Celles-ci ont forcément un nombre impair de points. Il y en a deux dans le graphe de la Fig. 5, une à un seul sommet et une à cinq sommets, à savoir

• - - - - •  •
•
•

Fig. 9

Soit B_{n} (resp. C_{n}) l’ensemble des chaînes de n sommets, numérotés 1, 2, …, n, dont les deux boucles terminales sont en trait continu (resp. en trait pointillé). Soit, enfin, D_{n} l’ensemble des chaînes de n sommets, toujours numérotés 1, 2, …, n, dont les boucles terminales sont, l’une en trait continu, l’autre en trait pointillé.

Lorsque l’on identifie Inv_{n} × Inv_{n} avec l’ensemble des graphes obtenus par superposition de deux graphes d’involutions de [ n] (appelons-les graphes bi-involutionnaires), un instant de réflexion permet de se convaincre que les seuls sous-graphes connexes de ce graphe bi-involutionnaire sont les cycles du type précédent et les chaînes de l’un des trois types précédents. Posons Y_{n} = A_{n} + B_{n} + C_{n} + D_{n} (union disjointe). Un second instant de réflexion permet alors de se persuader que

l’ensemble de ces graphes bi-involutionnaires est le composé partitionnel de la suite Y = (Y_{n}) (n ≥ 1).

Soit maintenant w un graphe bi-involutionnaire de n sommets, donc un élément de Y_{n}^{(+)}, ayant k arêtes en trait continu, l arêtes en trait pointillé, k′ boucles en trait continu et l′ boucles en trait pointillé. Pour un tel graphe, posons :

μ(w) := (−1)^{k}x^{k′}(−1)^{l}y^{l′}.

Il est facile de voir que cette fonction μ ainsi définie est multiplicative et que, d’autre part, μ est constante sur chacun des sous-ensembles A_{n}, B_{n}, C_{n}, D_{n}. Par exemple, en notant |A| le cardinal d’un ensemble fini A,

μ{A_{n}} = μ(y) · |A_{n}|,

où y est l’un quelconque des éléments de A_{n}. Il suffit donc d’évaluer les cardinaux de ces ensembles pour déterminer les quantités μ{A_{n}}, μ{B_{n}}, μ{C_{n}}, μ{D_{n}}. On obtient le tableau suivant de la Fig. 10.

Type  n  μ(y)  Cardinal μ{·}
A_{n}  pair  (−1)^{n}  (n − 1)! (n − 1)!
A_{n} = ∅ impair  0  0
B_{n}  pair (−1)^{n−1}x^{2} n!/2 −x^{2}n!/2
B_{n} = ∅ impair  0  0
C_{n}  pair (−1)^{n−1}y^{2} n!/2 −y^{2}n!/2
C_{n} = ∅ impair  0  0
D_{n} = ∅ pair  0  0
D_{n} impair (−1)^{n−1}xy n!/2  xyn!

Fig. 10

On en tire

∑_{n≥1} μ\{Y_{n}\}\frac{u^{n}}{n!} = ∑_{n impair} xy n! \frac{u^{n}}{n!} + ∑_{n≥2 pair}((n − 1)! − \frac{x^{2} + y^{2}}{2} n! )\frac{u^{n}}{n!} ,

qui est bien l’argument de l’exponentielle qui apparaît dans (5.2). La formule de Mehler est donc démontrée.

6. Comment exploiter ce nouveau modèle combinatoire ?

Considérons encore un graphe bi-involutionnaire G, de n sommets, numérotés 1, 2, …, n, mais convenons qu’au lieu d’avoir deux couleurs (les traits continus et les traits pointillés) pour colorier arêtes et boucles, on en ait m ≥ 2, tout en supposant que les arêtes ou boucles incidents à un même sommet sont de couleurs différentes. Appelons m-involutionnaire un tel graphe. Pour 1 ≤ i < j ≤ m soit N_{i,j} le sous-ensemble de tous les sommets incidents à une arête ou boucle de couleur i et à une arête ou boucle de couleur j. Pour i < j, posons N_{j,i} = N_{i,j} et S_{j} = ∑_{i, i≠j} N_{i,j}. Par

conséquent, S_{j} est l’ensemble des sommets qui sont incidents à une arête ou boucle de couleur j.

L’ensemble {N_{i,j} : 1 ≤ i < j ≤ m} est une partition de [ n] ; appelons blocs du graphe ces sous-ensembles N_{i,j}; de plus, pour chaque i = 1, 2, …, m, le sous-graphe G_{i}, dont l’ensemble des sommets est S_{i} et dont les arêtes et boucles sont de couleur i, est le graphe G_{i} d’une involution de l’ensemble S_{i}.

Réciproquement, pour se donner un graphe m-involutionnaire de n sommets, il suffit d’avoir une suite (S_{i}) (1 ≤ i ≤ m) de sous-ensembles de ces sommets, tel que tout sommet appartient exactement à deux sous-ensembles S_{i}, S_{j} (i ≠ j) et tel que le sous-graphe G_{i} restreint à chaque S_{i} soit le graphe d’une involution. Les blocs sont alors définis par N_{i,j} := S_{i} ∩ S_{j} (i ≠ j).

Si donc on se fixe une suite (S_{i}) ayant les propriété précédentes et si l’on pose μ(G_{i}) = (−1)^{trans G_{i}} x_{i}^{fix G_{i}}, la sommation ∑_{G_{i}} μ(G_{i}) sur tous les graphes d’involutions G_{i} de l’ensemble S_{i} est précisément le polynôme d’Hermite H_{|S_{i}|}(x_{i}), d’après (3.2).

En plus des variables x_{i} (1 ≤ i ≤ m), considérons un ensemble de variables commutatives ρ_{i,j} (1 ≤ i < j ≤ m), puis définissons le poids d’un graphe m-involutionnaire G de m sommets comme étant

(6.1) \overline{μ}(G) := ∏_{i<j} ρ_{i,j}^{|N_{i,j}|} ∏_{i} μ(G_{i}),

enfin, formons la série

(6.2)  ∑_{n≥0} \frac{1}{n!} ∑_{G} \overline{μ}(G),

où la seconde somme porte sur tous les graphes m-involutionnaires de n sommets.

Dans cette seconde sommation, on peut d’abord se fixer une suite d’entiers (ν_{i,j}) (1 ≤ i, j ≤ m, i ≠ j) telle que ∑_{i<j} ν_{i,j} = n, définir ν_{j,i} := ν_{i,j}, s_{i} := ∑_{1≤i≤n, i≠j} ν_{i,j} pour 1 ≤ i ≤ m, puis faire la sommation

sur toutes les partitions {N_{i,j} : 1 ≤ i < j ≤ m} de [ n] telles que |N_{i,j}| = ν_{i,j} pour i < j, enfin faire la sommation sur tous les graphes G, m-involutionnaires de n sommets dont les blocs sont précisément les ensembles N_{i,j} pour i < j. La série (6.2) devient :

(6.3)  ∑_{n≥0} \frac{1}{n!} ∑_{(ν_{i,j})} ∏_{i<j} ρ_{i,j}^{ν_{i,j}} ∑_{(N_{i,j})} ∑_{G} ∏_{i} μ(G_{i}).

Comme ∑_{G} ∏_{i} μ(G_{i}) = ∏_{i} H_{s_{i}}(x_{i}), on obtient

(6.4)  ∑_{n≥0} \frac{1}{n!} ∑_{G} \overline{μ}(G) = ∑_{n≥0} \frac{1}{n!} ∑_{(ν_{i,j})} \frac{n!}{∏_{i<j} ν_{i,j}!} ∏_{i<j} ρ_{i,j}^{ν_{i,j}} ∏_{i} H_{s_{i}}(x_{i}).

Autrement dit, la fonction génératrice exponentielle des graphes minvolutionnaires par le poids \overline{μ} est donnée par

(6.5)  ∑_{n≥0} \frac{1}{n!} ∑_{G} \overline{μ}(G) = ∑_{(ν_{i,j})} \frac{∏_{i<j} ρ_{i,j}^{ν_{i,j}}}{∏_{i<j} ν_{i,j}!} H_{s_{1}}(x_{1}) ⋯ H_{s_{m}}(x_{m}),

où la somme est sur toutes les matrices symétriques

(ν_{i,j}) (1 ≤ i, j ≤ m, i ≠ j),

à coefficients entiers positifs et où l’on a posé s_{j} = ∑_{1≤i≤m, i≠j} ν_{i,j}.

On a ainsi interprété combinatoirement le membre de gauche de l’identité multilinéaire (1.6). La question qui se pose alors est la suivante : peut-on faire un comptage des graphes m-involutionnaires à l’aide de ses parties connexes, en s’inspirant du principe développé dans le paragraphe précédent, et obtenir le membre de droite de (1.6) et du coup démontrer l’identité (1.6) ? La réponse est oui.

Comme on peut l’imaginer, on peut vérifier que l’expression (det ρ)^{−1/2} est l’exponentielle de la série génératrice de tous les graphes m-involution-naires, qui sont des cycles. On montre, ensuite, que la forme quadratique −\frac{1}{2} ∑_{i,j}(ρ_{i,j}^{−} − δ_{i,j})x_{i}x_{j} est la série génératrice de toutes les chaînes, les variables x_{i}, x_{j} étant les poids des deux boucles aux extrémités. Les détails de cette démonstration combinatoire peuvent être trouvés dans [FoGa79].

5. Conclusion

Le modèle des graphes involutionnaires ayant été imaginé, on aurait pu croire que ce seraient les spécialistes de Combinatoire qui auraient obtenu les premiers l’extension multilinéaire (1.6). En fait, cette identité a été imaginée et prouvée tout d’abord par Kibble [Ki45], dans la thèse de doctorat qu’il a terminée en 1945, avant de faire une carrière comme… missionnaire. En fait, c’est sa familiarité avec les distributions statistiques et tout particulièrement la loi normale à plusieurs variables, qui lui a permis de trouver que la bonne extension du membre de droite de (1.5) était le membre de droite de (1.6). Il a ensuite su exprimer cette extension en termes de produits de polynômes d’Hermite.

L’identité (1.6) a ensuite été redécouverte par Slepian [Sl72] en 1972. La démonstration combinatoire esquissée dans le paragraphe 6 a été obtenue en 1979. Enfin, en 1981, Louck [Lo81] l’a reprouvée par des méthodes reposant sur les opérateurs de boson utilisés en physique. Contrairement à ce que dit le titre de l’article, Louck démontre, en fait, une identité qui est simplement équivalente à cette extension multilinéaire.

On trouve dans l’étude des polynômes orthogonaux, à l’intérieur de la classification donnée par Askey [As75] et qui regroupe plusieurs polynômes usuels (Hermite, Laguerre, Jacobi, …) des identités de type exponentiel, qui ont été prouvées par la technique ci-dessus. On peut dire enfin que c’est la démonstration combinatoire de la formule de Mehler [Fo78] qui a servi de déclic à Joyal [Jo81], pour mettre au point sa théorie des espèces, popularisée par l’école montréalaise (voir [Be98]) et qui constitue un cadre élégant pour la manipulation des séries formelles. Notons, enfin, que cette méthode combinatoire a été judicieusement utilisée et exploitée par Zeng, d’abord dans sa thèse de doctorat [Ze88] et dans plusieurs travaux ultérieurs, notamment dans [Ze92] et [Ze01]

Remerciements. — Merci à Raymond Seroul, qui a relu, de façon très critique, une première version de cet article.

BIBLIORAPHIE

[As70] Richard Askey. — Orthogonal polynomials and positivity, “Studies in Appl. Math.,” 6, in “Wave Propagation and Special Functions” (D. Ludwig and F. W. J. Olver, eds.), SIAM, Philadelphia, 1970.

[As75] Richard Askey. — Orthogonal polynomials and Special Functions. — “Regional Conference Series in Appl. Math., 21, SIAM, Philadelphia, 1970.

[As75a] Richard Askey. — MRC Technical Report, 1532, Madison, Wisconsin, 1975.

[Be98] François Bergeron, Gilbert Labelle, Pierre Leroux. — Combinatorial species and tree-like structures. — Encyclopedia of Math. and its Appl., 67, Cambridge Univ. Press, Cambridge, 1998.

[Er39] Arthur Erdélyi. — Über eine erzeugende Funktion von Produkten Hermitescher Polynome, Math. Zeitschrift, vol. 44, 1939, p. 201–211.

[Er53] Arthur Erdélyi, Wilhelm Magnus, Fritz Oberhettinger, Francesco G. Tricomi. Higher Transcendental Functions, Bateman Manuscript Project, Vol. II. — New York, McGraw-Hill, 1953.

[Fo74] Dominique Foata. — La série génératrice exponentielle dans les problèmes d’énumération. — Presses de l’Université de Montréal, Montréal, 1974.

[Fo78] Dominique Foata. — A combinatorial proof of the Mehler formula, J. Combina-

torial Theory, Ser. A, vol. 24, 1978, p. 250–259.

[FoGa79] Dominique Foata, Adriano Garsia. — A combinatorial approach to the Mehler formulas for Hermite polynomials, in “Relations between combinatorics and other parts of mathematics” (Proc. Sympos. Pure Math., Ohio State Univ., Columbus, Ohio, 1978), Proc. Sympos. Pure Math., XXXIV, Amer. Math. Soc., Providence, R.I., 1979, p. 163-179.

[Ja41] D. Jackson. — Fourier Series and Orthogonal Polynomials. — Carus Math. Monograph 6, Math. Assoc. Amer., State Univ. New York, Buffalo, New York, 1941.

[Jo81] André Joyal. — Une théorie combinatoire des séries formelles, Adv. in Math., vol. 42, 1981, p. 1–82.

[Ki45] W. F. Kibble. — An extension of a the theorem of Mehler on Hermite polynomials, Proc. Cambridge Philos. Soc., vol. 41, 1945, p. 12–15.

[Le72] N. N. Lebedev. — Special Functions and their Applications. — Dover Publ., New York, 1972.

[Lo81] J. D. Louck. — Extension of the Kibble-Slepian formula for Hermite polynomials using boson operator methods, Adv. in Appl. Math., vol. 2, 1981, p. 239–249.

[Me66] F. G. Mehler. — Über die Entwicklung einer Function von beliebig vielen Variablen nach Laplaceschen Functionen höherer Ordnung, J. für die reine und angewandte Mathematik, vol. 66, 1866, p. 161–176.

[Pf97] J. F. Pfaff. — Observationes analyticae ad L Euleri institutiones calculi integralis, vol. IV. Supplem. II et IV, Nova Acta Academiae Scientiarum Imperialis Petropolitanae, vol. 11, 1797, p. 37–57.

[Ra60] Earl D. Rainville. — Special Functions. — Chelsea Publ. Co., New York, 1960.

[Ri58] John Riordan. — An Introduction to Combinatorial Analysis. — J. Wiley & Sons, New York, 1958.

[Ro96] Gian-Carlo Rota. — Report on the present state of combinatorics (Inaugural address delivered at the 5th Formal Power Series and Algebraic Combinatorics Conference, Florence, 21 juin 1993), Discrete Math., vol. 153, 1996, p. 289–303.

[Sa90] L. Saalschütz. — Eine Summationsformel, Z. für Math. u. Phys., vol. 35, 1890, p. 186–188.

[Sl72] David Slepian. — On the symmetrized Kronecker power of a matrix and extensions of Mehler’s formula for Hermite polynomials, SIAM J. Math. Anal., vol. 3, 1972, p. 606–616.

[Sz39] Gabor Szegö. — Orthogonal Polynomials. — Amer. Mat. Soc. Colloq. Publ., 23, Amer. Math. Soc., Providence, R.I. 1939, fourth ed. 1978.

[Wa33] G. N. Watson. — Notes on generating functions. II. Hermite polynomials, J. London Math. Soc., vol. 8, 1933, p. 194–199.

[Ze88] Jiang Zeng. — Calcul Saalschützien (thèse doctorat), Publ. IRMA Strasbourg, vol. 360/TS-05, 1988.

[Ze92] Jiang Zeng. — Weighted derangements and the linearization coefficients of orthogonal Sheffer polynomials, Proc. London Math. Soc., vol. 65, 1992, p. 1-22.

[Ze01] Jiang Zeng, D.S. Kim. — A combinatorial formula for the linearization coefficients of general Sheffer polynomials, Europ. J. Combin., vol. 22, 2001, p. 313–332.

Dominique Foata Institut Lothaire 1, rue Murner F-67000 Strasbourg, France

                 foata@math.u-strasbg.fr
                 http://www-irma.u-strasbg.fr/∼foata