Q32 Matemática  (IMO Longlists 1985)

Uma coleção de $2n$ letras contém $2$ cada uma de $n$ letras diferentes. A coleção é particionada em $n$ pares, cada par contendo $2$ letras, que podem ser iguais ou diferentes. Denote o número de partições distintas por $u_n$. (Partições que diferem na ordem dos pares na partição ou na ordem das duas letras nos pares não são consideradas distintas.) Prove que $u_{n+1}=(n+1)u_n-\frac{n(n-1)}{2}{u}_{n-2}.$ Problema Semelhante: Um baralho de $2n$ cartas contém $n$ pares de $2$ cartas idênticas. Ele é embaralhado e cartas de $2$ são distribuídas para cada um dos $n$ jogadores diferentes. Seja $p_n$ a probabilidade de que cada um dos jogadores $n$ receba duas cartas idênticas. Prove que $\frac{1}{p_{n+1}}=\frac{n+1}{p_n}+\frac{n(n-1)}{2p_{n-2}}.$