ILL 1985 Problem 32

A collection of $2n$ letters contains $2$ each of $n$ different letters. The collection is partitioned into $n$ pairs, each pair containing $2$ letters, which may be the same or different. Denote the number of distinct partitions by $u_n$ . (Partitions differing in the order of the pairs in the partition or in the order of the two letters in the pairs are not considered distinct.) Prove that $u_{n+1}=(n+1)u_n - \frac{n(n-1)}{2} u_{n-2}.$ Similar Problem :

A pack of $2n$ cards contains $n$ pairs of $2$ identical cards. It is shuffled and $2$ cards are dealt to each of $n$ different players. Let $p_n$ be the probability that every one of the $n$ players is dealt two identical cards. Prove that $\frac{1}{p_{n+1}}=\frac{n+1}{p_n} + \frac{n(n-1)}{2p_{n-2}}.$