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