Combination of pairing elements or keeping them single 
Given a number $n$, find the number of ways to keep the $n$ elements single or pair them up.

The elements in any arrangement may or may not be paired.
If $n=3$, then the number of ways would be $4$ namely $:$ $(1, 23), (12, 3), (13, 2), (1, 2, 3)$.
If $n = 4$ then the $10$ possible arrangements would be $(1, 2, 3, 4), (12, 3, 4), (12, 34), (13, 2, 4)  etc..$
I'm aware that this problem is related to the formula $\frac{(2k)!}{2^{k}k!}$ where $k$ is the number of pairs. However that formula is strictly only for pairs. I'm also trying to implement this in a simple program. Can I get an explanation on how solve this. I also want to know how to treat odd numbers.
I've tried using a simple summation but I'm unable to resolve overcounting at each stage
I'm sorry if that sounded confusing. I dont know of any other way to represent pairs
Thanks!
 A: $\frac{(2n)!}{2^nn!}$ only counts the number of perfect matchings of the complete graph $K_{2n}$. You are looking for the number of matchings, incomplete ones included, in the complete graph $K_n$, i.e. the Hosoya index. This is a far different beast, and in fact there is no easy closed form for these numbers, although there is a simple recurrence relation.
The number of matchings in $K_n$ is given by the telephone numbers:
$$a(0)=a(1)=0,a(n)=a(n-1)+(n-1)a(n-2)$$
A: You say that a summmation is an acceptable answer, and there is a nice summation for these numbers:
$$
\text{# ways to pair up some of $n$ elements}=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}\frac{(2k)!}{2^kk!}
$$The index $k$ represents the number of pairs, the $\binom{n}{2k}$ is the number of ways to choose the people to be put in pairs, and $\frac{(2k)!}{2^kk!}$ is the number of ways to pair all of the chosen people.
Perhaps this generalization is of interest: the number of ways to divide some of the people into groups of size $m$, and leave the others in singletons, is
$$
\sum_{k=0}^{\lfloor n/m\rfloor}\binom{n}{mk}\frac{(mk)!}{m^kk!}
$$
