Formule de Dobiński

En combinatoire, la formule de Dobiński [1] donne une expression du nombre de Bell ${\displaystyle B_{n}}$ de rang n (c'est-à-dire du nombre de partitions d'un ensemble de taille n) sous forme de somme de série :

${\displaystyle B_{n}={1 \over {\rm {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 loi 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 loi.

Formule réduite

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

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

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

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

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

Généralisation

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

${\displaystyle {1 \over {\rm {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 [2] repose sur la formule de la fonction génératrice des nombres de Bell ,

${\displaystyle {\rm {e}}^{{\rm {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

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

d'où

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

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

${\displaystyle B_{n}={\frac {1}{\rm {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).

1. (de) Dobiński, « Summirung der Reihe ${\displaystyle \textstyle \sum {\frac {n^{m}}{n!}}}$ für m = 1, 2, 3, 4, 5, … », Grunert's Archiv, vol. 61,‎ 1877, p. 333–336 (lire en ligne)
2. Edward A. Bender et S. Gill Williamson, Foundations of Combinatorics with Applications, Dover, 2006, 319–320 p. (ISBN 0-486-44603-4, lire en ligne), « Theorem 11.3, Dobiński's formula »

Liens externes

(en) Eric W. Weisstein, « Dobiński's Formula », sur MathWorld