Re: [obm-l] Dica de problema.

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

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" <nicolau@sucuri.mat.puc-rio.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>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, faccast@impa.br 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
=========================================================================