How many combinations with $n$ numbers to form groups of at most $2$? Let $n$ be a positive integer. I would like to generate the combinations from $n$ of size at most $2$. For example, if $n=3$, then the combinations are:
$$
\{1\}, \{2\}, \{3\}\\
\{1\}, \{2,3\}\\
\{2\}, \{1,3\}\\
\{3\}, \{1,2\}\\
$$
So I have $9$ combinations.
If $n=4$, the combinations are:
$$
\{1\}, \{2\}, \{3\}, \{4\}\\
\{1,2\}, \{3,4\}\\
\{1,3\}, \{2,4\}\\
\{1,4\}, \{2,3\}\\
\{1\}, \{2\}, \{3,4\}\\
\{1\}, \{3\}, \{2,4\}\\
\{1\}, \{4\}, \{2,3\}\\
\{2\}, \{3\}, \{1,4\}\\
\{2\}, \{4\}, \{1,3\}\\
\{3\}, \{4\}, \{1,2\}\\
$$
So I have $28$ combinations.
So, given $S=\{1,2\ldots,n\}$, find the collection of sets $C=\{S_1,S_2,\ldots,S_m\}$ such that: $S_i\cap S_j=\emptyset$ for $i\ne j$ and $\cup_{s\in S_i}s=S$ and for any $s\in S_i$, we have $|s|\leq 2.$
I am looking for $$\sum_{i=1}^m|S_i|.$$
 A: First decide how many pairs you will form, then find the number of ways to choose the pairs.  All the rest will be singletons.  If you have $k$ pairs from $n$ numbers, there are $n \choose 2$ ways to form the first pair, ${n-2 \choose 2}$ ways to form the second, and so on down to ${n-2k+2 \choose 2}$ for the last pair.  We have overcounted by a factor $k!$ because we can choose the pairs in any order.  This means that for $k$ pairs there are 
$$\frac {n!}{2^k(n-2k)!k!}$$  The total number of combinations is then
$$\sum_{k=0}^{\lfloor \frac n2 \rfloor}\frac {n!}{2^k(n-2k)!k!}(n-k)$$
where the final $n-k$ factor is the number of parts for each combination.
A: Let $a_{n,m}$ be the number of ways to partition $\{1,2,\dots,n\}$ into $m$ parts whose sizes are $1$ or $2$. By the exponential formula (see Theorem 3.4.1 in generatingfunctionology, p. 81), we have
$$
\sum_{n=0}^\infty \sum_{m=0}^\infty a_{n,m}\frac{x^n}{n!}y^m=e^{y(x+x^2/2)}
$$
Now, differentiating both sides with respect to $y$, and then setting $y=1$, we get
$$
\sum_{n=0}^\infty \left(\sum_{m=0}^nma_{n,m}\right)\frac{x^n}{n!}=(x+x^2/2)e^{x+x^2/2}
$$
Note that $\sum_{m=0}^n ma_{n,m}$ is exactly the quantity you want. Therefore, this shows that $(x+x^2/2)e^{x+x^2/2}$ is the exponential generating function for your series. In other words, letting $[x^n]f(x)$ denote the coefficient of $x^n$ in the power series $f(x)$, the the number of combinations is
$$
\boxed{\;n!\cdot [x^n](x+x^2/2)e^{x+x^2/2}.\;}
$$
This may not seem like seem like a satisfying answer, but it gives you an effective method to compute the number of combinations for $n$. For example, Wolfram Alpha has no problem saying there are $$789503185108476263077354022270054400$$combinations when $n=50$. You can also use that link to verify my formula gives the correct answers for $n=3$ and $n=4$. 
