Constructing a bijection to show that the number of equivalence relations on a finite set is equal to the bell numbers.

Question

It is said that the Bell numbers count the number of partitions of a finite set. How can we prove that what they count is actually the number of partitions? I don't want to take it as a definition; I want to prove the correspondence between bell numbers and the cardinality of the partitions. Is there a way to construct a bijection between the partitions of a finite set with cardinality $k$ and some other set whose cardinality is $B_k$ (basically a set-theoretic cardinality argument)?

Answer 1

Hint: Bell numbers are defined by $$B_{n+1}=\sum _{k=0}^n\binom{n}{k}B_k,B_0=1$$ Call the set of partitions of $[n]=\{1,\cdots ,n\}$ by $P([n])=\{\pi:\pi \vdash [n]\}.$ So consider the following function $$\varphi :P([n+1])\longrightarrow \bigcup _{k=0}^n\binom{[n]}{k}\times P([n-k]),$$ defined as $\varphi (\pi=\{B_1,\cdots ,B_k\})=(B_i\setminus \{n+1\},\psi (\pi \setminus B_i)),$ where $n+1\in B_i$ and $\psi$ is a function that given a partition on a linear ordered set of size $X$ with $|X|=n$, it gives a partition on $[n].$(respecting the order of the elements in $X$).For example: $\psi(\{ \{1,5\},\{10,3,6\}\})=\{\{1,3\},\{2,4,5\}\}$ because $1<3<5<6<10.$

In other words, you are consider the block in which $n+1$ is in the partition $\pi$ and taking it away to get a partition on $[n+1]\setminus B_i$ but remembering which elements where in the block that contained $n+1.$ Notice that this information let us show that this is indeed a bijection. Why?