Re: Quest�o

["Ecass Dodebel" <ecassdodebel@xxxxxxxxxxx>]

>From: "Ecass Dodebel" <ecassdodebel@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Quest�o
>Date: Tue, 20 Jun 2000 18:40:35 GMT
>
>
>Ol�, novamente!
>
>Queria propor este problema para a lista.
>
>Seja F[n] o conjunto de todas as bije��es f de {1,...,n} em {1,...,n} 
>satisfazendo:
>i. f(k) <= k+1 para k=1,2,...,n
>ii. f(k) <> k para k=2,...,n
>Determine a probabilidade de que f(1)<>1 para um f arbitr�rio em F[n]
>
>
>Valeu!
>
>Eduardo Casagrande Stabel.
>
>obs. <= menor ou igual ; <> diferente
>________________________________________________________________________
>Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>

J� que ningu�m respondeu � minha mensagem, respondo eu. Eu achei a resposta 
para essa quest�o em termos dos n�meros de Fibonacci. Ser� que eu fiz de 
modo certo? E eles aceitam a resposta nesses termos?

Eu tentei achar o n�mero de fun��es de F[n] e chamei I[n] o conjunto das 
fun��es em F[n] onde f(1)=1. Da� tentei calcular

1 - #I[n]/#F[n]

Para #F[n] encontrei o n-�simo n�mero de Fibonacci, e para #I[n] encontrei o 
(n-2)-�simo n�mero de Fibonacci ( considerei o -2 e o -1 �simos n�meros de 
Fibonacci como 1 e 0, isso segundo a recurs�o ).

Obrigado aos que leram!

obs. os n�meros de Fibonacci s�o {1,1,2,3,5,8,13,21,...} onde cada termo � a 
soma dos dois imediatamente anteriores. Existe uma express�o para o n-�simo 
n�mero de Fibonnaci, � a seguinte:
Sejam x1 e x2 a maior e menor ra�zes x de x^2 = x + 1, ent�o o n-�simo 
n�mero de Fibonacci � dado por:

([x1]^n - [x2]^n)/([x1] - [x2])


________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com