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)?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ You need to define somehow the Bell numbers if you want a proof. How do you define them? $\endgroup$– BerciCommented Sep 13, 2020 at 15:31
-
$\begingroup$ 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. $\endgroup$– user821980Commented Sep 13, 2020 at 15:39
-
$\begingroup$ 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? $\endgroup$– BerciCommented Sep 13, 2020 at 15:43
-
$\begingroup$ Yes: I want to show that the set of partitions of $\{0,1,\ldots,n-1\}$ has cardinality $B_n$. Is it possible? $\endgroup$– user821980Commented Sep 13, 2020 at 15:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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?
