Let $f(n)$ be the number of all partitions of $[n]$ with no single blocks. Prove that $B(n) = f(n) + f(n+1)$. Where $B(n)$ is the Bell number. Can anyone help me start a bijection?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Hint: If $\sim$ is an equivalence relationship on $[n+1]$ with no singleton blocks, how can you find a partition on $[n]$ which must have singleton blocks?
You basically want to find a bijection showing $f(n+1)=B(n)-f(n)$, where $B(n)-f(n)$ is represented by the obvious set of partitions that do have at least one singleton block.