MathDB
Partitioning a deck with 2 cards in n types into pairs

Source:

September 13, 2010
probabilitycombinatorics proposedcombinatorics

Problem Statement

A collection of 2n2n letters contains 22 each of nn different letters. The collection is partitioned into nn pairs, each pair containing 22 letters, which may be the same or different. Denote the number of distinct partitions by unu_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 un+1=(n+1)un−n(n−1)2un−2.u_{n+1}=(n+1)u_n - \frac{n(n-1)}{2} u_{n-2}.
Similar Problem :
A pack of 2n2n cards contains nn pairs of 22 identical cards. It is shuffled and 22 cards are dealt to each of nn different players. Let pnp_n be the probability that every one of the nn players is dealt two identical cards. Prove that 1pn+1=n+1pn+n(n−1)2pn−2.\frac{1}{p_{n+1}}=\frac{n+1}{p_n} + \frac{n(n-1)}{2p_{n-2}}.
Back to ProblemsView on AoPS