En mathématiques des concepts relativement simples peuvent conduire à des formules complexes dont les preuves sont des bijoux d’ingéniosité. Un bon exemple sur lequel je viens de travailler quelques jours : Les nombres de Bell (ainsi nommés en l’honneur du mathématicien Eric Temple Bell) qui désignent le nombre de partitions d’un ensemble à \(n\) éléments distincts. Un peu comme pour la factoriel, il n’existe pas d’expression analytique "simple" de cette suite \(B_n\) de nombres entiers mais on trouve quand même un équivalent pour \(n\to\infty\) faisant intervenir la fonction W de Lambert:
Commençons par rappeler ce qu’est une partition
i) \(\cup_{i}A_i=E\) ii) \(\forall i\neq j,\; A_i\cap A_j=\emptyset\) iii) \(\forall i,\; A_i\neq\emptyset\).
on note \(B_n=\)le nombre de partitions d’un ensemble à \(n\) éléments distincts
par exemple
\(B_1=1\) car la seule partition possible de l’ensemble \(E=\{1\}\) c’est \(\{E\}\)
\(B_2=2\) car il y a 2 partitions de \(E=\{1,2\}\) qui sont \(\{E\}\) et \(\{\{1\},\{2\}\}\)
\(B_3=5\) car pour \(E=\{1,2,3\}\) \[\begin{aligned} \text{partition à 1 ensemble~}&:\{E\}\\ \text{partition à 2 ensembles}&:\{\{1\},\{2,3\}\} ~~\{\{2\},\{1,3\}\}~~\{\{3\},\{1,2\}\}\\ \text{partition à 3 ensembles}&:\{\{1\},\{2\},\{3\}\}\end{aligned}\]
La valeur \(B_0=1\) (nombre de partitions de l’ensemble vide) peut sembler arbitraire mais elle va se révéler bien utile ensuite. Cette manière de compter les partitions d’un ensemble en les regroupant par nombre de sous-ensemble permet d’obtenir une formule récurrente de calcul des nombres \(B_n\).
une partition d’un ensemble à \(n+1\) éléments \(E=\{1,2,\dots,n,n+1\}\) peut s’obtenir comme un ensemble contenant \(n+1\) et une partition du reste de l’ensemble. Il suffit maintenant de classer les partitions suivant l’ensemble contenant \(n+1\) :
\(\{n+1\}\) et une partition du reste \(\to C_n^0B_n\)
\(\{n+1,k\}\) et une partition du reste \(\to C_n^1B_{n-1}\)
\(\{n+1,k,l\}\) et une partition du reste \(\to C_n^2B_{n-2}\)
\(E\) tout seul (et une partition du reste vide) \(\to C_n^n=1\)
avec la convention \(B_0=1\) et en sommant on obtient bien \(B_{n+1}=\sum_{k=0}^n C_n^k B_{n-k}\) et par changement d’indice \(k\to n-k\) on obtient la deuxième formule puisque \(C_n^k=C_n^{n-k}\). On peut ainsi facilement calculer les termes suivant de la suite
\(B_4=C_3^0B_3+C_3^1B_2+C_3^2B_1+C^3_3 B_0= 1\times 5+3\times 2+3\times 1+1\times 1=15\)
\(B_5=C_4^0B_4+C_4^1B_3+C_4^2B_2+C^4_3 B_1+C_4^4B_0= 1\times 15+4\times 5+6\times 2+4\times 1+1\times 1=52\)
\(B_6=52+5\times 15+10\times 5+10\times 2+5\times 1+1=203\)
cette suite semble croître exponentiellement vite, on peut donner un premier encadrement de son comportement :
pour les premières valeurs de \(n\leq 6\) on a \(B_n\leq n!\) donc par récurrence : \[\begin{aligned} B_{n+1}&=\sum_{k=0}^{n} C_{n}^k \times B_{n-k}\leq \sum_{k=0}^{n} C_{n}^k \times (n-k)!= \sum_{k=0}^{n} {n!\over k!}\leq e \times {n!}\leq (n+1)!\end{aligned}\]
si on minore \(B_n\geq 1\) alors on peut obtenir successivement : \[\begin{aligned} B_n&\geq \sum_{k=0}^{n-1} C_{n-1}^k \times 1= (1+2)^{n-1}=2^{n-1}\\ B_n&\geq \sum_{k=0}^{n-1} C_{n-1}^k \times 2^{k-1}= {(1+2)^{n-1}\over 2}= {3^{n}\over 2\times 3}\\ B_n&\geq \sum_{k=0}^{n-1} C_{n-1}^k \times {3^{k}\over 2\times 3}= {(1+3)^{n-1}\over 2\times 3}= {4^{n}\over 4!}\\ &\dots\\ B_n&\geq \sum_{k=0}^{n-1} C_{n-1}^k \times {(p-1)^{k}\over (p-1)!}= {(1+p-1)^{n-1}\over (p-1)!}= {p^{n}\over p!}\\\end{aligned}\] La minoration est plus intéressante car, lorsque \(n\to\infty\), on minore \(B_n\) par une croissance exponentielle de plus en plus grande, mais à \(n\) fixée la minoration est de plus en plus mauvaise quand \(p\) augmente. Il existe donc une valeur optimale du minorant en fonction de \(p\). Pour la trouver on peut chercher un extremum du logarithme : \[\ln\left({p^n\over p!}\right)=n\ln(p)-\sum_{k=1}^p\ln(k) =\underbrace{n\ln(p)-p\ln(p)+p-{\ln(p)\over 2}-\ln(\sqrt{2\pi})}_{=\phi(p)}+{\cal O}\left(1\over p\right)\] En cherchant les points où la dérivée s’annule \[{d\phi(p)\over dp} ={n\over p}-\ln(p)-{1\over 2p}=0\Rightarrow n=p\ln(p)+{1\over 2}\Rightarrow p={n-1/2\over W(n-1/2)}\sim_{\infty }{n\over \ln(n)}\] Où \(W(n)\) est la fonction de Lambert. En utilisant la valeur plus simple \(n=p\ln(p)\) et la formule de Stirling on en déduit un minorant plus explicite : \[B_n\geq {p^n\over p!}\sim_\infty\left({e\over p}\right)^{p}{p^n\over \sqrt{2\pi p}} \sim_\infty { {e^{p-1}p^{n-p-1/2}}\over \sqrt{2\pi}} ~~avec~~ p={n\over W(n)}\sim_{\infty }{n\over \ln(n)}\] ce qui est très proche de l’équivalent de \(B_n\) trouvé par Moser et Wyman en 1955 . En fait cette minoration contient déjà le terme principal pour estimer les nombres de Bell.
L’approche la plus générale pour étudier une suite définie par une relation de récurrence consiste à étudier une série génératrice associée qui permette d’exprimer les termes de la suite sous forme d’intégrale par le théorème des résidus :
\[F(z)=\sum_{n\geq 0}a_nz^n\Rightarrow a_n={1\over 2i\pi}\oint {F(z)\over z^{n+1}} dz\]
Dans notre cas on va ainsi établir une formule qui exprime les nombres de Bell sous forme d’une série convergente grâce à une série génératrice (exponentielle):
On pose \(G(x)=\sum_{n=0}^\infty {B_n\over n!}x^n\), comme \(1\leq B_n\leq n!\) le critère de d’Alembert assure que le rayon de convergence de la série entière est au moins \(1\). On va déterminer \(G(x)\) par une équation différentielle : \[\begin{aligned} G(x)&=\sum_{n=0}^\infty {B_n\over n!}x^n=1+\sum_{n=0}^\infty {B_{n+1}\over (n+1)!}x^{n+1}\\ \Rightarrow G'(x)&=0+\sum_{n=0}^\infty {B_{n+1}\over n!}x^{n} &\text{dérivation terme à terme}\\ &=\sum_{n=0}^\infty\sum_{k=0}^\infty C_n^k {B_{k}\over n!}x^{n}&\text{formule de récurrence des $B_k$}\\ &=\sum_{n=0}^\infty\sum_{k=0}^\infty {B_{k}\over k!}x^{k}\times {x^{n-k}\over (n-k)!}&\text{formule du produit de séries}\\ &=\left(\sum_{k=0}^\infty {B_{k}\over k!}x^{k}\right)\times \left( \sum_{k=0}^\infty {x^{k}\over k!}\right)&\text{reconnaitre $G$ et $e^x$}\\ &=G(x)\times e^x&\text{équation différentielle sur $G$}\\\end{aligned}\] on a donc \(G(x)=c\times \exp(e^x)\) avec \(c=e^{-1}\) pour que \(G(0)=B_0=1\). D’un autre côté on a par le développement en série entière de \(e^x\) valable \(\forall x\in\mathbb{R}\) : \[\begin{aligned} e^{e^x}&=\sum_{k=0}^\infty {e^{kx}\over k!} =\sum_{k=0}^\infty\sum_{n=0}^\infty {(kx)^n\over k!n!} =\sum_{n=0}^\infty \left(\sum_{k=0}^\infty {k^n\over k!}\right) {x^n\over n!} =e\sum_{n=0}^\infty {B_n\over n!}x^n \end{aligned}\] par unicité du développement en série entière on peut identifier les deux séries et obtenir \(B_n={1\over e }\sum_{k=0}^\infty {k^n\over k!}\).
C’est en étudiant cette série génératrice que Moser et Wyman ont obtenu l’équivalent de \(B_n\), mais on peut déduire cet équivalent directement à partir de la formule de Dobinski et sans utiliser le théorème des résidus ! Pour cela il faut couper la série en deux pour la valeur \(k\approx {n\over W(n)}\) (maximum du terme \(k^n\over k!\) ) et montrer par comparaison série/intégrale que chacune des deux parties est équivalente à \({1\over 2}\times { e^{p-1}p^{n-p}\over \sqrt{\ln(p)}}\) . La méthode repose sur le lemme suivant qui est une sorte d’équivalent discret au théorème de la phase stationnaire :
On commence par exprimer \(t_{n,k}\) en fonction des rapport des termes consécutifs : \[t_{n,k}={t_{n,k}\over t_{n,k-1}}\times {t_{n,k-1}\over t_{n,k}-2}\times \dots \times {t_{n,1}\over t_{n,0}}\times t_{n,0}\] de sorte qu’en passant au logarithme on est ramené au calcul d’une série arithmétique \[\begin{aligned} \ln(t_{n,k})&=\sum_{j=0}^{k-1}\ln\left({t_{n,j+1}\over t_{n,j}}\right) +\ln(t_{n,0}) =\sum_{j=0}^{k-1}-jf(n)(1+{ o}\left(1\right)) +\ln(t_{n,0})\\ &=-{k^2\over 2}f(n)(1+{ o}\left(1\right)) +\ln(t_{n,0}) \Rightarrow t_{n,k}=t_{n,0}e^{-{k^2\over 2}f(n)}(1+{ o}\left(k^2 f(n)\right) )\end{aligned}\] Avec cette expression on se ramène par comparaison série/intégrale à une intégrale Gaussienne : \[\begin{aligned} \sum_{k=0}^\infty e^{-{k^2\over 2}f(n)} &=\int_0^\infty e^{-{x^2\over 2}f(n)} dx+ {\cal O}\left(1\right) ={1\over 2}\sqrt{2\pi\over f(n)}+{\cal O}\left(1\right)\sim_{n\to\infty}\sqrt{\pi\over 2 f(n)}\end{aligned}\] On a négligé dans la somme le terme \(\sum_{k=0}^\infty o\left( k^2 f(n) e^{-{k^2\over 2}f(n)}\right)=o(1)\) car \[\begin{aligned} \sum_{k=0}^\infty k^2 f(n) e^{-{k^2\over 2}f(n)} &=\int_0^\infty x^2 f(n)e^{-{x^2\over 2}f(n)} dx+ {\cal O}\left(1\right) &\text{avec } y=x\sqrt{f(n)}\\ &=\int_0^\infty y^2e^{-{y^2\over 2}} dx+ {\cal O}\left(1\right) =\mathcal{O}(1)\end{aligned}\]
Il ne reste plus qu’à appliquer ce lemme à chaque partie de la série de Dobinski. On pose \(t_{n,k}={(k+p)^n\over (k+p)!}\) avec \(p\ln(p)=n\) (car \(k^n/k!\) atteint son maximum en \(k\approx p\)) et on a quand \(n\to\infty\) \[\begin{aligned} \ln\left({t_{n,k+1}\over t_{n,k}}\right) &=\ln\left({(k+p+1)^n\over (k+p+1)!}{ (k+p)!\over (k+p)^n}\right)\\ &=n\ln\left(1+{1\over k+p}\right)-\ln(k+p+1)\\ &\sim {n\over k+p}-\ln({p+ k})= {p\ln(p)\over k+p}-\ln({p+ k})\\ &\sim {\ln(p)\over 1+{k\over p}}-\ln(p)-\ln\left(1+{k\over p}\right)\\ &\sim {\ln(p)-{k\ln(p)\over p}}-\ln(p)-{k\over p} \sim -k{\ln(p)\over p}=-k f(n)\end{aligned}\] on prend donc \(f(n)={\ln(p)\over p}\) avec \(p={n\over W(n)}\) et on en déduit que \[\sum_{k=p}^\infty {k^n\over k!}\sim_{n\to\infty} {p^n\over p!} \times \sqrt{\pi\over 2f(n)} \sim_{n\to\infty} {p^n\over p!} \times \sqrt{\pi p\over 2 \ln(p)}\]
Par symétrie le même équivalent s’applique à la première partie de la somme si on remarque astucieusement que : \[\ln\left({t_{n,p-(k+1)}\over t_{n,p-k}}\right)=-\ln\left({t_{n,p-k}\over t_{n,p-k-1}}\right)\sim -1\times (-1)\times-k{\ln(p)\over p}\] la somme n’est pas infinie (seulement \(p\sim n/ln(n)\) termes) mais la décroissance exponentielle assure que le reste non calculé est exponentiellement petit en \(n\) et donc négligeable \[\sum_{k=0}^{p} {k^n\over k!}=\sum_{k=0}^{-p} {(k+p)^n\over (k+p)!} \sim_{n\to\infty} {p^n\over p!} \times \sqrt{\pi p\over 2 \ln(p)}\]
Il ne reste plus qu’à ajouter les deux morceaux (si le terme \(p^n/n!\) est compté 2 fois ce n’est pas grave il est négligeable devant les 2 sommes) puis à diviser par le facteur \(1/e\) de la formule de Dobinski
\[\begin{aligned} B_n&={1\over e }\sum_{k=0}^\infty {k^n\over k!} ={1\over e }\left( \sum_{k=0}^{p-1} {k^n\over k!}+\sum_{k=p}^\infty {k^n\over k!}\right) \sim_{n\to\infty} {1\over e }{p^n\over p!} \left( \sqrt{\pi p\over 2 \ln(p)}+\sqrt{\pi p\over 2 \ln(p)} \right)\\ &\sim_{n\to\infty} {1\over e }\left({e\over p}\right)^{p}{p^n\over \sqrt{2\pi p}} \times \sqrt{2\pi p\over \ln(p)} \sim_{n\to\infty} {p^{n-p}e^{p-1}\over \sqrt{ \ln(p)}}\end{aligned}\]
On ne trouve pas forcément l’équivalent sous la forme donnée ici, par exemple sur le site mathworld , mais on peut retrouver cette autre formule en utilisant un équivalent pour la fonction W de Lambert \(p={n\over W(n)}\Leftrightarrow p\ln(p)=n\)
\[\begin{aligned} B_n&\sim_\infty{ e^{p-1}p^{n-p}\over \sqrt{\ln(p)}} \sim_\infty\left({n\over W(n)}\right)^{n-{n\over W(n)}} e^{{n\over W(n)}-1}{1\over \sqrt{\ln(p)}} \\ &\sim_\infty\left({n\over W(n)}\right)^{n+{1\over2}}\left({n\over W(n)}\right)^{-{1\over2}-{n\over W(n)}}e^n e^{{n\over W(n)}-n-1}{1\over \sqrt{\ln(p)}} \\ &\sim_\infty\left({n\over W(n)}\right)^{n+{1\over2}} \underbrace{e^{-\ln \left({n\over W(n)}\right){n\over W(n)}+n}}_{=e^0=1}\times e^{{n\over W(n)}-n-1}\underbrace{\sqrt{W(n)\over n\ln(p)}}_{W(n)\sim\ln(p)\sim\ln(n)} \\ &\sim_\infty\left({n\over W(n)}\right)^{n+{1\over2}} e^{{n\over W(n)}-n-1}{1\over \sqrt{n}} \\\end{aligned}\]
Et, comme l’a dit Eric Temple Bell, rappelez vous que :
"Obvious" is the most dangerous word in mathematics.
références :
- https://fr.wikipedia.org/wiki/Nombre_de_Bell
- https://fr.wikipedia.org/wiki/Fonction_W_de_Lambert
- https://mathworld.wolfram.com/BellNumber.html
- Moser, Leo; Wyman, Max An asymptotic formula for the Bell numbers. Trans. Roy. Soc. Canada Sect. III 49 (1955), 49–54. https://oeis.org/A000110/a000110_4.pdf
Merci!!!!!!! Très intéressant!!!!!
RépondreSupprimer