Formule exponentielle - Exponential formula

En mathématiques combinatoires , la formule exponentielle (appelée expansion des polymères en physique ) indique 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 une version en série d'un cas particulier de la formule de Faà di Bruno .

Déclaration

Pour toute série entière formelle de la forme

f(x)=a_{1}x+{a_{2} \over 2}x^{2}+{a_{3} \over 6}x^{3}+\cdots +{a_{n } \sur n!}x^{n}+\cdots \,

on a

\exp f(x)=e^{f(x)}=\sum _{n=0}^{\infty }{b_{n} \over n!}x^{n},\,

où

b_{n}=\sum _{\pi =\left\{\,S_{1},\,\dots ,\,S_{k}\,\right\}}a_{\left|S_ {1}\right|}\cdots a_{\left|S_{k}\right|},

et l'indice

π

parcourt la liste de toutes les partitions { S ₁ , ..., S _k } de l'ensemble { 1, ..., n }. (Lorsque le produit est vide et par définition égal à 1.)

{\style d'affichage k=0,}

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}^{\infty }{a_{n} \over n!}x^{n}\right)=\sum _{n=0}^{ \infty }{B_{n}(a_{1},\dots ,a_{n}) \over n!}x^{n},

où B _n ( a ₁ , ..., a _n ) est le n ième polynôme de Bell complet .

Alternativement, la formule exponentielle peut également être écrite en utilisant l' indice de

cycle du groupe symétrique, comme suit :

\exp \left(\sum _{n=1}^{\infty }a_{n}{x^{n} \over n}\right)=\sum _{n=0}^{\ infty }Z_{n}(a_{1},\dots ,a_{n})x^{n},

où Z _n représente le polynôme d'indice de cycle, pour le groupe symétrique défini comme :

{\style d'affichage S_{n}}

Z_{n}(x_{1},\cdots ,x_{n})={\frac {1}{n!}}\sum _{\sigma \in S_{n}}x_{1} ^{\sigma _{1}}\cdots x_{n}^{\sigma _{n}}

et désigne le nombre de cycles de de taille . Ceci est une conséquence de la relation générale entre et les polynômes de Bell :

\sigma _{j}

{\style d'affichage \sigma }

j\in \{1,\cdots ,n\}

{\style d'affichage Z_{n}}

Z_{n}(x_{1},\dots ,x_{n})={1 \over n!}B_{n}(0!\,x_{1},1!\,x_{2 },\points ,(n-1)!\,x_{n}).

Exemples

$b_{3}=B_{3}(a_{1},a_{2},a_{3})=a_{3}+3a_{2}a_{1}+a_{1}^{3 },$ car il y a une partition de l'ensemble { 1, 2, 3 } qui a un seul bloc de taille 3, il y a trois partitions de { 1, 2, 3 } qui le divisent en un bloc de taille 2 et un bloc de taille 1, et il y a une partition de { 1, 2, 3 } qui la divise en trois blocs de taille 1. Cela découle également de , puisqu'on peut écrire le groupe sous la forme , en utilisant la notation cyclique pour les permutations. $Z_{3}(a_{1},a_{2},a_{3})={1 \over 6}(2a_{3}+3a_{1}a_{2}+a_{1}^ {3})={1 \sur 6}B_{3}(a_{1},a_{2},2a_{3})$ ${\style d'affichage S_{3}}$ ${\style d'affichage S_{3}=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\} }$
Si est le nombre de graphes dont les sommets sont un ensemble de

n points donné, alors a _n est le nombre de graphes connectés dont les sommets sont un ensemble de n points donné.

{\style d'affichage b_{n}=2^{n(n-1)/2}}

Il existe de nombreuses variantes de l'exemple précédent où le graphe a certaines propriétés : par exemple, si b _n compte des graphes sans cycles, alors un _n compte des arbres (graphes connectés sans cycles).

Si b _n compte les graphes orientés dont les arêtes (plutôt que les sommets) sont un ensemble de n points donné, alors un _n compte les graphes orientés connectés avec cette arête s

Applications

Dans les applications, les nombres a _n comptent souvent le nombre d'une sorte de structure "connectée" sur un ensemble de n points, et les nombres b _n comptent le nombre de structures (éventuellement déconnectées). Les nombres b _n / n ! compter le nombre de classes d'isomorphismes de structures sur n points, chaque structure étant pondérée par l'inverse de son groupe d'automorphismes, et les nombres a _n / n ! compter les classes d'isomorphisme des structures connectées 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 connectés, en termes de fonctions de corrélation connectées .

Voir également

Surjection des espaces de Fréchet – Caractérisation de la surjectivité

Les références

Stanley, Richard P. (1999), Combinatoire énumérative. Vol. 2 , Cambridge Studies in Advanced Mathematics, 62 , Cambridge University Press , ISBN 978-0-521-56069-6, MR 1676282 , ISBN 978-0-521-78987-5 Chapitre 5

Languages

In other projects