Partitions and Bell numbers 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. 
 A: 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).$$
A: It is somewhat surprising that there was no answer in terms of generating function as these are quite straightforward. The combinatorial class of set partitions is given by
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(\textsc{SET}_{\ge 1}(\mathcal{Z}))$$
and hence it has the exponential generating function
$$G(z) = \exp(\exp(z)-1).$$
The combinatorial class of set partitions excluding singletons is
$$\textsc{SET}(\textsc{SET}_{\ge 2}(\mathcal{Z}))$$
and hence it has the exponential generating function
$$H(z) = \exp(\exp(z)-1-z).$$
To answer the first question differentiate $H(z)$ to get
$$H'(z) = H(z) \times (\exp(z)-1).$$
Here is a useful observation which I have included in several of my posts.
When we  multiply two exponential generating functions of
the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!}
\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0}
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0}
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the  product of  the two generating  functions is  the generating
function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
Therefore when we extract coefficients from the differentiated equation for $H(z)$ we get
$$F(n+1) =  \sum_{k=0}^{n-1} {n\choose k} F(k) \times 1 =
\sum_{k=0}^{n-1} {n\choose k} F(k).$$
The upper limit is $n-1$ and not $n$ because $\exp(z)-1$ has no constant term.
This is valid for $n\ge 1.$ The base cases are $F(0)=1$ and $F(1)=0.$
For the second part of the question rewrite the equation for $H(z)$ like this:
$$H(z) = \exp(\exp(z)-1)\exp(-z).$$
Using the convolution of exponential generating functions one more time and recognising $G(z)$ from above we obtain that
$$F(n) = \sum_{k=0}^n {n\choose k} B_k (-1)^{n-k} =
(-1)^n \sum_{k=0}^n {n\choose k} (-1)^k B_k.$$
Here is some Maple code to explore these numbers.


with(combinat, bell);
with(combinat, setpartition);

nsb :=
proc(n)
option remember;
local p, admit, s, res, k;

    res := 0;
    for p in setpartition([seq(k, k=1..n)]) do
        admit := true;

        for s in p do
            if nops(s) = 1 then
                admit := false;
                break;
            fi;
        od;

        if admit then res := res+1; fi;
    od;

    res;
end;

F :=
proc(n)
    option remember;

    if n=0 then return 1 fi;
    if n=1 then return 0 fi;

    add(binomial(n-1, k)*F(k), k=0..n-2);
end;

q := n -> (-1)^n*add(binomial(n, k)*(-1)^k*bell(k), k=0..n);

