Bell number in terms of variant without singletons

Question

$B_m$ is the Bell's number (the # of all partitions of the set $m$) and $B_m^*$ is the number of partitions of set $m$ with no singleton block

How to prove that $B_m = B_m^* + B_{m+1}^*$?

Answer 1

HINT: Clearly $B_m=B_m^*+B_{m+1}^*$ if and only if $[m]$ has exactly $B_{m+1}^*$ partitions with at least one singleton block. Thus, we’d like to find a bijection between partitions of $[m]$ with at least one singleton block and partitions of $[m+1]$ with no singleton block. If $\pi$ is a partition of $[m]$ with at least one singleton block, combine the singletons of $\pi$ into a single set, and put $m+1$ into that set as well; the result is a partition of $[m+1]$ with no singleton block. Check that the procedure is reversible.