So I need to calculate the number of ways you can partition a set of $n$ items such that the size of each partition is either 1 or 2.
Let $m = \lfloor \frac{n}{2}\rfloor$
$m$ is the maximum number of pairs (2-partitions).
Then the answer is:
$\sum_{i=0}^m{{\prod_{j=0}^{i-1}{n-2j \choose 2}} \over i!}$
i is the number of pairs to use, and then j is choosing the jth pair from the remaining items, with i! factoring out the irrelevant order selection.
I don't know how to simplify from here, or have I taken a bad turn? Is there a simpler way to approach this problem?
${{\prod_{j=0}^{i-1}{n-2j \choose 2}} \over i!}$ $ = {n \choose 2}{n-2 \choose 2}\dots{n-2i-2 \choose 2}$ $ = {n! \over 2!(n-2)!}{(n-2)! \over 2!(n-4)!}\dots{(n-2i-2)! \over 2!(n-2i-4)!}$ $ = {n! \over 2^i(n-2i-4)!} $
Is that right? And now expanding the sum?