Motivation:

Given a particular equivalence relation on a finite set \(X\), its equivalence classes define a partition on \(X\). Likewise, a partition on \(X\) corresponds to an equivalence relation on \(X\).

But, what can we use to count the number of partitions of a set of size \(n\)?

Counting set partitions with Dobinski’s formula:

Dobinski’s formula states that the number of partitions of a set of size \(n\), also known as the nth Bell number, is given by:

\begin{equation} B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!} \end{equation}

An adaptation of Rota’s proof:

The number of injective(i.e. one-to-one) functions that map a set of size \(n\) to a set of size \(x\) is given by:

\begin{equation} (x)_{n} = \frac{x!}{(x-n)!} \end{equation}

assuming that \(x \geq n\).

Now, let \(f\) be any function from a set \(A\) where \(\lvert A \rvert = n\) and a set \(B\) where \(\lvert B \rvert = x\). If we define:

\begin{equation} \forall b \in B, f^{-1}(b) = \{a \in A: f(a) = b\} \end{equation}

then \(\{f^{-1}(b): b \in B\}\) corresponds to \(\text{Ker}(f)\) in set theory, a partition of \(\text{Dom}(f)\).

It follows that any function \(f: A \rightarrow B\) factors into:

\begin{equation} f = f_2 \circ f_1 \end{equation}

where we have:

\begin{equation} f_1 : A \rightarrow \text{Ker}(f) \end{equation}

\begin{equation} f_2 : \text{Ker}(f) \rightarrow B \end{equation}

and \(f_2\) is necessarily injective(i.e. one-to-one).

The first of these two factors is completely determined by the partition \(\pi\) that is the Kernel:

\begin{equation} \pi := \text{Ker}(f) = \bigcup_{i=1}^{|\pi|} A_i \implies A_i \cap A_{j \neq i} = \emptyset \end{equation}

The number of one-to-one functions from \(\pi\) into \(B\) is:

\begin{equation} (x)_{|\pi|} = \frac{x!}{(x-|\pi|)!} \end{equation}

It follows that the total number of functions from \(A\) to \(B\) is:

\begin{equation} \sum_{\pi} (x)_{|\pi|} = x^n \end{equation}

Now, we note that since (9) holds for all integers \(x \in \mathbb{N}\) we could replace \(x\) with a discrete random variable without loss of generality. For convenience, let’s choose \(X\) to be Poisson-distributed with mean \(1\) and apply the expected value operator to both sides of the equation:

\begin{equation} \mathbb{E}[X^n] = \sum_{\pi} \mathbb{E} [(X)_{|\pi|}] \end{equation}

If we consider the right hand side of (10) then we note that \(\sum_{\pi} \mathbb{E} [(X)_{\lvert \pi \rvert}]\) simplifies to:

\begin{equation} \frac{1}{e} \sum_{k=0}^{\infty} \frac{1}{k!} = 1 \end{equation}

and so (10) simplifies to:

\begin{equation} \mathbb{E}[X^n] = \sum_{\pi} 1 \end{equation}

which is the number of partitions of \(A\).

And given that \(X\) is Poisson-distributed with mean 1, (12) simplifies to:

\begin{equation} \sum_{\pi} 1 = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!} \end{equation}

References:

  1. Dobiński, G. (1877). “Summirung der Reihe {\displaystyle \textstyle \sum {\frac {n^{m}}{n!}}}\textstyle\sum\frac{n^m}{n!} für m = 1, 2, 3, 4, 5, …”. Grunert’s Archiv (in German). 61: 333–336.

  2. Rota, G.-C. “The Number of Partitions of a Set.” Amer. Math. Monthly 71, 498-504, 1964.

  3. Wilf, H. Generatingfunctionology, 2nd ed. New York: Academic Press, 1994.