Dobiński's formula

In combinatorial mathematics, Dobiński's formula states that the n-th Bell number Bn (i.e., the number of partitions of a set of size n) equals where denotes Euler's number. The formula is named after G. Dobiński, who published it in 1877. In the setting of probability theory, Dobiński's formula represents the nth moment of the Poisson distribution with mean 1. Sometimes Dobiński's formula is stated as saying that the number of partitions of a set of size n equals the nth moment of that distribution. The computation of the sum of Dobiński's series can be reduced to a finite sum of terms, taking into account the information that is an integer. Precisely one has, for any integer provided (a condition that of course implies , but that is satisfied by some of size ). Indeed, since , one has Therefore for all so that the tail is dominated by the series , which implies , whence the reduced formula. Dobiński's formula can be seen as a particular case, for , of the more general relation: and for in this formula for Touchard polynomials One proof relies on a formula for the generating function for Bell numbers, The power series for the exponential gives so The coefficient of in this power series must be , so Another style of proof was given by Rota. Recall that if x and n are nonnegative integers then the number of one-to-one functions that map a size-n set into a size-x set is the falling factorial Let ƒ be any function from a size-n set A into a size-x set B. For any b ∈ B, let ƒ −1(b) = {a ∈ A : ƒ(a) = b}. Then {ƒ −1(b) : b ∈ B} is a partition of A. Rota calls this partition the "kernel" of the function ƒ. Any function from A into B factors into one function that maps a member of A to the element of the kernel to which it belongs, and another function, which is necessarily one-to-one, that maps the kernel into B. The first of these two factors is completely determined by the partition pi that is the kernel. The number of one-to-one functions from pi into B is (x)|pi|, where |pi| is the number of parts in the partition pi.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (2)

Stirling numbers of the second kind

In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling. The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices.

Partition of a set

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset. Every equivalence relation on a set defines a partition of this set, and every partition defines an equivalence relation. A set equipped with an equivalence relation or a partition is sometimes called a setoid, typically in type theory and proof theory. A partition of a set X is a set of non-empty subsets of X such that every element x in X is in exactly one of these subsets (i.