Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Before you give up, you might try writing out that product.... – Hurkyl Jun 24 '12 at 1:14

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.