Questão 28: Forma-se ao acaso uma permutação simples dos números 1,2, ldots, n. Caso o número i ocupe o i-ésimo lugar, dizemos que há um encontro na posição i. Calcule a probabilidade que na permutação formada hajam exatamente k=0 encontros.

Passo 1

O enunciado pede a probabilidade de não aparecer nenhum encontro (ou ponto fixo) numa permutação aleatória de 1,2,dots,n. 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 Ai o conjunto de permutações em que o número i fica na posição i. O número total de permutações é n!. 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 Ai) é
Dn ;=; n! ;-;binomn1(n-1)!;+;binomn2(n-2)!;-;binomn3(n-3)!;+;cdots+(-1)^nbinomnn(n-n)!

Passo 3

Fatorando n! em cada termo obtemos a fórmula clássica dos desarranjos:
Dn ;=; n!,sumi=0^n(-1)^ii!

Passo 4

Como cada permutação é igualmente provável, a probabilidade de exatamente k=0 encontros é
P(k=0);=;Dnn! ;=;sumi=0^n(-1)^ii!
Para n grande essa soma se aproxima de tfrac1e, mas a expressão acima vale para qualquer n.

Resposta

P(k=0)=sumi=0^n(-1)^ii!

Exercícios relacionados