## 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}

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.