In
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
mathematics, Dobiński's formula states that the ''n''-th
Bell number
In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy ...
''B''
''n'' (i.e., the number of
partitions of a set
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of size ''n'') equals
:
where
denotes
Euler's number
The number , also known as Euler's number, is a mathematical constant approximately equal to 2.71828 that can be characterized in many ways. It is the base of the natural logarithms. It is the limit of as approaches infinity, an expressi ...
.
The formula is named after G. Dobiński, who published it in 1877.
Probabilistic content
In the setting of
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
, Dobiński's formula represents the ''n''th
moment of the
Poisson distribution
In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time or space if these events occur with a known co ...
with
mean
There are several kinds of mean in mathematics, especially in statistics. Each mean serves to summarize a given group of data, often to better understand the overall value (magnitude and sign) of a given data set.
For a data set, the '' ari ...
1. Sometimes Dobiński's formula is stated as saying that the number of partitions of a set of size ''n'' equals the ''n''th moment of that distribution.
Reduced formula
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.
Generalization
Dobiński's formula can be seen as a particular case, for
, of the more general relation:
:
Proof
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 function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
s 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'') = . Then is a partition of ''A''. Rota calls this partition the "
kernel
Kernel may refer to:
Computing
* Kernel (operating system), the central component of most operating systems
* Kernel (image processing), a matrix used for image convolution
* Compute kernel, in GPGPU programming
* Kernel method, in machine learn ...
" 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 that is the kernel. The number of one-to-one functions from into ''B'' is (''x'')
, , , where , , is the number of parts in the partition . Thus the total number of functions from a size-''n'' set ''A'' into a size-''x'' set ''B'' is
:
the index running through the set of all partitions of ''A''. On the other hand, the number of functions from ''A'' into ''B'' is clearly ''x''
''n''. Therefore, we have
:
Rota continues the proof using linear algebra, but it is enlightening to introduce a
Poisson-distributed random variable ''X'' with
mean
There are several kinds of mean in mathematics, especially in statistics. Each mean serves to summarize a given group of data, often to better understand the overall value (magnitude and sign) of a given data set.
For a data set, the '' ari ...
1. The equation above implies that the ''n''th moment of this random variable is
:
where ''E'' stands for
expected value. But we shall show that all the quantities ''E''((''X'')
''k'') equal 1. It follows that
:
and this is just the number of partitions of the set ''A''.
The quantity ''E''((''X'')
''k'') is called the ''k''th
factorial moment In probability theory, the factorial moment is a mathematical quantity defined as the expected value, expectation or average of the falling factorial of a random variable. Factorial moments are useful for studying non-negative integer-valued random ...
of the random variable ''X''. To show that this equals 1 for all ''k'' when ''X'' is a Poisson-distributed random variable with mean 1, recall that this random variable assumes each value integer value
with probability
. Thus
:
Notes and references
{{DEFAULTSORT:Dobinski's formula
Combinatorics
Poisson point processes
Articles containing proofs