Questão 28: Forma-se ao acaso uma permutação simples dos números
. Caso o número
ocupe o
-ésimo lugar, dizemos que há um encontro na posição
. Calcule a probabilidade que na permutação formada hajam exatamente
encontros.
Passo 1
O enunciado pede a probabilidade de não aparecer nenhum encontro (ou ponto fixo) numa permutação aleatória de
. Esse problema leva ao conceito de desarranjos (ou derangements) e vamos usar o princípio da inclusão-exclusão para contar quantas permutações não fixam nenhum elemento.
Passo 2
Seja
o conjunto de permutações em que o número
fica na posição
. O número total de permutações é
. Pelo princípio da inclusão-exclusão, o número de permutações que não têm nenhum ponto fixo (ou seja, que não pertencem a nenhum dos
) é
Passo 3
Fatorando
em cada termo obtemos a fórmula clássica dos desarranjos:
Passo 4
Como cada permutação é igualmente provável, a probabilidade de exatamente
encontros é
Para
grande essa soma se aproxima de
, mas a expressão acima vale para qualquer
.