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