Formule de Dobiński

formule mathématique (combinatoire)

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

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

Version probabiliste

modifier

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

modifier

Le calcul de la somme de la série de Dobiński peut être réduit à une somme finie de   termes, en tenant compte du fait que   est un entier. Précisément, on a, pour tout entier   vérifiant   :

 

  est la partie entière supérieure.

En effet, on a   pour tout   , de sorte que le reste   est dominé par la série  , ce qui implique  , d'où la formule réduite.

La condition   implique   mais est satisfaite par un certain   de taille   .

Généralisation

modifier

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

 

Démonstration de la formule de Dobiński

modifier

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

 

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

 

d'où

 

Le coefficient de   dans cette série doit être  , donc

 

Notes et références

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

Liens externes

modifier

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