Re: [obm-l] O JOGO DE RENCONTRE!

[kleinad@xxxxxxxxxx]

É verdade Fabio, hj pela manha conclui que o raciocinio era falho quando eu
fazia permutações... A formula so funciona ate n=4.

Minha ultima ideia foi considerar as linhas L_1, L_2, ..., L_n da matriz
identidade I_nxn. Assim, para L_k.k (que significa a k-ésima linha da matriz
identidade na k-ésima linha da matriz permutada), as permutações seriam:

L_1.1 = (n - 1)!
L_2.2 = L_2.2 - L_2.2_1.1 >> para elimanar repetições com L 1.1<< = (n -1)! -
 (n - 2)!
L_3.3 = L_3.3 - L_3.3_1.1 - L_3.3_2.2 + L_3.3_2.2_1.1 = (n-1)! - 2(n - 2)! +
(n - 3)!
....
Pensando assim, IMAGINO que o termo geral seria
L_k.k = Somatório de { (n - 1 - i)!*C(k - 1, i)*(-1)^i }, i variando de 0 a
(k - 1)

Donde a solução para o problema seria o somatório de L_j.j, j variando de 1
a n, dividido por n!. E isso se torna mais parecido mais com o que o Claudio
falou, o que me deixa contente :)


Fábio Dias Moreira (fabio@dias.moreira.nom.br) escreveu:
>
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>kleinad@webcpd.com said:
>> COrreçãozinha, em que eu troquei a ordem para não confundir sobre de que é
>> o fatorial:
>>
>> Mais tarde eu espero conseguir explicar, mas creio que a solução é
>>
>> S = (1/n!)*[ 1 + S_a + S_b ], em que
>>
>> >>> S_a = Somatório de { A*(n!)/[ (n - 2A)!*2A ] }, com A variando de 1
até
>>
>> o inteiro menor ou igual a (n - 1)/2
>>
>> >>> S_b = Somatório de { B*(n!)/[ (n - 2B - 1)!*(2B + 1) ] }, com B
>> >>> variando
>>
>> de 1 até o inteiro menor ou igual a (n - 2)/2
>>
>> Claro que, para incorporar S_a, devemos ter n >=3 , e, para incorporar
S_b,
>> devemos ter n >= 4.
>> [...]
>
>Para n=5, S_a = 1*5!/(3!*2) + 2*5!/(1!*4) = 10 + 60 = 70, S_b = 1*5!/(2!*3)
=
>20, logo existiriam 70+20+1 = 91 permutações com rencontres. Mas, na
>realidade, só há 76:
>
>01234 01243 01324 01342 01423 01432 02134 02143 02314 02341
>02413 02431 03124 03142 03214 03241 03412 03421 04123 04132
>04213 04231 04312 04321 10234 10243 10324 10432 12034 12304
>12430 13024 13204 13240 14032 14203 14230 20134 20314 20431
>21034 21043 21304 21340 21403 21430 23014 23104 24031 24130
>30124 30214 30241 31024 31042 31204 31240 31402 31420 32014
>32104 34201 34210 40132 40213 40231 41023 41032 41203 41230
>41302 41320 42031 42130 43201 43210
>
>(Eu usei um programinha para gerar a lista acima.)
>
>[]s,
>
>- --
>Fábio Dias Moreira
>http://dias.moreira.nom.br/
>-----BEGIN PGP SIGNATURE-----
>Version: GnuPG v1.2.3 (GNU/Linux)
>
>iD8DBQFAcMCqalOQFrvzGQoRArbzAKDiTpKoTAzjhyJkCOabtM8uLIRm4gCfVn+W
>Et1H9PUYEp0d6WU5JOD+r5Q=
>=HDC4
>-----END PGP SIGNATURE-----
>
>
>=========================================================================
>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
>=========================================================================
>

=========================================================================
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
=========================================================================