In combinatorial

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

 mathematics, Dobinski’s formula states that the number of partitions of a set

Partition of a set

In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

 of n members is


This number has come to be called the nth Bell number

Bell number

In combinatorics, the nth Bell number, named after Eric Temple Bell, is the number of partitions of a set with n members, or equivalently, the number of equivalence relations on it...

 B_n, after Eric Temple Bell

Eric Temple Bell

Eric Temple Bell , was a mathematician and science fiction author born in Scotland who lived in the U.S. for most of his life...

.

The above formula can be seen as a particular case, for , of the more general relation:

Probabilistic content

Those familiar with probability theory

Probability theory

Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...

 will recognize the expression given by Dobinski's formula as the nth moment

Moment (mathematics)

In mathematics, a moment is, loosely speaking, a quantitative measure of the shape of a set of points. The "second moment", for example, is widely used and measures the "width" of a set of points in one dimension or in higher dimensions measures the shape of a cloud of points as it could be fit by...

 of the Poisson distribution

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 and/or space if these events occur with a known average rate and independently of the time since...

 with expected value

Expected value

In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

 1. Today, Dobinski's formula is sometimes stated by saying the number of partitions of a set of size n equals the nth moment of that distribution.

A proof

The proof given here is an adaptation to probabilistic language, of the proof given by Rota

Gian-Carlo Rota

Gian-Carlo Rota was an Italian-born American mathematician and philosopher.-Life:Rota was born in Vigevano, Italy...

.

Combinatorialists use the Pochhammer symbol

Pochhammer symbol

In mathematics, the Pochhammer symbol introduced by Leo August Pochhammer is the notation ', where is a non-negative integer. Depending on the context the Pochhammer symbol may represent either the rising factorial or the falling factorial as defined below. Care needs to be taken to check which...

 (x)_n to denote the falling factorial


(whereas, in the theory of special functions, the same notation denotes the rising factorial). If x and n are nonnegative integers, 0 ≤ n ≤ x, then (x)_n is the number of one-to-one functions that map a size-n set into a size-x set.

Let ƒ be any function from a size-n set A into a size-x set B. For any u ∈ B, let ƒ ⁻¹(u) = {v ∈ A : ƒ(v) = u}. Then {ƒ ⁻¹(u) : u ∈ B} is a partition of A, coming from the equivalence relation

Equivalence relation

In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

 of "being in the same fiber". This equivalence relation is called the "kernel" of the function ƒ. Any function from A into B factors into

• one function that maps a member of A to that part 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ⁿ. Therefore we have


If X is a Poisson-distributed

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 and/or space if these events occur with a known average rate and independently of the time since...

 random variable

Random variable

In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...

 with expected value

Expected value

In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

 1, then we get that the nth moment of this probability distribution is


But all of the factorial moments E((X)_k) of this probability distribution are equal to 1. Therefore


and this is just the number of partitions of the set A. Q.E.D.