[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] O Truque do Nicolau
Ola Pessoal,
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
=========================================================================