Importante: Para os próximos exercícios defina claramente o espaço de probabilidade!

13 - Problema do Pareamento

No final de um dia agitado, os pais chegam ao jardim de infância para pegar seus filhos. Cada pai escolhe uma criança para levar a casa uniformemente ao acaso. Use o fórmula de inclusão-exclusão para mostrar que a probabilidade de pelo menos um pai escolhe seu próprio filho é igual a
1-12!+13! cdots+(-1)^n-1 1n!
E que essa probabilidade converge a 1-1 /e quando n infty

Passo 1

O enunciado pede a probabilidade de que pelo menos um pai escolha o próprio filho num sorteio aleatório sem reposição entre n pais e n filhos. O conteúdo principal é o Princípio da Inclusão-Exclusão aplicado a permutações, e vamos precisar definir o espaço de probabilidade (todas as permutações de n elementos igualmente prováveis) e os eventos de interesse (cada pai acertar o próprio filho).

Passo 2

Definimos o espaço de probabilidade como Omega=Sn, o conjunto de todas as permutações de 1,2,dots,n. Cada permutação tem probabilidade uniforme P(omega)=1/n!. Para cada i=1,dots,n, definimos o evento Ai como "o pai i escolhe o filho i".

Passo 3

Para aplicar a inclusão-exclusão, precisamos de P(Ai1cap Ai2capcdotscap Aik). Se k pais fixam seus filhos, restam n-k pais para permutar livremente, logo há (n-k)! permutações favoráveis. Assim
P(Ai1capcdotscap Aik)=(n-k)!n!

Passo 4

Pela fórmula de inclusão-exclusão, a probabilidade de pelo menos um acerto é
Pl(cupi=1^nAir)=sumk=1^n(-1)^k-1sum1<= i1

Passo 5

Como há binomnk escolhas de k índices e cada interseção tem probabilidade (n-k)!/n!, obtemos
Pl(cupiAir)=sumk=1^n(-1)^k-1binomnk(n-k)!n! = sumk=1^n(-1)^k-11k!

Passo 6

Para ver o limite quando ntoinfty, lembramos que
e=sumk=0^infty1k!=1+sumk=1^infty1k!,

Passo 7

logo
sumk=1^infty(-1)^k-11k!=1-1e

Resposta

A probabilidade é
1-12!+13!-cdots+(-1)^n-11n!
e, quando ntoinfty, converge para
1-1e

Exercícios relacionados