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