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

$$B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}$$

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

$$(x)_{n} = \frac{x!}{(x-n)!}$$

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:

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

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:

$$f = f_2 \circ f_1$$

where we have:

$$f_1 : A \rightarrow \text{Ker}(f)$$

$$f_2 : \text{Ker}(f) \rightarrow B$$

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:

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

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

$$(x)_{|\pi|} = \frac{x!}{(x-|\pi|)!}$$

It follows that the total number of functions from $$A$$ to $$B$$ is:

$$\sum_{\pi} (x)_{|\pi|} = x^n$$

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:

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

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

$$\frac{1}{e} \sum_{k=0}^{\infty} \frac{1}{k!} = 1$$

and so (10) simplifies to:

$$\mathbb{E}[X^n] = \sum_{\pi} 1$$

which is the number of partitions of $$A$$.

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

$$\sum_{\pi} 1 = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}$$

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