Let $F(n)$ be the number of all partitions of $[n]$ with no singleton blocks.
-
Find the recursive formula for the numbers $F(n)$ in terms of the numbers $F(i)$, with $i ≤ n − 1$
-
Find a formula for $F(n)$ in terms of the Bell Numbers $B(n)$.
For the first question, it's obviously something like $F(n+1) = \sum_{i=0}^n {n \choose i} F(i)$, since that's what it is for Bell numbers, but I really can't see how I'd get to the correct formula.
For the second one, I believe I'm supposed to use inclusion-exclusion, but I'm a bit lost.
Best Answer
Say that a partition of $[n]$ is good if it has no singleton blocks and bad otherwise. $B_n$, the $n$-th Bell number, is the total number of partitions of $[n]$. If $b(n)$ is the number of bad partitions of $[n]$, $F(n)=B_n-b(n)$. As usual, a little data can’t hurt. By direct enumeration of $F(n)$ and $b(n)$ and a table of the Bell numbers I find
$$\begin{array}{cccc} n&F(n)&b(n)&B_n\\ \hline 0&0&1&1\\ 1&0&1&1\\ 2&1&1&2\\ 3&1&4&5\\ 4&4&11&15\\ 5&11&41&52\\ 6&41&162&203 \end{array}$$
This very strongly suggests that $F(n+1)=b(n)$ for $n\ge 1$. To see why this is true, suppose first that $\pi$ is a bad partition of $[n]$; then we can form a good partition of $[n+1]$ by gathering all of the singletons of $\pi$ into a single block and putting $n+1$ into that block. Conversely, if $\pi$ is a good partition of $[n+1]$, we can form a bad partition of $[n]$ by taking the block of $\pi$ containing $n+1$, throwing away $n+1$, and converting the rest of the block to singletons. These operations are clearly inverses of each other and thus establish a bijection between bad partitions of $[n]$ and good partitions of $[n+1]$.
This immediately gives us the recurrence $F(n+1)=B_n-F(n)$. Unwrapping the recurrence, we find that:
$$\begin{align*} F(n+1)&=B_n-F(n)\\ &=B_n-\big(B_{n-1}-F(n-1)\big)\\ &=B_n-B_{n-1}+F(n-1)\\ &=B_n-B_{n-1}+\big(B_{n-2}-F(n-2)\big)\\ &=B_n-B_{n-1}+B_{n-2}-F(n-2)\\ &\;\vdots\\ &=\sum_{i=0}^k(-1)^iB_{n-i}+(-1)^{k+1}F(n-k)\\ &\;\vdots\\ &=\sum_{i=0}^{n-1}(-1)^iB_{n-i}\;. \end{align*}$$
Added: For the first question, let $\pi$ be a good partition of $[n+1]$, and let $B$ be the block containing $n+1$. There is at least one element of $[n]$ in that block, so $[n]\setminus B$ is a proper subset of $[n]$. If $|[n]\setminus B|=k$, $\pi\setminus\{B\}$ can be any one of the $F(k)$ good partitions of $[n]\setminus B$. Conversely, all good partitions of $[n+1]$ can be obtained by choosing a proper subset $S$ of $[n]$, forming a good partition of $S$, and adding to it the block $\{n+1\}\cup([n]\setminus S)$. Since $[n]$ has $\binom{n}k$ subsets of cardinality $k$, $[n+1]$ has $\binom{n}kF(k)$ good partitions in which the block containing $n+1$ has $n-k$ other elements, and it follows that $$F(n+1)=\sum_{k=0}^{n-1}\binom{n}kF(k).$$