MathDB

32

Part of 1985 IMO Longlists

Problems(1)

Partitioning a deck with 2 cards in n types into pairs

Source:

9/13/2010
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}}.
probabilitycombinatorics proposedcombinatorics