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

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)?

• You need to define somehow the Bell numbers if you want a proof. How do you define them? – Berci Sep 13 '20 at 15:31
• Won't the definition by recurrence (using binomial coefficient) do? I would have to find a set whose cardinality would be equal to that expression, right? I cannot find a proof anywhere. Every book says something like "obviously these numbers count partitions etc. etc." It is not obvious to me at all. – guam Sep 13 '20 at 15:39
• So you basically want to prove the recurrence formula (if $B_n$ are defined as that then $\{$partitions of $\{0,1,\dots,n-1\}\}$ has cardinality $B_n$), right? – Berci Sep 13 '20 at 15:43
• Yes: I want to show that the set of partitions of $\{0,1,\ldots,n-1\}$ has cardinality $B_n$. Is it possible? – guam Sep 13 '20 at 15:44

## 1 Answer

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?