Generating function for the number of partitions of [n] without singletons.

Question

I know the generating function for the total number of partitions of [n] is given by $$ B(x)=e^{e^x-1}$$ I am struggling to find $V(X)$, the exponential generating function for the number of partitions containing no singleton blocks. I have read the answer is $V(x)=e^{e^x-x-1}$ but not sure how this is obtained.

Answer 1

We consider $[n]=\{1,2,\ldots,n\}$ as combinatorial class $\mathrm{SET}_{n}(\mathcal{X})$ of $n$ labelled objects. In terms of exponential generating function (EGF) this is represented as \begin{align*} \mathrm{SET}_{n}(\mathcal{X})\qquad\Longrightarrow\qquad\frac{x^n}{n!} \end{align*} Allowing $n\geq 1$ gives a disjoint union of sets of objects and a series representation as EGF. \begin{align*} \mathrm{SET}_{n\geq 1}(\mathcal{X})=\bigcup_{n\geq 1}\mathrm{SET}_{n}(\mathcal{X})\qquad\Longrightarrow\qquad\sum_{n=1}^\infty\frac{x^n}{n!}=e^{x}-1 \end{align*} We want to exclude singletons, so $n\geq 2$ \begin{align*} \mathrm{SET}_{n\geq 2}(\mathcal{X})=\bigcup_{n\geq 2}\mathrm{SET}_{n}(\mathcal{X})\qquad\Longrightarrow\qquad\sum_{n=2}^\infty\frac{x^n}{n!}=e^{x}-1-x\tag{1} \end{align*}

We can use sets as building blocks in order to obtain more complex structures. A set of $n$ objects of a combinatorial class $\mathcal{B}$ and disjoint unions of them are then given as \begin{align*} \mathrm{SET}_{n}(\mathcal{B})\qquad&\Longrightarrow\qquad\frac{\left(B(x)\right)^n}{n!}\\ \mathrm{SET}_{n\geq 0}(\mathcal{B})=\bigcup_{n\geq 0}\mathrm{SET}_{n}(\mathcal{B})\qquad&\Longrightarrow\qquad\sum_{n=0}^\infty\frac{\left(B(x)\right)^n}{n!}=e^{B(x)}\tag{2} \end{align*} In (1) we also allow a neutral object $\epsilon$ with size $0$ and having no labels at all, represented as $1$ in terms of EGF.

We are now prepared for the current problem:

The number of set-partitions of $[n]$ which do not contain singletons, is a set of sets each having at least two elements. Taking also the empty set-partition into account we consider according to (1) and (2) the combinatorial class \begin{align*} \color{blue}{\mathrm{SET}_{n\geq 0}\left(\mathrm{SET}_{n\geq 2}(\mathcal{X})\right) \qquad\Longrightarrow}\qquad\sum_{n=0}^\infty\frac{\left(e^x-1-x\right)^n}{n!}\color{blue}{=e^{e^x-1-x}} \end{align*}

Hint: A great presentation of this approach is given in section II.1 and II.2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.