RE: [obm-l] permutacap caotica..

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

Ola Vinicius e demais
colegas desta lista ... OBM-L,
(escreverei sem acentos)

Vou aproveitar este feriado para responder esta solicitacao com 
tranquilidade.

1) DEFINICAO

Uma permutacao de elementos e dita caotica se nenhum de seus elementos ocupa 
a posicao

original, vale dizer, fixamos previamente uma particular permutacao que 
imnplicitamente

especifica as posicoes originais originais dos elementos e procuramos 
determinar de quantas

maneiras podemos permutar estes mesmos elementos de maneira que nenhum deles 
permaneca em

sua posicao original. Exemplificando :

EXEMPLO 1

Vamos considerar a permutacao ABCD, tomada como o referencial ( inercial ? 
). A permutacao ACDB nao e

caotica pois o elemento "A" mantem a posicao original. Ja a permutacao DABC 
e caotica, pois

nenhum elemento mantem a posicao original.

2) ASPECTOS HISTORICOS

As PERMUTACOES CAOTICAS surgiram num problema proposto ao Euler numa carta 
que o Nicolau

Bernoulli lhe remeteu. Em linhas gerais o problema era assim ...

( Nicolau propoe a Euler ) De quantas maneiras N cartas, duas a duas 
distintas,  podem ser

colocadas em N envelopes com destinatarios previamente preenchidos de 
maneira que nenhuma

destinatario receba a carta que corretamente  deveria lhe ter sido remetida 
?

O Euler gastou algum tempo para resolver o problema, mas a solucao que ele 
encontrou e

longa, grosseira e sem inteligencia. Mas ...  a solucao do Nicolau ... 
Belissima ! Faz jus

tanto a tradicao da familia Bernoulli quanto a tradicao dos Nicolau's que 
conhecemos ...

Eis o TRUQUE DO NICOLAU :


3) EQUACAO FUNCIONAL

Para facilitar a esposicao, FIXE no lado esquerdo a permutacao ABCDEFG. Seja 
C(7) o numero

total de permutacoes caoticas. Agora, com o lado direito IMAGINE dois casos 
:

(1) Todas as permutacoes caoticas nas quais a letra "A" esta na posicao da 
letra "B" e a

letra "B" esta na posicao da letra "A". Quantas permutacoes caoticas sao 
possiveis ?

Claramente : C(5), pois apenas iremos permutar caoticamente as 5 outras 
letras restante

(2) Todas as permutacoes caoticas nas quais a letra "A" esta na posicao da 
letra "B" e a

letra "B" NAO ESTA na posicao da letra "A". Quantas permutacoes sao 
possiveis ? Aqui comeca

o TRUQUE DO NICOLAU ... a letra "B" tera 5 posicoes para ocupar e as demais 
letras tambem,

vale dizer, tudo sucede como se estivessemos permutando caoticamente 6 
elementos. Logo, a

resposta e C(6).

Ora, os casos (1) e (2) encerram TODAS as permutacoes caoticas nas quais a 
letra "A" esta na

posicao da letra "B", isto e, o total de permutacoes em que a letra "A" esta 
na posicao da

letra "B" e C(5) + C(6). Agora,  colocando a letra "A" sucessivamente nas 
posicoes das letra

"C", ...,"G" e repetindo para cada caso os raciocinios (1) e (2) acima e 
facil ver que :

C(7) = 6*( C(5) + C(6) )

Esta tecnica, obviamente, pode ser extendida para o caso de N elementos. 
Assim :

C(N) = (N-1) * [ C(N-2) + C(N-1) ]

Que e a "equacao funcional" para as permutacoes caoticas.


4) FORMULA EXPLICITA

Em geral, o estudante iniciante busca uma formula explicita, fechada, com a 
qual fica facil

fazer computacoes diretas. E facil obter uma tal expressao. Eis como :

C(N) = (N-1) * [ C(N-2) + C(N-1) ]
C(N) - N*C(N-1) = -[c(N-1) - (n-1)*C(N-2) ]

substituindo N sucessivamente por 3, 4, ... ate N, teremos :

C(3) - 3*C(2) = -[ C(2) - 2*C(1) ]
C(4) - 4*C(3) = -[ C(3) - 3*C(2) ]
...
C(N) - N*C(N-1) = -[c(N-1) - (n-1)*C(N-2) ]

Multiplicando membro a membro estas N-2 igualdades e eliminado os fatores 
iguasi que estao nos dois lados do sinal de igualdade :

C(N) - N*C(N-1) = [(-1)^(N-2)]*[C(2) - 2*C(1) ]
Como obviamente C(1)=0, C(2)=1 e (-1)^(N-2) = (-1)^N :

C(N) - N*C(N-1) = (-1)^N

Dividindo tudo por N! teremos :

C(N)/N!   +   C(N-1)/(N-1)!   =   [(-1)^N]/N!

Substituindo N por 2, 3, ... ate N e somando as N-1 equacoes, vem :

C(N) = (N!)*{ 1/2!  -   1/3!   +   1/4!   - ... + [(-1)^N]/N! }

Que e a formula explicita para permutacoes caoticas


5) ALEM DE EULER E NICOLAU


Alguem ja disse que "Os matematicos nao nascem, eles surgem". Sem entrar no 
merito ou interpretacao do aforismo, me parece que ele encerra uma grande 
dose de verdade ... quantos de nos nao tem alguma historia singela de 
(RE)descobertas e pesquisas cientificas quando ainda era uma crianca ? 
Olhando para a historia, para a vida de alguns colegas matematicos e para 
mim mesmo, parece-me que tal fenomeno e mais a regra que a excecao ...

Neste problema de Matematica Elementar e possivel exercitar esta ALMA ou 
ESPIRITO que se admira e se maravilha diante do desconhecido e sem receios 
ou frescuras se lanca em especulacoes e pesquisas solitarias. O confronto 
com o desconhecido, com o misterio, e uma das mais empolgantes facetas da 
investigacao ...

PROBLEMA : Sejam dadas DUAS permutacoes caoticas, digamos, ABCDEFG e 
BCDEFGA. Quantas permutacoes SIMULTANEAMENTE caoticas em relacao as duas 
podemos construir ?

Euler e Nicolau, pelo que sei, nao resolveram esta questao e nem ao menos 
citaram-na, o que a torna muito mais interessante. Digamos que eles 
resolveram O CASO 1, isto e, quanto fixamos apenas uma permutacao. O 
problema se refere ao caso 2. Poedemos portanto por :

C(N,1) = (N!)*{ 1/2!  -   1/3!   +   1/4!   - ... + [(-1)^N]/N! }

Qual a expressao para C(N,2), a resposta do problema proposto ? Bom, 
claramente que C(N,N-1)=1. Assim, ja temos dois dados :

C(N,1) = (N!)*{ 1/2!  -   1/3!   +   1/4!   - ... + [(-1)^N]/N! }
C(N,N-1) = 1 = (N!)*{ 1/N!}

Isto sugere que para o caso P, a expressao tem a forma :

C(N,P) = (N!)*{ 1/P! - ... [(-1)^f(N)]/N! }

Este caminho e o PRIMEIRO CAMINHO : tentar descobrir atraves da FORMULA 
EXPLICITA a cara da expressao para o caso P.

Um SEGUNDO CAMINHO seria tentar reformar ou generalizar o raciocinio do 
Nicolau e chegar a uma EQUACAO FUNCIONAL tal como ele chegou. Essa linha de 
investigacao tambem parece promissora, pois pode suceder que uma expressao 
explicita dependa de alguma relacao mantida entre os elementos das 
permutacoes fixas em relacoes as quais buscamos as caoticas

Note que este problema esta diretamente ligado a questao dos QUADRADOS 
LATINOS que, ate onde eu sei, ainda e uma questao em aberto da Matematica 
elementar. Mas o mais importante aqui nao e resolver o problema. E muito 
mais tentar e lancar a esta aventura do pensamento, a este contato e 
confrontacao com o desconhecido que e quase ou muito proxima da experiencia 
religiosa, quando sabemos que DO OUTRO LADO existe algo real, belo e 
verdadeiro e que com a nossa mente nos podemos descerrar.

Um Abraco a Todos
Paulo Santa Rita
5,1513,120906

>From: vinicius aleixo <viniciusaleixo@yahoo.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: [obm-l] permutacap caotica..
>Date: Wed, 11 Oct 2006 22:04:07 -0300 (ART)
>
>   Quantos anagramas da palavra VESTIBULAR não possuem nenhuma letra em sua
>   posição original?
>
>
>   Alguem poderia aproveitar e me explicar como funciona essa tal de 
>permutacao caotica?de onde veio, como deduzo a formula e talz...
>
>
>   vlw!
>
>   vinicius
>
>
>---------------------------------
>  Novidade no Yahoo! Mail: receba alertas de novas mensagens no seu 
>celular. Registre seu aparelho agora!

_________________________________________________________________
Insta-le já o Windows Live Messenger. A nova geração do messenger. 
http://get.live.com/messenger/overview

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