Re: [obm-l] Probabilidade - Dígitos aleatórios

[kleinad@xxxxxxxxxx]

Há alguns meses apareceu na lista um problema equivalente. Em uma urna com n
bilhetes numerados sorteia-se um de cada vez retirando-o da urna. Quando
ocorre de, na k-ésima rodada, tirarmos exatamente o número k, dizemos que
ocorreu um "match". Encontre a probabilidade de ocorrer pelo menos um match.

Outra formulação equivalente: encontrar quantas das permutações das linhas
da matriz identidade n x n preservam elementos 1 na diagonal principal.

A solução era C(n) = 1 - 1/2! + 1/3! - 1/4! + ... + (-1)^(n+1)/n!. No limite
quando n -> oo, isso tende para 1 - e^(-1).

Eu cheguei a fazer esse desenvolvimento por conta própria na época (depois
de vários equívocos, como sempre), mas ficou extremamente extenso, usando
diversas induções... Considerei basicamente seqüências P(i), que
correspondiam ao número de permutações da matriz identidade que mantinham a
i-ésima linha inalterada e que não repetiam permutações já consideradas
anteriormente; era assim:

P(1) = (n-1)!
P(2) = (n-1)! - (n-2)!
P(3) = (n-1)! - 2*(n-2)! + (n-3)!
...
P(k) = Somatório(i=0,k-1) (k-1)!/(i!*(k-i)!)*(-1)^i*(n-1-i)!

Somam-se os P(k) e dividi-se tudo por n! para obter a expressão C(n).

[]s,
Daniel

David M. Cardoso (david-obm@suati.com.br) escreveu:
>
>
>Tentei, tentei, tentei um pouco mais e não consegui encontrar uma solução:
>
>Suponha que os n dígitos 1,2,3,...,n sejam escritos em ordem aleatória. Qual
>é a probabilidade de que ao menos um dígito ocupe seu lugar próprio?
>
>Alguém ajuda?
>
>Abraço,
>David
>
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>=========================================================================
>

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================