I am having some trouble solving the following problem:
Let $A_n$ be the set of set partitions of $\{1, . . . , n\}$ without any singleton blocks. Show that $$\left| A_n \right| = \sum_{k=0}^{n} (-1)^k \binom{n}{k} B(n - k)$$ where $B(n)$ is the nth Bell number.
Here we cannot use generating functions and our professor told us to apply the principle of inclusion-exclusion. So, I let $A_S$ to be the collection of set partitions of $\{1, . . . , n\}$ where each element of $S$ is in a singleton block and start working from there but I end up with $$\left| A_{=S} \right| = \sum_{k=0}^{n-|s|} (-1)^k \binom{n-|s|}{k} B(n -|s|- k)$$ Can someone help me with this?
Your displayed formula is clearly wrong, since for $n=4$ the righthand side is $-11$.
The inclusion-exclusion principle says that
$$\begin{align*} \left|\bigcup_{k=1}^nA_{\{k\}}\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{k\in I}A_{\{k\}}\right|\\ &=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}|A_I|\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{n}kB(n-k)\,, \end{align*}$$
since there are $\binom{n}k$ subsets $S$ of $[n]$ of cardinality $k$ and $B(n-k)$ partitions of $[n]\setminus S$. This is the number of ‘bad’ partitions of $[n]$, i.e., of partitions that have at least one singleton block. There are altogether $B(n)$ partitions of $[n]$, so
$$\begin{align*} |A_n|&=B(n)-\sum_{k=1}^n(-1)^{k+1}\binom{n}kB(n-k)\\ &=\sum_{k=0}^n(-1)^k\binom{n}kB(n-k)\,. \end{align*}$$