Um baralho de n cartas numeradas de 1 a n é embaralhado da seguinte maneira: em cada etapa, escolhemos aleatoriamente uma das cartas e a movemos para a frente do baralho, deixando inalteradas as posições relativas das demais cartas. Esse procedimento continua até que todas exceto uma carta tenham sido escolhidas. Neste momento, resulta por simetria que todas as n! possíveis sequências de cartas são igualmente prováveis. Determine o número esperado de etapas necessárias.

Passo 1

Fala galeraaa!

Vamos que vamos!

Este é um problema típico de coletor de cupons. Considere esta ideia: pense que cada carta representa um tipo de cupom e escolher uma carta aleatoriamente do baralho é na verdade obter um novo cupom onde todos os tipos são igualmente prováveis. É-nos dado que paramos com o processo até embaralharmos todas menos uma carta, ou seja, obtemos todos menos um tipo de cupom $-n-1$ tipos de cupom. Assim, temos que o número esperado de passos para obter $n-1$ cartões distintos é igual a:

E X = 1 + n n - 1 + n n - 2 + ⋯ + n 2

Resposta

Conecte este problema ao problema do coletor de cupons!

.