$F(n)$ is number of ways to partition set of $n$ without singleton blocks. Prove that $B(n) = F(n) + F(n+1)$ In this case $B(n)$ is $n$-th Bell number.
To be honest, I would really love to know if there is a combinatorial proof for that. If there is not, other proofs are appreciated too.
 A: Clearly that amounts to showing that there are $F(n+1)$ partitions of $[n]$ that do have at least one singleton block. Suppose that $\pi$ is a partition of $[n]$ with at least one singleton block; then we can take all the singletons, combine them into a single block, and put $n+1$ in that block to get a partition of $[n+1]$ with no singletons. Conversely, given a partition of $[n+1]$ with no singletons, we can take the block that contains $n+1$, throw away the $n+1$, and break the rest of the block (which is non-empty) into singletons to get a partition of $[n]$ with at least one singleton.
A: The combinatorial class for ordinary set partitions is
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SET}(\textsc{SET}_{\ge 1}(\mathcal{Z}))$$
and for set partitions with no singletons it is
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SET}(\textsc{SET}_{\ge 2}(\mathcal{Z})).$$
This gives the exponential generating functions
$$B(z) = \exp(\exp(z)-1)$$
and
$$B_{\ge 2}(z) = \exp(\exp(z)-z-1).$$
Now observe that
$$n! [z^n] B_{\ge 2}(z) + (n+1)! [z^{n+1}] B_{\ge 2}(z)
\\ = n! [z^n] B_{\ge 2}(z) + n! [z^n] B_{\ge 2}(z)'
\\ = n! [z^n] \exp(\exp(z)-z-1)
+ n! [z^n] \exp(\exp(z)-z-1) (\exp(z)-1)
\\ = n! [z^n] \exp(\exp(z)-z-1) \exp(z)
\\ = n! [z^n] \exp(\exp(z)-1)
= n! [z^n] B(z).$$
This is the claim.
