Re: Questão

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Thu, 22 Jun 2000, Ecass Dodebel wrote:

> >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.
> 
> 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])

Na verdade, eu achei o problema muito legal, pensei nele e cheguei
ao mesmo resultado. Não cheguei a escrever para a lista por pregiça
de escrever a demonstração (que você também não escreveu).

Minha única observação é que eu prefiro indexar Fibonacci por
a_0 = 0, a_1 = 1, a_2 = 1, a_3 = 2, a_4 = 3,...
Com isso temos as seguintes propriedades, que o leitor incansável
poderá tentar demonstrar:

a_{-n} = (-1)^(n+1) a_n
m | n => a_m | a_n (onde m | n significa m é divisor de n)
a_(mdc(m,n)) = mdc(a_m,a_n)
a_(2n) = a_n(a_(n+1) + a_(n-1))
a_(2n+1) = a_n^2 + a_(n+1)^2

e, se 

    [0   1]
A = [     ]
    [1   1]

então

       [a_(n-1)  a_n    ]
A^n =  [                ]
       [a_n      a_(n+1)]

A sua indexação de Fib, entretanto, também é usada por muita gente.
O Morgado e eu uma vez discordamos sobre qual a indexação mais usual
e fizemos uma rápida pesquisa de verificar em vários livros;
deu aproximadamente empate.



[]s, N.