Olá Claudio, achei esse problema bem interessante* . Vamos esperar pelas elocubrações do pessoal .
Ah, achei ótimo tomar conhecimento do link que vc enviou ! Obrigado !
Abraços, Rogério.
"bem interessante" = "já me gastou horas de banho pensando a respeito"
---------------------------
From: Claudio Buffara <[EMAIL PROTECTED]> > 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.
_________________________________________________________________ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com
========================================================================= 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 =========================================================================
