Counting set partitions with Dobinski's formula
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. onetoone) functions that map a set of size \(n\) to a set of size \(x\) is given by:
\begin{equation} (x)_{n} = \frac{x!}{(xn)!} \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. onetoone).
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 onetoone 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 Poissondistributed 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 Poissondistributed 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:

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.

Rota, G.C. “The Number of Partitions of a Set.” Amer. Math. Monthly 71, 498504, 1964.

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