# Bijective proof for set partitions

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?

-

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.
So, in a way you consider the $n+1$th element as a kind of ideal element and collect all the singletons to join its class. –  Berci Jan 28 '13 at 16:44