Estou reproduzindo abaixo um raciocinio do Nicolau Bernoulli / Euler no caso das permutacoes caoticas. O excelente livro de Combinatoria do Prof Morgado trata desse tema, com outra tecnica de abordagem. Em linhas gerais, o Nicolau supoe a existencia da funcao C(N) e, a seguir, deduz uma relacao de recorrencia. Voces perceberao que o raciocinio destes matematicos e muito bonito.
Logo depois proponho uma generalizacao. Para quem quiser refletir mais sobre estas coisas, sugiro que se analise com calma o seguinte triangulo aritmetico:
1/(2!) - 1/(3!) + 1/(4!) - 1/(5!) + 1/(6!) - 1/(7!) + ...
1/(3!) - 2/(41) + 3/(5!) - 4/(6!) + 5/(7!) - ...
1/(4!) - 3/(5!) + 6/(6!) - 10/(7!) +...
1/(5!) - 4/(6!) + 10/(7!) - ...
1/(6!) - 5/(7!) + ...
+ 1/(7!) - ...
... ... ... ... ...Considere N objetos, que aqui serao representados genericamente pelos numeros naturais 1, 2, 3, ..., N. Adotando a permutacao 123 ... N como padrao, diremos que uma PERMUTACAO e CAOTICA ( em relacao a padrao ) se nenhum de seus elementos ocupar a posicao que originalmente ocuopava.
Exemplo : Se adotarmos 12345 como padrao, 23451 e 34512 sao caoticas enquanto 21354 nao e.
Queremos saber quantas permutacoes caoticas existem em relacao a uma permutacao fixada, adotada como padrao. O total de permutacoes caoticas que construtiveis a aprtir de N elementos sera representada C(N). Assim, fixemos a permutacao :
12345...N
Dividimos as C(N) caoticas em relacao a ela e que teem o 1 no lugar do 2 em dois conjuntos, a saber :
A) Aquelas nas quais o 1 esta no lugar do 2 e o 2 esta no lugar do 1 21XXX...X B) Aquelas nas quais o 1 esta no lugar do 2 e o 2 NAO esta no lugar do 1 X1XXX...X
O conjunto A) tem quantos elementos ? Bom, como 1 e 2 estao fixos, basta permutarmos caoticamente os N - 2 elementos restantes, isto e, o conjunto A) tem exatamente C(N-2) elementos. Portanto :
Conjunto A tem : C(N-2) elementos
O conjunto B) tem quantos elementos ? Aqui esta o TRUQUE DO EULER : Vamos permutar caoticamente. O 1 esta fixo na posicao do 2, o 2 nao pode ocupar a posicao do 1 mas pode ocupar qualquer outra das N - 2 posicoes restantes, qualquer outro elementos (3,4,...,N) pode ocupar N - 2 posicoes possiveis. Portanto, isso e equivalente a permutarmos caoticamente N-1 elementos, isto e, o conjunto B) tem C(N-1) elementos ...
Conjunto B tem : C(N-1) elementos
Ora A) + B) e o conjunto de TODAS AS PERMUTACOES CAOTICAS nas quais o elemento 1 ocupa a posicao do 2, isto e , Total de permutacoes caoticas nas quais o elemento 1 ocupa a posicao do 2 e igual a :
C(N-1) + C(N-2)
Agora basta reiterarmos sucessivamente este raciocinio : colocamos o 1 no lugar do 3 e dividimos estas permutacoes em dois conjuntos :
C) Aquelas nas quais o 1 esta no lugar do 3 e o 3 esta no lugar do 1 3X1XX...X D) Aquelas nas quais o 1 esta no lugar do 3 e o 3 NAO esta no lugar do 1 XX1XX...X
Aplicando um raciocinio identico ao que aplicamos antes, chegaremos a conclusao de que :
Conjunto C tem : C(N-2) elementos Conjunto D tem : C(N-1) elementos
E portanto :
Ora C) + D) e o conjunto de TODAS AS PERMUTACOES CAOTICAS nas quais o elemento 1 ocupa a posicao do 3, isto e , Total de permutacoes caoticas nas quais o elemento 1 ocupa a posicao do 3 e igual a :
C(N-1) + C(N-2)
Fica claro que vamos repetir este raciocinio N-1 vezes, isto e, vamos repeti-lo para o 1 ocupando sucessivamente as posicoes do 2, 3, 4, ..., N. Ao final, teremos C(N), todas as permutacoes caoticas, isto e :
C(N) = (N-1) * [ C(N-1) + C(N-2) ] RELACAO 1
A equacao de recorrencia acima foi obtida primeiramente por Nicolau Bernoulli, que propos o problema a Euler que, usando o raciocinio que reproduzi acima, chegou ao mesmo resultado. Em geral, os raros livros que tratam de permutacoes caoticas nao apresentam as coisas assim. Eles provam a validade da formula :
C(N) = N! * [ 1/(2!) - 1/(3!) + 1/(4!) - 1/(5!) + ... +- 1/(N!) ]
E claro que esta expressao esta contida da relacao de recorrencia. Mas o fundamental e o raciocinio que o Euler e o Nicolau desenvolveram. Fica como exercicio deduzi-la ( a formula ) da RELACAO 1.
Considere agora duas permutacoes, caoticas entre si, tais como :
1234 2341
Quantas permutacoes, caoticas em relacao as duas, existem ? Resposta : duas. A saber : 4123 e 3412
Considere agora as duas permutacoes, caoticas entre si :
1234 3412
Quantas permutacoes, caoticas em relacao as duas, existem ? Resposta : quatro. A saber : 4123, 2143, 4321, 2341.
Bom, os fenomenos acima mostram que o total de permutacoes caoticas em relacoes a duas outras permutacoes, caoticas entre si, depende de alguma relacao entre elas. Seria possivel generalizar o raciocinio do Euler, exposto acima, de forma a resolver tambem esse caso ?
O problema e uma modelagem valida para inumeras circunstancias. Por exemplo :
PROBLEMA 1 ) Seja A = { 1, 2, ..., N }. Quantas funcoes F:A->A existem que cumprem as duas seguintes condicoes :
a) F(X) nao tem ponto fixo
b) F(F(X)) nao tem ponto fixo
PROBLEMA 2 ) Uma matrix de 3 linhas e N colunas e dita ser latina se todos os seus elementos pertencem ao conjunto A = {1, 2, ..., N } e nenhuma fila ( linha ou coluna ) tem elementos repetidos. Quantas Matrizes latinas 3xN existem tais que
A1j = j, j = {1, 2, ..., N }. ( Aij e o elemento da linha i e coluna j )
PROBLEMA 3 ) Participam de uma mesa redonda N pessoas, cada uma das quais tendo um lugar pre-determinado para sentar e uma pasta com o seu nome para receber. Eremildo, que e um idiota, deve distribui as pessoas nos lugares bem como as pastas. Qual a probabilidade de que nenhuma pessoa sente no seu lugar correto e nao receba a pasta correta ?
Um Abraco a Todos ! Paulo Santa Rita 2,1608,140703
_________________________________________________________________ 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 =========================================================================
