[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Re: [obm-l] permutações circulares com repetição
Ola Rafael e demais
colegas desta lista,
O unico TEOREMA DE MOREAU que eu conheco e aquele. Eu nunca vi aquele
teorema ser aplicado para resolver problemas do tipo que voce apresentou.
Todavia, o Prof Morgado explicitamente cita TEOREMA DE MOREAU. Segue que :
1) O teorema de moreau QUE EU CONHECO tem aplicacoes QUE EU NAO CONHECO.
2) Existe um teorema de moreau QUE EU NAO CONHECO que tem aplicacoes QUE EU
CONHECO.
Independente de tudo isso, com os modestos conhecimentos habituais de
Analise Combinatoria podemos abordar o problema que voce propos ...
A - O MISTERIO
Se alguem lhe perguntar de quantas formas distintas N pessoas podem sentar
em uma mesa redonda, incontinenti voce respondera : de (N-1)! maneiras. E a
conhecidissima formula de permutacoes circulares ... COM ELEMENTOS, DOIS A
DOIS, DISTINTOS !
Bom ... Por que essa formula e assim ? Dentre um montao de respostas
igualmente validas, e digna de destaque aquela que diz que A CADA PERMUTACAO
CIRCULAR DE N ELEMENTOS,DOIS A DOIS DISTINTOS correspondem N PERMUTACOES
LINEARES. Logo, calculando o total possivel de permutacoes lineares, basta
dividir esse total por N para obtermos o total de permutacoes circulares :
N*PC = PL, PL=N! => PC= N!/N => PC=(N-1)!
Um exemplo : A permutacao circular ABCD correspondem as permutacoes lineares
ABCD, BCDA, CDAB e DABC.
E isto e, evidentemente, absolutamente geral ... UM PERMUTACAO CIRCULAR E(
OU PODE SER DEFINIDA COMO ), EM VERDADE, UM CONJUNTO DE PERMUTACOES LINEARES
... Mas, e preciso tomar cuidado ... Quando entram elementos repetidos, nem
sempre a quantidade de permutacoes lineares que correspondem a uma dada
permutacao circular e constante !
Para ver isso, considere a permutacao circular :
1) ABAB. Correspondem a ela as seguintes permutacoes lineares : ABAB e BABA.
Duas portanto !
2) AABB. Correspondem a ela as seguintes permutacoes lineares : AABB, ABBA,
BBAA, BAAB. Quatro portanto !
Portanto, os mesmos objetos - A,A,B,B - distribuidos ao longo de um circulo
de duas maneiras diferentes geraram quantidades distintas de permutacoes
lineares. Isso so ocorre, claramente, quando nas permutacoes circulares
entram objetos repetidos .
Bom, e dai ? O que fazer ? Considerando que :
1) Calcular e construir permutracoes lineares com elementos repetidos e um
problema facil e ja bem resolvido.
2) Cada permutacao circular corresponde a um conjunto de permutacoes
lineares
O que se deve fazer e estudar, observando e caracterizando com precisao
todos os fenomenos que ocorrem e, so entao, passar a uma possivel
explicacao.
B - OS FENOMENOS
1) E facilmente observavel e pode-se confirmar com inumeras experiencias o
seguinte : se uma permutacao circular pode ser expressa como multiplo de um
de seus SUB-GRUPOS entao a quantidade de permutacoes lineares geradas sera
igual a extensao do SUB-GRUPO.
Exemplo :
ABBCABBC = 2(ABBC)
A permutacao acima gera apenas 4 permutacoes lineares : ABBCABBC, BBCABBCA,
BCABBCAB, CABBCABB
Daqui se conclui, imediatamente, que se a multiplicidade dos elementos de
uma permutacao circular tem MDC igual a 1 entao, mesmo havendo elementos
repetidos, a quantidade de permutacoes lineares geradas sera sempre igual a
extensao da permutacao circular, isto e :
N*PC = PL => PC = PL/N
como PL = (M1+M2+...+Mn)!/(M1!*M2!*...*Mn!) segue que :
PC = (M1+M2+...+Mn - 1)!/(M1!*M2!*...*Mn!)
Onde Mi sao as multiplicidades dos objetos e M1+M2+...+Mn=N
2) Se o MDC entre as multiplidades nao e um entao a permutacao circular pode
ser expressa sucessivamente como multiplo dos diversos divisores do MDC e
essas serao as unicas permutacoes circulares para as quais ha a contracao no
numero de permutacoes lineares geradas.
Exemplo :
ABABABAB = 4(AB) implica nas PL's ABABABAB, BABABABA
AABBAABB = 2(AABB) implica nas PL's AABBAABB, ABBAABBA, BBAABBAA, BAABBAAB
Nos caso em que o MDC das Multiplicidades e diferente de 1 somos obrigados a
admitir que so os SUB-GRUPOS com extensao igual aos divisores do MDC geram
contracoes nas PL's pois, de outra forma, O MDC seria diferente, o que e um
absurdo !
Com os casos 1) e 2) exaurem todas as possibilidades nas quais uma PC
corresponde a PL's em numero inferior a sua extensao e resolve o seu
problema.
SO UM DETALHE : Eu observo que muitas pessoas, diante de um problema, buscam
previamente uma tecnica com a qual podem trata-lo e resolve-lo. A verdadeira
tecnica de resolucao de qualquer problema e o pensamento : primeiro nos
observamos as coisas, DEPOIS procuramos entende-las. A tecnica ou teoria
aparece depois, naturalmente. Newton foi muito feliz quando falava sobre
isso :
" Pois A MELHOR E MAIS SEGURA maneira de pensar parece-me ser a seguinte :
PRIMEIRO, pesquisar com afinco as propriedades das coisas; COMPROVAR estas
propriedades, por intermedio de experiencias e, SO ENTAO, adiantar-se
LENTAMENTE para o campo das hipoteses relativas a explicacao. As teorias
devem ser criadas para explicar as propriedades verificaveis das coisas e
nao para impor propriedades a elas "
(NEWTON)
Um abraco
Paulo Santa Rita
3,1304,210502
>From: Rafael WC <rwcinoto@yahoo.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] permutações circulares com repetição
>Date: Mon, 20 May 2002 14:55:57 -0700 (PDT)
>
>Olá Pessoal!
>
>Obrigado Morgado e Paulo pela ajuda.
>
>Paulo, entrei na página que você indicou. Encontrei a
>demonstração de um teorema de Moreau que sinceramente
>não consegui associar nem de longe com permutações
>circulares com repetição.
>
>Como você falou que conhece um caminho alternativo,
>acho que vou abusar da sua boa vontade e perguntar
>qual é. Se puder me ajudar, agradeço muito. Hoje fui à
>biblioteca da faculdade e andei procurando alguns
>livros, mas todos param nas permutações circulares
>simples!!
>
>Muito obrigado,
>
>Rafael.
_________________________________________________________________
Converse com amigos on-line, conheça o MSN Messenger:
http://messenger.msn.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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================