on 26.11.03 14:32, Rogerio Ponce at [EMAIL PROTECTED] 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 =========================================================================