Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Before I ask the question, I must admit that combinatorics has never been my forte.

I am given a set X of size $n$, we may assume assume $X=\{1,2,...,n\}$. I want to count the partition of this set into subsets of size either 1 or 2. Let's denote the set of such partitions by $T_{n}$. I can find a recurrence equation for $|T_{n}|$. If I take one such partition, then the element $n$ must be in a subset of either size 2 or 1: let $R_{2}$ be the set of partitions in $T_{n}$ where $n$ is in a subset of size 2, and let $R_{1}$ be the set of partitions in $T_{n}$ where $n$ is in a subset of size 1. Then $R_{1}\cup R_{2}=T_{n}$ and their intersection is empty, so $|R_{1}|+ |R_{2}|=|T_{n}|$. In fact $R_{1}$ is simply $T_{n-1}$ and $R_{2}$ is $(n-1)T_{n-2}$ (as I have $n-1$ choices for the element in the same subset in which $n$ lies and then I can partition the remaining $n-2$ elements in $|T_{n-2}|$ ways). So $|T_{n}|=(n-1)|T_{n-1}|+|T_{n-2}|$.

This recurrence relation seems to work (in a very heuristic way, I have checked it for few $n$'s), but I am not sure it is right. I can construct a bijection between $T_{n}$ and the set $U_{n}$ of elements of the symmetric group $S_{n}$ with cycles types which are a sequence of 2's and 1's.

For example, I tried to calculate $|U_{6}|$ as follows: I have a single choice for the permutation of cycle type $(1,1,1,1,1,1)$, $\frac{6!}{2*5!}$ for the permutation with cycle type $(2,1,1,1,1)$, $\frac{6!}{4*4!}$ for the permutation with cycle type $(2,2,1,1)$, and $\frac{6!}{8*3!}$ for the permutation with cycle type $(2,2,2)$ but this gives me $26.5$.

The questions are:

  • Is my recurrence relation correct?
  • Where is my error in counting the elements of $U_{6}$?

Thank you so much in advance and I hope the questions are clear.

Erratum: I mis-wrote the recurrence relation, it should read $|T_{n}|=(n-1)|T_{n-2}|+|T_{n-1}|$.

share|improve this question
sequence Sloane A000085 –  Hendrik Jan Oct 24 '12 at 12:36
add comment

3 Answers

up vote 3 down vote accepted

Your work looked good at first, but then I think you mis-wrote your formula for $T_n$. In particular, you multiplied the wrong piece by $(n-1)$ at the end of your first full paragraph.

There is nothing "heuristic" about this recurrence relation; you proved it holds!

Basically restating back what you wrote: whatever the answer is for a set of size $n-1$ (let's call this $f_{n-1}$) consider next a set of size $n$. Begin by putting the element $n$ into a subset. If you put it into a subset of size $1$, then there are $n-1$ elements left to partition into subsets of size $1$ or $2$, which we just decided can be done in $f_{n-1}$ ways. On the other hand, if we put $n$ into a subset of size $2$, which can be done in one of $n-1$ different ways (one possible pairing with each of the other $n-1$ elements), then there will be $f_{n-2}$ ways to partition the remaining $n-2$ elements.

This gives: $f_{n} = f_{n-1} + (n-1) f_{n-2}$.

share|improve this answer
Thank you so much, so my proof was right! :) –  dado Oct 24 '12 at 16:05
add comment

The permutations whose cycle lengths are all $1$ or $2$ are precisely the involutions, and the number of involutions on $\{1,\dots,n\}$ is $$\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!\;,\tag{1}$$

where we set $(-1)!!=1$. For $n=6$ this yields the value


The number of permutations of $\{1,\dots,n\}$ having $r$ $2$-cycles and $n-2r$ fixed points is $$\frac{n!}{1^{n-2r}\cdot2^r\cdot(n-2r)!\cdot r!}=\frac{n!}{2^rr!(n-2r)!}\;,$$ so $U_6$ has $1$ permutation of type $(1,1,1,1,1,1)$, $\frac{6!}{2\cdot4!}=15$ of type $(1,1,1,1,2)$, $\frac{6!}{4\cdot2!\cdot 2!}=45$ of type $(1,1,2,2)$, and $\frac{6!}{8\cdot3!\cdot0!}=15$ of type $(2,2,2)$.

Now to the derivation of your recurrence. There are a couple of glitches. First, your ‘$R_1$ is simply $T_{n-1}$ and $R_2$ is $(n-1)T_{n-2}$’ should be ‘$|R_1|$ is simply $|T_{n-1}|$ and $|R_2|$ is $(n-1)|T_{n-2}|$’. It isn’t the sets that are equal, but rather their cardinalities. And secondly, you reversed the coefficients when you wrote $|T_{n}|=(n-1)|T_{n-1}|+|T_{n-2}|$: that should have been $|T_{n}|=|T_{n-1}|+(n-1)|T_{n-2}|$. The basic reasoning is correct, however.

Added: This special case can be handled more directly, but I got formula $(1)$ from a more general result: if $C$ is any set of positive integers, and $g_C(n)$ is the number of permutations of $\{1,\dots,n\}$ whose cycle lengths are all in $C$, then the exponential generating function of the $g_C(n)$ is

$$G_C(x)=\sum_{n\ge 0}g_C(n)\frac{x^n}{n!}=\exp\left(\sum_{n\in C}\frac{x^n}n\right)\;.$$

Take $C=\{1,2\}$, and this becomes

$$G_C(x)=\exp\left(x+\frac{x^2}2\right)=\left(\sum_{k\ge 0}\frac{x^k}{k!}\right)\left(\sum_{i\ge 0}\frac{x^{2i}}{2^ii!}\right)\;.$$

The coefficient of $n$ in the product on the right is $$\sum_{i=0}^{\lfloor n/2\rfloor}\frac1{(n-2i)!2^ii!}=\sum_{i=0}^{\lfloor n/2\rfloor}\left((n-2i)!\cdot\frac{(2i)!}{(2i-1)!!}\right)^{-1}=\sum_{i=0}^{\lfloor n/2\rfloor}\frac1{n!}\binom{n}{2i}(2i-1)!!\;,$$ so $$g_C(n)=\sum_{i=0}^{\lfloor n/2\rfloor}\binom{n}{2i}(2i-1)!!\;.$$

share|improve this answer
Thank you a lot, now I have understood what was wrong with my counting of the permutations. –  dado Oct 24 '12 at 16:06
add comment

Moreover, from $$ f_n = f_{n+1} + (n-1) f_{n-2} $$ it is quite easy to deduce: $$ f_n = \frac{d^n}{dx^n}\left.\exp\left(x+\frac{x^2}{2}\right)\right|_{x=0}. $$ In fact, if we take $f_n = n!\,g_n$ and $$ g(x) = \sum_{n=1}^{+\infty} g_n\, x^n,$$ we have $$ n\,g_n = g_{n-1} + g_{n-2} $$ and so: $$ g'(x) = g(x) + x\, g(x).$$

share|improve this answer
add comment

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.