# Number of Optional Pairings?

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?

-
Before you give up, you might try writing out that product.... –  Hurkyl Jun 24 '12 at 1:14

## 1 Answer

This is Number of self-inverse permutations on n letters, also known as involutions; number of Young tableaux with n cells at the Online Encyclopedia of Integer Sequences, where you will find many alternative interpretations, references to the literature, links to websites, and formulas for this sequence, which has been the object of much study.

I'm assuming the $n$ items are distinguishable.

-
What do you mean distinguishable in this context? The elements of the set are pairwise distinct. –  Andrew Tomazos Jun 26 '12 at 5:23
I guess then that I mean the same thing you mean. The partition of $\{{a,b,c\}}$ into $\{{a\}}$ and $\{{b,c\}}$ differs from the partition into $\{{b\}}$ and $\{{a,c\}}$. But if you follow the links the meaning should become evident. –  Gerry Myerson Jun 26 '12 at 6:19