Ola Prof Nicolau e demais colegas desta lista ... OBM-L,
Eu nao conhecia este problema, mas a sua mensagem - abaixo - e muito estimulante.
Existe mais de uma maneira de abordar o problema, todas na dependencia de alguma investigacao mais profunda. Uma que ocorre imediatamente a cabeca e a seguinte :
INVESTIGACAO 1 )
A primeira linha de um quadrado latino e qualquer das permutacoes que podemos fazer com os N elementos 1, 2, 3, ...,N. Podemos fazer isso de N! maneiras. De quantas maneiras podemos montar a segunda linha ? Claramente que a segunda linha sao todas as PERMUTACOES CAOTICAS de N elementos ! Nicolau Bernoulli e Euler ja calcularam essa quantidade e vale :
N!( 1/(2!) - 1/(3!) + ... +- 1/(N!)
Quem seria a terceira linha ? Claramente que deve ser uma PERMUTACAO CAOTICA em relacao as duas primeiras. Que nome daremos a esta permutacao ? Bom, uma ideia pode ser assim : A primeira linha seriam as permitacoes de 1 especie, na segunda estariam a de 2 especie, na terceira as de 3 especie e assim sucessivamente, ate a ultima linha, onde estaria uma permutacao caotica de N-esima especie.
O numero de quadrados latinos, claramente, seria o produto dos numeros alencados acima. O problema, pelo que sei, e que nos so sabemos calcular as PERMUTACOES CAOTICAS de segunda especie. A solucao dos problema esta, portanto, na depemndencia desta investigacao.
E importante notar que esta linha de investigacao tem o duplo sabor de resolver em definitivo o problema dos quadrados latinos e ser uma continuidade de um trabalho iniciado pelo Euler e Nicolai bernoulli. E portanto uma contribuicao nao desprezivel e uma continuidade historica interessante.
Eu acredito que o numero de permutacoes caoticas de 2 especie ( e posteriores ) devem ser uma sub-serie interessante da seria (1/(2!) - 1/(31) + ... +- 1/(N!) ), dado que esta serie surge nas permutacoes caoticas de primeira especie. Enfim, e um caminho interessante ...
INVESTIGACAO 2)
Existe uma classe ampla de quadrados latinos faceis de construir e calcular. Para ver isso, considere o caso N=4 :
1234, jogue o 4 para a primeira posicao. Resulta : 4123, jogue o 3 para a primeira posicao. Resulta : 3412 jogue o 2 para a primeira posicao. Resulta : 2341
O quadrado acima e quadrado latino. O que fizemos ? Simplesmente dispomos os numeros 1,2,3,4 e percorremos em um sentido previamente fixado a partir dos diversos elementos. Isso e o que se chama uma PERMUTACAO CIRCULAR. Estamos, pois, identificando um quadrado latino com uma PERMUTACAO CIRCULAR ...
Agora, permutamos, as linhas das diversas formas possiveis, mantendo os numeros nas mesmas colunas ( ou o inverso, permutamos as colunas e mantemos os elementos nas mesmas linhas ). Isso fornece 4! quadrados latinos, dois a dois distintos. Bom, aqui surge uma luz :
Para N elementos, existem (N-1)! permutacoes circulares. Para cada permutacao circular associamos um quadrado latino. As linhas podem ser permutadas de N! modos. Assim, existem : (N-1)!*N! quadrados latinos derivados diretamente da associacao QUADRADO LATINO -> PERMUTACAO CAOTICA.
Seja portanto QL(N) o total de quadrados latinos de ordem N, entao :
QL(N) = (N-1)!N! + F(N), onde F(N) e uma funcao que ainda nao conhecemos ...
O que podemos dizer sobre F(N) - numa primeira observacao - que nos permite uma aproximacao com a sua forma definitiva ? O seguinte : Dado a associacao QUADRADO LATINO <-> PERMUTACAO CIRCULAR, no computo (N-1)!N! estao TODAS as permutacoes circulares de 1,2,...,N, isto e, associando os quadraodos latinos computados no calculo de (N-1)!N! pela PERMUTACAO CIRCULAR que o originou, teremos todas as permutacoes de 1,2,...,N. Isso significa, claramente, que qualquer outro quadrado latino e, em verdade, uma associacao de DUAS ou mais permutacoes circulares, isto e :
F(N) = A1*G(N,2) + A2*G(N,3) + ... + An-1*G(N,N)
onde A1, A2, ..., An sao inteiros nao todos nulos e G(N,P) e o total de quadrados latinos obtidos da associacao de P PERMUTACOES CIRCULARES. A questao e saber como associar, "operar", estas permutacoes circulares de forma a gerar os quadrados latinos que serao computados em F(N).
A meu ver, aqui trata-se, a principio, de um trabalho experimental. Pegamos os quadrados latinos de ordem N=3, N=4, retiramos aqueles oriundos das permutacoes circulares e vemos como estao montados os outros. Deve surgir algum padrao de somposicao de permutacoes circulares e, a partir dai, adivinhamos a lei geral. E tambem uma linha de pesquisa interessante ...
INVESTIGACAO 3)
Bom, esta ideia a baseada na q-contagem, na transformacao dos indices de um quadrado latino em polinomios, mas ela chegou na minha cabeca muito rapidamente, quando eu ainda estava escrevendo as coisas acima e nao consegui registra-la. Mas "senti" que era uma ideia legal e promissora. Havendo tendo eu me concentro e ela volta e entao eu comunico.
Um Grande Abraco ! Paulo Santa Rita 5,1045,030703
From: "Nicolau C. Saldanha" <[EMAIL PROTECTED]> Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] Dica de problema. Date: Wed, 2 Jul 2003 13:40:28 -0300
On Wed, Jul 02, 2003 at 10:06:48AM -0300, [EMAIL PROTECTED] wrote:
> Caros colegas, aqui vai um bom exercicio de contagem.
> Seja S uma matriz nxn com entradas em {1,... ,n} que nao possui elementos
> repetidos em suas filas (linhas e colunas).
> Quantas matrizes existem com tal propriedade?
Uma matriz com estas propriedades é chamada de quadrado latino. Não existe fórmula simples para o número de quadrados latinos de tamanho n. Na verdade, o valor do que você pede para n = 10 só foi calculado em 1990. Os primeiros valores são:
1,2,12,576,161280,812851200,61479419904000,108776032459082956800, 5524751496156892842531225600,9982437658213039871725064756920320000
Você pode ler mais sobre esta seqüência nas páginas abaixo:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002860 http://mathworld.wolfram.com/LatinSquare.html http://www.combinatorics.org/Volume_2/PostScriptfiles/v2i1n3.ps
[]s, N. ========================================================================= 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 =========================================================================
_________________________________________________________________ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com
========================================================================= 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 =========================================================================
