3
$\begingroup$

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?

  • 1
    Before you give up, you might try writing out that product....2012-06-24

1 Answers 1

2

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.

  • 0
    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.2012-06-26