Re: [obm-l] Probabilidade em amigo oculto

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 26.11.03 14:32, Rogerio Ponce at rogerio_ponce@hotmail.com wrote:

> Olá pessoal,
> 
> Num sorteio válido*  de "amigos ocultos" , com N pessoas, qual a
> probabilidade de haver pelo menos uma troca mútua* de presentes ?
> 
> E qual o valor quando N cresce ?
> 
> ---------------
> sorteio válido :  é um sorteio em que ninguém sorteia a si mesmo
> troca mútua  :  X sorteia Y , e Y sorteia X .
> 
Oi, Rogerio:

Os casos possiveis sao as permutacoes caoticas de A = {1,2,...,N}.
O numero delas eh D(N) = N!*(1/2! - 1/3! + 1/4! - ... + (-1)^N/N!).

Os casos favoraveis sao as permutacoes caoticas sem ciclos de ordem 2 de A.
Seja F(N) o numero delas.

Eu calculei F(N) para N pequeno:
F(1) = 0

F(2) = 0

F(3) = 2    
(a,b,c)

F(4) = 6    
(a,b,c,d)

F(5) = 24   
(a,b,c,d,e)

F(6) = Binom(6,3)*2!*2!/2! + 5! = 160
(a,b,c)(d,e,f)  ou  (a,b,c,d,e,f)

F(7) = Binom(7,4)*3!*2! + 6! = 1140
(a,b,c,d)(e,f,g)  ou  (a,b,c,d,e,f,g)

e achei que F(N) eh a sequencia no. A038205 da Encyclopedia of Integer
Sequences: http://www.research.att.com/~njas/sequences/

Infelizmente, nao consegui ver nenhum argumento combinatorio obvio pra
justificar a relacao de recorrencia lah contida. Eu agradeceria se voce me
mostrasse um.

Quando N -> infinito, F(N)/D(N) parece convergir pra 1/raiz(e).


Um abraco,
Claudio.


=========================================================================
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
=========================================================================