Dobiński's formula

Dobiński's formula is a mathematical expression that provides a means to calculate the nth Bell number. Bell numbers are significant in combinatorics, as they represent the number of ways a set with n elements can be partitioned into non-empty subsets. The formula is named after the Polish mathematician G. Dobiński, who introduced it in 1877.

Definition

Dobiński's formula states that the nth Bell number can be expressed as:

$$B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}$$

where e is the base of the natural logarithm, approximately equal to 2.71828, and k! denotes the factorial of k.

Derivation

The derivation of Dobiński's formula involves generating functions and the exponential function. It is derived from the moment generating function of the Poisson distribution, reflecting the deep connection between combinatorial identities and probability theory.

Applications

Dobiński's formula has applications in various fields of mathematics and computer science, especially in combinatorics, graph theory, and the analysis of algorithms. It is used to understand the partitioning of sets, the structure of graphs, and the behavior of certain algorithms.

Example

To calculate the 3rd Bell number using Dobiński's formula:

$$B_3 = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^3}{k!}$$

This series converges to approximately 5, which is the third Bell number, indicating there are five ways to partition a set of three elements.

See Also

• Bell numbers
• Combinatorics
• Partition (number theory)
• Poisson distribution

References

• G. Dobiński, "Summierung der Reihe Σn^n/n! für n=1 bis ∞," Arch. Math. Phys., vol. 61, pp. 333-336, 1877.