Formule exponentielle

En combinatoire, la formule exponentielle (appelée expansion du polymère en physique) établit que la fonction génératrice exponentielle pour les structures sur des ensembles finis est l'exponentielle de la fonction génératrice exponentielle pour les structures connectées. La formule exponentielle est un cas particulier de la formule de Faà di Bruno appliquée aux séries entières.

Définition

Pour toute série formelle de la forme $$f(x)=a_{1}x+\frac{a_2}{2}{x}^2+\frac{a_3}{6}{x}^3+\cdots +\frac{a_n}{n!}{x}^n+\cdots$$ On a $$\exp f(x)={\mathrm{e}}^{f(x)}=\sum _{n=0}^{\mathrm{\infty }}\frac{b_n}{n!}{x}^n,$$ où $$b_n=\sum _{\pi =\{S_1,\dots ,S_k\}}{a}_{\left|S_1\right|}\cdots a_{\left|S_k\right|},$$ et l'indice Modèle:Math parcourt la liste de toutes les partitions {S₁,..., S_k} de l'ensemble {1,..., n}. (Lorsque k = 0, le produit est vide et par définition égal à 1).

On peut écrire la formule sous la forme suivante : $$b_n=B_n(a_1,a_2,\dots ,a_n),$$ Et ainsi $$\exp \left(\sum _{n=1}^{\mathrm{\infty }}\frac{a_n}{n!}{x}^n\right)=\sum _{n=0}^{\mathrm{\infty }}\frac{B_n(a_1,\dots ,a_n)}{n!}{x}^n,$$ où Modèle:Math est le n-ième polynôme de Bell complet.

Autre possibilité, la formule exponentielle peut être écrite en utilisant l'indice de cycle du groupe symétrique, comme suit :$$\exp \left(\sum _{n=1}^{\mathrm{\infty }}{a}_n\frac{x^n}{n}\right)=\sum _{n=0}^{\mathrm{\infty }}{Z}_n(a_1,\dots ,a_n)x^n,$$ où Modèle:Mvar représente le polynôme d'indice de cycle, pour le groupe symétrique ${𝔖}_n$ défini comme : $$Z_n(x_1,\cdots ,x_n)=\frac{1}{n!}\sum _{\sigma \in {𝔖}_n}{x}_1^{{\sigma }_1}\cdots x_n^{{\sigma }_n}$$et ${\sigma }_j$ désigne le nombre de cycles de $\sigma$ de taille $j\in \{1,\cdots ,n\}$. Ceci est une conséquence de la relation générale entre Modèle:Mvar et les polynômes de Bell : $$Z_n(x_1,\dots ,x_n)=\frac{1}{n!}{B}_n(0!x_1,1!x_2,\dots ,(n-1)!x_n).$$

Exemples

• $b_3=B_3(a_1,a_2,a_3)=a_3+3a_2{a}_1+a_1^3,$ parce qu'il y a
  • une partition de l'ensemble { 1, 2, 3 } qui a un seul bloc de taille 3 ;
  • trois partitions de { 1, 2, 3 } qui le divisent en un bloc de taille 2 ;
  • un bloc de taille 1, et une partition de { 1, 2, 3 } qui la divise en trois blocs de taille 1.

Cela découle également de $Z_3(a_1,a_2,a_3)=\frac{1}{6}(2a_3+3a_1{a}_2+a_1^3)=\frac{1}{6}{B}_3(a_1,a_2,2a_3)$, puisqu'on peut écrire le groupe ${𝔖}_3$ comme ${𝔖}_3=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\}$, en utilisant la notation cyclique pour les permutations.

• Si $b_n=2^{n(n-1)/2}$ est le nombre de graphes dont les sommets sont un ensemble donné de n points, alors Modèle:Mvar est le nombre de graphes connectés dont les sommets sont un ensemble donné de n points.
• Il existe de nombreuses variantes de l'exemple précédent où le graphe a certaines propriétés : par exemple, si Modèle:Mvar compte des graphes sans cycles, alors Modèle:Mvar compte des arbres (graphes connectés sans cycles).
• Si Modèle:Mvar compte les graphes orientés dont les arêtes (plutôt que les sommets) sont un ensemble donné de n points, alors Modèle:Mvar compte les graphes orientés connectés avec cet ensemble d'arêtes.

Applications

Dans les applications, les nombres Modèle:Mvar comptent souvent le nombre d'une sorte de structure « connexe » sur un ensemble à n points, et les nombres Modèle:Mvar comptent le nombre de structures (éventuellement non connexes). Les nombres Modèle:Math comptent les classes d'isomorphisme de structures sur n points, chaque structure étant pondérée par l'inverse de son groupe d'automorphismes, et les nombres Modèle:Math comptent les classes d'isomorphisme des structures connexes de la même manière.

En théorie quantique des champs et en mécanique statistique, les fonctions de partition Z, ou plus généralement les fonctions de corrélation, sont données par une somme formelle sur des diagrammes de Feynman. La formule exponentielle montre que log(Z) peut être écrit comme une somme sur des diagrammes de Feynman connexes, en termes de fonctions de corrélation connexes.

Références

• Modèle:Ouvrage