Formule de Dobiński

En Combinatoire, la formule de Dobiński donne une expression du n -ième nombre de Bell $B_{n}$ (c'est-à-dire le nombre de partitions d'un ensemble de taille n ) sous forme de somme de série :

$B_{n}={1 \over e}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.$

La formule porte le nom de G. Dobiński, qui l'a publiée en 1877.

Version probabiliste

Dans le cadre de la théorie des probabilités, la formule de Dobiński exprime le n-ième moment de la distribution de Poisson de moyenne 1. Parfois, la formule de Dobiński est énoncée comme disant que le nombre de partitions d'un ensemble de taille n est égal au n-ième moment de cette distribution.

Formule réduite

Le calcul de la somme de la série de Dobiński peut être réduit à une somme finie de n + o (n) termes, en tenant compte des l'information que $B_{n}$ est un entier. Précisément, on a, pour tout entier $K>1$ vérifiant ${\frac {K^{n}}{K!}}\leqslant 1$ :

$B_{n}=\left\lceil {1 \over e}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}\right\rceil$

où $\left\lceil .\right\rceil$ est la partie entière supérieure.

En effet, on a ${\frac {(K+j)^{n}}{(K+j)!}}\leqslant {\frac {K^{n}}{K!}}{1 \over j!}\leqslant {1 \over j!}$ pour tout $j\geqslant 0$ , de sorte que le reste $\sum _{k\geqslant K}{\frac {k^{n}}{k!}}=\sum _{j\geqslant 0}{\frac {(K+j)^{n}}{(K+j)!}}$ est dominé par la série $\sum _{j\geqslant 0}{\frac {1}{j!}}=e$, ce qui implique $0<B_{n}-{1 \over e}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}<1$, d'où la formule réduite.

La condition ${\frac {K^{n}}{K!}}\leqslant 1$ implique $K>n$ mais est satisfaite par un certain $K$ de taille $n+o(n)$ .

Généralisation

La formule de Dobiński peut être vue comme le cas particulier, pour $x=0$, de la relation plus générale :

${1 \over e}\sum _{k=x}^{\infty }{\frac {k^{n}}{(k-x)!}}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}x^{n-k}.$

Démonstration de la formule de Dobiński

Une preuve repose sur la formule de la fonction génératrice des nombres de Bell ,

$e^{e^{x}-1}=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}.$

Le développement en série entière de l'exponentielle donne

$e^{e^{x}}=\sum _{k=0}^{\infty }{\frac {e^{kx}}{k!}}=\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{n=0}^{\infty }{\frac {(kx)^{n}}{n!}}$

d'où

$e^{e^{x}-1}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{n=0}^{\infty }{\frac {(kx)^{n}}{n!}}$

Le coefficient de $x^{n}$ dans cette série doit être $B_{n}/n!$, donc

$B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.$

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Dobiński's formula » (voir la liste des auteurs).