1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ You need to define somehow the Bell numbers if you want a proof. How do you define them? $\endgroup$ – Berci Sep 13 '20 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$ – guam Sep 13 '20 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$ – Berci Sep 13 '20 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$ – guam Sep 13 '20 at 15:44
1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.