Partition of a set of size n into subsets of size 1 and 2.

Question

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}|$.

Answer 1

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}$.

Answer 2

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

$$\sum_{k=0}^3\binom6{2k}(2k-1)!!=1\cdot1+15\cdot1+15\cdot3\cdot1+1\cdot5\cdot3\cdot1=76\;.$$

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)!!\;.$$

Answer 3

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).$$