Como prometi, aqui vai a "explicacao".
Como disse anteriormente, esse problema equivale a determar quantas das
permuta��es da matriz identidade nxn possuem ao menos um elemento n�o nulo
na diagonal.
Existe apenas uma matriz com n elementos 1 na diagonal, e n�o existe uma com
n - 1 elementos n�o nulos na diagonal sem que tenha o n-�simo.
Para n - 2 elemtos n�o nulos (frase que passarei a abreviar por T - 2),
basta sabermos de quantas formas podemos escolher 2 das n colunas --> C(n,2)
= n!/(2!*(n - 2)!)
T - M em geral:
Precisamos combinar pares K_i, K_j, com i dif. de j. Como AQUI n�o importa
a "ordem" (pois queremos apenas determinar o n�mero de matrizes poss�veis,
ficando a ordem do jogo subentendida nos pares (linha=rodada,
coluna=numero)), podemos CHAMAR um elemento de k_1 e o que lhe associa de
k_m, pegar outro k_2 e CHAMAR seu associado de k_(m-1) e assim por diante,
sendo que estes m correspondem as m colunas em permuta��o entre elas.
Este k_i, k_j significa uma permuta��o entre a coluna i e a coluna j da
matriz identidade.
Quando chegamos a (m + 1)/2 (se m for �mpar) ou m/2 (se m for par), o n�mero
de op��es para a correspond�ncia seguinte se repete. Por exemplo, para m = 5:
k_1 --> 4 op��es
k_2 --> 3 op��es
k_3 --> 3 op��es
k_4 --> 2 op��es
k_5 --> 1 op��o
Deste modo, o termo geral �, para m colunas sem 1 na diagonal:
para m par:
T - 2A: (2A - 1)!*A*C(n, 2A), com A >=1 desde que poss�vel
para m �mpar:
T - (2B + 1): (2B)!*B*C(n, 2B + 1), com B >=1 desde que poss�vel
para m = 0 (� a pr�pria matriz identidade) --> 1 op��o
Como temos n! arruma��es poss�veis, basta considerarmos a some de tudo e
dividir por n!
S_a = Somat�rio de { (2A - 1)!*A*C(n, 2A) }, A variando de 1 ao inteiro
menor ou igual a (n - 1)/2 --> S_a corresponde aos termos pares
S_b = Somat�rio de { (2B)!*B*C(n, 2B + 1) }, B variando de 1 ao inteiro
menor ou igual a (n - 2)/2 --> S_b corersponde aos termos impares
+ 1, que � o "termo" zero
Assim, S = [1/(n!)]*[ 1 + S_a + S_b ], que na mensagem anterior eu
simplifiquei para S_a e S_b, e espero eu que de forma correta....
[EMAIL PROTECTED] escreveu:
>
>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.
>
>=========================================================================
>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
=========================================================================
