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?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
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. |
|||||||
|

