La série formelle $$A(x) = \sum_{n\ge 0}a_n\frac{x^n}{n!}$$ est appelée série génératrice exponentielle (SGE) de la suite $(a_n)$. C'est donc aussi la série génératrice ordinaire (SGO) de la suite $\left(\frac{a_n}{n!}\right)$
L'esponentielle $e^x$ est donc la SGE de la suite constante $a_n=1$ ($n\ge 0$). La SGE de la suite $(n!)$ est la série géométrique $\frac1{1-x}$.
Ces séries apparaissent souvent lorsque l'on cherche à compter des permutations. Il y a $n!$ permutations de $n$ objets. Si on note $a_n$ le nombre de celles qui vérifient une certaine contrainte, $\frac{a_n}{n!}$ est la probabilité qu'one permutation aléatoire vérifie la contrainte en question.
Le premier exemple d'une telle série est donné par le problème des rencontres, ou problème du chevalier de Montmort (1708).
On peut le formuler de nombreuses manières. Par exemple, $n$ personnes se rendent à une soirée et déposent leur chapeau au vestiaire. En repartant, chacun reprend un chapeau au hasard. Quelle est la probabilité pour que personne n'ait son propre chapeau sur la tête ?
Si on numérote les invités et les chapeaux de 1 à $n$, et qu'on note $\sigma(i)$ le numéro du chapeau récupéré par l'invité $i$, $\sigma:\ \{1,2,\ldots,n\}\rightarrow \{1,2,\ldots,n\}$ est une permutation de l'ensemble $\{1,2,\ldots,n\}$.
Un point fixe d'une permutation est un élément $i$ tel que $\sigma(i)=i$.
On cherche donc à dénombrer les permutations sans point fixe, également appelées dérangements.
from itertools import permutations
permutations((1,2,3))
list(_) # c'est un itérateur, on convertit en liste
def perms(n):
return list(permutations(range(1,n+1)))
perms(3)
def is_derangement(p):
return not [i for i in range(1,len(p)+1) if p[i-1]==i] # attention aux indices qui commencent à 0
[p for p in perms(3) if is_derangement(p)]
def num_der(n):
return len([p for p in perms(n) if is_derangement(p)])
[num_der(n) for n in range(8)]
Soit $d_n$ le nombre de dérangements de $n$ objets.
On connaît le nombre total de permutations ($n!$). Parmi celles ci, il y en a $d_n$ qui n'ont pas de point fixe.
Et les autres ? Et bien, si on suppose connus $d_{n-1}$, $d_{n-2}$,..., $d_1=0$, $d_0=1$ (convention), on peut calculer le nombre de celles qui ont 1 point fixe, 2 points fixes, etc.
En effet, pour fabriquer une permutation avec exactement un point fixe, il y a $n$ manières de choisir le point fixe, et $d_{n-1}$ de permuter ce qui reste sans introduire de nouveau point fixe, soit au total $nd_{n-1}$ permutations.
Pour exactement 2 points fixes, on a ${n\choose 2}$ choix pour les points fixes, et $d_{n-2}$ possibilités pour permuter le reste. Et ainsi de suite : pour $k$ points fixes, on a ${n\choose k}$ choix pour les points fixes, et $d_{n-k}$ manières de permuter le reste.
Donc, $$n! = d_n +nd_{n-1}+{n\choose 2}d_{n-2}+\cdots{n\choose n-1}d_1+{n\choose n}d_0=\sum_{k=0}^n{n\choose k}d_{n-k}.$$ On peut alors écrire $$n!=\sum_{k=0}^n\frac{n!}{k!(n-k)!}d_{n-k}$$ et en simplifiant les $n!$ $$1 = \sum_{k=0}^n\frac1{k!}\frac{d_{n-k}}{(n-k)!}$$ On reconnaît la formule pour le produit des séries ! $$C(x)=A(x)B(x),\quad c_n=\sum_{k=0}^na_k b_{n-k},$$ avec $$c_n=1,\ a_k=\frac{1}{k!},\ b_{n-k}=\frac{d_{n-k}}{(n-k)!}$$ autrement dit, $$C(x) =\frac1{1-x},\ A(x)=e^x,\ B(x)=D(x)=\sum_{n\ge 0}\frac{d_n}{n!}x^n$$ et ainsi $$e^xD(x)=\frac1{1-x}, \ \text{soit finalement}\ D(x)=\frac{e^{-x}}{1-x}.$$ On peut maintenant développer le produit $$D(x)=\sum_{p\ge 0}\frac{(-x)^p}{p!}\sum_{q\ge 0}1\cdot x^q = \sum_{n\ge 0}\left(\sum_{p=0}^n\frac{(-1)^p}{p!}\right)x^n$$ et donc $$d_n =\sum_{p=0}^n(-1)^p\frac{n!}{p!}$$
# test
def fact(n):
if n<2: return 1
return n*fact(n-1)
def d(n):
return sum([(-1)**p*fact(n)//fact(p) for p in range(n+1)])
[d(n) for n in range(8)]
Cette formule pourait sembler décevante, dans la mesure où elle se présente sous forme d'une somme que l'on n'arrive pas à simplifier, et qui ne permet pas un calcul beaucoup plus efficace que la récurrence.
Mais si on s'intéresse à la probabilité $$p_n = \frac{d_n}{n!} = \sum_{p=0}^n\frac{(-1)^p}{p!}$$ on voit que c'est une somme partielle de la série (convergente) pour $e^{-1}$ $$e^{-1}=\frac1e = \sum_{p=0}^\infty\frac{(-1)^p}{p!}$$
from math import *
exp(-1)
[d(n)/fact(n) for n in range(1,11)]
On voit que pour $n=10$, la probabilité coincide déjà avec $e^{-1}$ sur les 7 premières décimales.
En fait, $|p_n-e^{-1}|<\frac1{(n+1)!}$ (dans une série alternée dont le terme général tend vers 0 en décroissant, l'erreur commise en approchant la somme par une somme partielle est inérieure au premier terme négligé).
Un autre problème classique qui peut se traiter par les séries exponentielles est celui du nombre de partitions d'un ensemble de $n$ éléments.
Une partition $\pi$ d'un ensemble $E$ est un ensemble de parties non vides (appelées blocs) et deux à deux disjointes de $E$, dont la réunion est $E$.
On s'intéresse au nombre $b_n$ de partitions de l'ensemble $[n]:=\{1,2,\ldots,n\}$, appelé $n$ième nombre de Bell.
Structure récursive : une partition de $[n]$, c'est soit une partition de $[n-1]$ à laquelle on a ajouté un bloc $\{n\}$, soit une partition de $[n-1]$ où on a inséré $n$ sans un bloc existant.
p =((1,3,6),(2,),(4,5)) # une partition de [6], représentée par un tuple de tuples
def insert_all(x,p): # p partition ensembliste, on insère x dans un bloc existant de toutes les manières possibles
return [p[:i] + ((x,)+p[i],) + p[i+1:] for i in range(len(p))]
insert_all(7,p)
def add_block(x,p): # ajout d'un nouveau bloc {x}
return ((x,),)+p
add_block(7,p)
from functools import reduce
def set_partitions(ll):
if not ll: return [tuple()]
else:
mm = set_partitions(ll[1:]); x=ll[0]
return [add_block(x,p) for p in mm] + reduce(lambda a,b:a+b, [insert_all(x,p) for p in mm])
set_partitions(range(1,5)) # Et voilà le travail ...
[len(set_partitions(range(1,n))) for n in range(2,8)]
Passons à la théorie. Pour fabriquer l'une des $b_n$ partitions de $[n]$, on peut
Au total, $$ b_n = b_{n-1}+(n-1)b_{n-2}+{n-1\choose 2}b_{n-3}+\cdots = \sum_{k=0}^{n-1}{n-1\choose k}b_{n-1-k}.$$ Comme précédemment, on écrit les binomiaux avec les factorielles $$b_n = \sum_{k=0}^{n-1}\frac{(n-1)!}{k!(n-1-k)!}b_{n-1-k}$$ c'est à dire $$\frac{b_n}{(n-1)!}=\sum_{k=0}^{n-1}\frac1{k!}\frac{b_{n-1-k}}{(n-1-k)!}$$ Ça ressemble encore à la formule du produit. En remplaçant $n$ par $n+1$, et en arrangeant un peu à gauche, il vient $$(n+1)\frac{b_{n+1}}{(n+1)!}=\sum_{k=0}^n\frac1{k!}\frac{b_{n-k}}{(n-k)!}$$ Si l'on pose $$B(x)=\sum_{n\ge 0}\frac{b_n}{n!}x^n$$ on voit que le membre droit est le coefficient de $x^n$ dans $e^xB(x)$.
Le membre gauche est quant à lui le coefficient de $x^n$ dans $B'(x)$.
Ainsi, $B(x)$ vérifie l'équation différentielle $$B'(x) = e^xB(x),\ \text{avec la condition initiale $B(0)=b_0=1$.}$$ Elle est facile à intégrer : $$\frac{B'(x)}{B(x)}=\frac{d}{dx}\ln B(x) = e^x$$ donc $$\ln B(x)=\int e^x dx + C = e^x +C$$ et $B(0)=1\Rightarrow \ln B(0)=\ln 1=0 =e^0+C=1+C$, donc $C=-1$ et finalement, $$B(x) = e^{e^x-1}.$$
Là encore, cette formule ne donne pas un moyen de calculer $b_n$ beaucoup plus efficace que la récurrence, mais elle conduit à une expression curieuse. On peut écrire $$B(x) = e^{e^x}e^{-1}=\frac1e\sum_{k\ge 0}\frac{(e^x)^k}{k!} =\frac1e\sum_{k\ge 0}\frac{e^{kx}}{k!} =\frac1e\sum_{k\ge 0}\frac1{k!}\sum_{n\ge 0}\frac{(kx)^n}{n!} $$ $$ =\frac1e \sum_{n\ge 0}\frac1{n!}\left(\sum_{k\ge 0}\frac{k^n}{k!}\right)x^n $$ et donc $$b_n=\frac1e \sum_{k\ge 0}\frac{k^n}{k!}.$$ C'est la formule de Dobiński.
Elle est étrange, car elle exprime un nombre entier comme quotient de deux nombres irrationnels.
def dobin(n,N): # N = nombre de termes
return sum([(k**n)/fact(k) for k in range(N)])/exp(1)
[dobin(n,10) for n in range(1,10)]
[round(dobin(n,10)) for n in range(1,10)]
On peut facilement raffiner les calculs précédents, pour compter les partitions de $[n]$ par nombre de blocs.
Si on note $S(n,k)$ le nombre de partitions de $[n]$ en $k$ blocs, et $$B_n(t) =\sum_{k=1}^nS(n,k)t^k,$$ on voit que la récurrence pour $b_n=B_n(1)$ devient
$$ B_n(t) = t \sum_{k=0}^{n-1}{n-1\choose k}B_{n-1-k}(t),$$puisque le $k$ème terme décrit une partition obtenue en ajoutant un bloc à une partition d'un ensemble de $n-1-k$ éléments. L'équation différentielle devient $$\frac{d}{dx}{\mathcal B(x;t)} = te^x{\mathcal B(x;t)}, \quad {\mathcal B(0;t)}=1$$ et la solution est $${\mathcal B(x;t)} =e^{t(e^x-1)}.$$ Les polynômes $B_n(t)$ sont appelés polynômes de Touchard, ou de Bell. Les $S(n,k)$ sont les nombres de Stirling de seconde espèce, dont on verra plus loin une autre définition.