[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Combinatoria do Circulo
Colegas da Lista,
Saudacoes !
Se precisarmos dispor "N" pessoar ao longo de uma mesa
redonda, de quantas maneiras podemos fazer isso ?
Em geral, a resposta a esta pergunta e : de ( N - 1 ) !
maneiras. E nao e raro que apreciemos o seguinte raciocinio
:
Sejam P1, P2, ..., Pn as N pessoas dispostas ao longo da
mesa. Partindo de P1 e seguindo ao longo da mesa em sentido
horario, iremos gerar a PERMUTACAO LINEAR : P1, P2, ..., Pn.
Se houvessemos partido da pessoa "P2", teriamos gerado a
PERMUTACAO LINEAR : P2, P3, ..., P1. Isto e suficiente para
deixar claro que qualquer PERMUTACAO CIRCULAR possivel gera
N permutacoes lineares, duas a duas distintas. Ora, o total
de permutacoes lineares que podemos fazer com N pessoas (
Ex: Filas Indianas ) e N!. Assim, o total de PERMUTACOES
CIRCUARES sera:
T = N! / N => T = ( N - 1 )! ( EXPRESSAO A )
A "Analise Combinatoria do Circulo" parece se resumir a isso
... ao menos na maioria dos livros de 2 grau !
O que comumente ocorre e que nao se menciona que a EXPRESSAO
A acima pressupoe o conceito de "sentido de percurso" ...
Quero dizer com isso que se estamos analisando uma situacao
em que o sentido de percurso e irrelevante, a EXPRESSAO A
acima nao condiz com a realidade...
Se o sentido de percurso nao distingue duas disposicoes,
vale dizer, quando podemos "rodar" de 180 graus em torno de
um diametro e obter a mesma disposicao
Este e o caso de quando precisamos determinar quantos
"colares" podemos fazer dispondo-se de N contas, duas a duas
distintas.
Num caso como este o numero de PERMUTACOES CIRCULARES e:
V = ( N - 1)! / 2 ( EXPRESSAO B )
Muitos dos conceitos acima sao discutiveis e podem ser
apresentados de uma forma ou de outra. Todavia, o que nao se
discute e que a COMBINATORIA DO CIRCULO nao pode se
restringir a isso ... Os fenomenos que ocorrem no circulo
sao por demais interessantes e merecem um tratamento mais
pomenorizado ...
So para suscitar interesse considere o caso das PERMUTACOES
CIRCULARES COM ELEMENTOS REPETIDOS. Se na "Combinatoria
Linear" existe o caso das permutacoes com elementos
repetidos, por que nao se aborda o seu analogo circular ?
Vamos ver se conseguimos comecar a abordar este tema, vale
dizer, se conseguimos encontrar alguma coisa interessante
sobre as PERMUTACOES CIRCULARES COM ELEMENTOS REPETIDOS.
Vamos considerar primeiro o caso em que o sentido de
percurso ao longo do circulo distingue duas permutacoes.
Antes de encetar propriamente na pesquisa acho valido
assinalar uma posicao filosofica, contestavel como tudo que
se refere a Filosofia, mas que tem se mostrado proficua ao
longo dos seculos.
Desde Platao, passando por Poincare e Hardy e chegando hoje
a Herman Weyl e Godel, para nao citar muitos outros belos
cerebros, muitos matematicos admitem que nao se inventa em
Matematica: nesta ciencia, tudo SE DESCOBRE ! O matematico,
por este ponto de vista, e apenas um cientista de um mundo
ideal dotado de uma realidade especial. Ele olha com o
intelecto para este mundo e nele divisa as propriedades e
relacoes entre os objetos ideais que percebe. Ser um
matematico e, assim, ser um cientista do mundo superior do
espirito ...
Ora, ninguem descreve melhor o ato de fazer ciencia do que
Newton. Ele diz : " Pois a melhor e mais segura maneira de
fazer ciencia consiste, primeiro, em pesquisar com afinco as
propriedades das coisas, corroborar estas propriedades por
intermedio de experiencias e so entao adiantar-se,
lentamente, para o campo das hipoteses relativas a sua
explicacao. As hipoteses so devem ser usadas para explicar
as experiencias e propriedades das coisas e, nao, para
postula-las ... "
O que nos vamos fazer aqui e precisamente isso. Vamos
analisar as propriedades mais notaveis das PERMUTACOES
CIRCULARES COM ELEMENTOS REPETIDOS ( PCR ) e propor
explicacoes para elas
Desde ja temos por estabelecido que o caso linear esta bem
assentado. Vale dizer, se temos X1 objetos identicos entre
si, X2 objetos identicos entre si, ..., Xn objetos identicos
entre si e se Xi # Xj se i # j ( estou usando "#" paa
simbolizar diferente ) entao o numero de permutacoes
lineares que podemos fazer e:
L{ N / X1,X2,...,XN } = N! / ( X1! * X2! *...* Xn! )
onde N = X1 + X2 + ... + Xn
No caso em que os elementos sao dois a dois distintos a cada
permutacao circular de N elementos correspondem N
permutacoes lineares. E no caso, que estamos analisando, em
que os elementos nao sao distintos, dois a dois ?
Considere os objetos A, A, B, B. Quantas permutacoes
lineares eles geram ?
L{ 4 / 2,2 } = 4! / (2!*2!) = 6
Estas 6 permutacoes lineares sao agrupadas em duas
permutacoes circulares, a saber:
AABB e ABAB.
A permutacao circular AABB gera: AABB, ABBA, BBAA e BAAB.
A permutacao circular ABAB gera: ABAB e BABA.
Como se ve, no mundo das PCR´s, nem sempre uma dada
permutacao circular gera tantas lineares quanto o seu
comprimento ou extensao !
por que sera que este fenomeno ocorre ? Claramente, olhando
a permutacao "ABAB", salta os olhos a explicacao : ela e
como uma funcao periodica. Ela e formada de blocos iguais de
"AB". Ocorreria o mesmo se a permutacao fosse, digamos:
ABABABABAB. Se uma permutacao e periodica e seu periodo tem
estensao P ela ira gerar apenas P permutacoes lineares,
independente de sua extensao. Fui claro ? Estou certo ? O
que voces acham ?
Bom. Se e correto a minha observacao entao posso enunciar o
seguinte
TEOREMA : O total de PERMUTACOES CIRCULARES COM OS ELEMENTOS
REPETIDOS X1, X2, ...,Xn e:
PCR{ N / X1,X2,...,Xn } = ( N - 1)! / X1!*X2!*...*Xn!
se MDC(X1, X2,...,XN) = 1.
Nesta formula : N = X1 + X2 + ... + Xn
Com efeito, se MDC(X1,X2,...,Xn) = 1 entao qualquer
permutacao circular nao podera ser periodica, vale dizer,
nao podera ser formada por uma quantidade finita e reiterada
de sub-sequencias, pois isto equivaleria a dizer que o MDC e
igual a quantidade de periodos. Assim, Toda Permutacao
circular dara origem a tantas permutacoes lineares com
elementos repetidos quanto a sua extensao. Ora, o total de
permutacoes lineares e L{ N / X1! * X2 * ... *Xn } e,
portanto, o total de PCR´s sera:
PCR{N / X1,...,Xn}=(X1+...+Xn - 1)! / ( X1!*...*Xn! )
Bom. Se a nossa logica esta certa, cabe agora investigar o
caso em que MDC(X1,X2,...,Xn) = P > 1.
Caso P Primo
Aqui vamos descobrir algo notavel, relacionado aos numeros
perfeitos. Com efeito, se P for primo, entao
Se precisarmos dispor "N" pessoar ao longo de uma mesa
redonda, de quantas maneiras podemos fazer isso ?
Em geral, a resposta a esta pergunta e : de ( N - 1 ) !
maneiras. E nao e raro que apreciemos o seguinte raciocinio
:
Sejam P1, P2, ..., Pn as N pessoas dispostas ao longo da
mesa. Partindo de P1 e seguindo ao longo da mesa em sentido
horario, iremos gerar a PERMUTACAO LINEAR : P1, P2, ..., Pn.
Se houvessemos partido da pessoa "P2", teriamos gerado a
PERMUTACAO LINEAR : P2, P3, ..., P1. Isto e suficiente para
deixar claro que qualquer PERMUTACAO CIRCULAR possivel gera
N permutacoes lineares, duas a duas distintas. Ora, o total
de permutacoes lineares que podemos fazer com N pessoas (
Ex: Filas Indianas ) e N!. Assim, o total de PERMUTACOES
CIRCUARES sera:
T = N! / N => T = ( N - 1 )! ( EXPRESSAO A )
A "Analise Combinatoria do Circulo" parece se resumir a isso
... ao menos na maioria dos livros de 2 grau !
O que comumente ocorre e que nao se menciona que a EXPRESSAO
A acima pressupoe o conceito de "sentido de percurso" ...
Quero dizer com isso que se estamos analisando uma situacao
em que o sentido de percurso e irrelevante, a EXPRESSAO A
acima nao condiz com a realidade...
Se o sentido de percurso nao distingue duas disposicoes,
vale dizer, quando podemos "rodar" de 180 graus em torno de
um diametro e obter a mesma disposicao
Este e o caso de quando precisamos determinar quantos
"colares" podemos fazer dispondo-se de N contas, duas a duas
distintas.
Num caso como este o numero de PERMUTACOES CIRCULARES e:
V = ( N - 1)! / 2 ( EXPRESSAO B )
Muitos dos conceitos acima sao discutiveis e podem ser
apresentados de uma forma ou de outra. Todavia, o que nao se
discute e que a COMBINATORIA DO CIRCULO nao pode se
restringir a isso ... Os fenomenos que ocorrem no circulo
sao por demais interessantes e merecem um tratamento mais
pomenorizado ...
So para suscitar interesse considere o caso das PERMUTACOES
CIRCULARES COM ELEMENTOS REPETIDOS. Se na "Combinatoria
Linear" existe o caso das permutacoes com elementos
repetidos, por que nao se aborda o seu analogo circular ?
Vamos ver se conseguimos comecar a abordar este tema, vale
dizer, se conseguimos encontrar alguma coisa interessante
sobre as PERMUTACOES CIRCULARES COM ELEMENTOS REPETIDOS.
Vamos considerar primeiro o caso em que o sentido de
percurso ao longo do circulo distingue duas permutacoes.
Antes de encetar propriamente na pesquisa acho valido
assinalar uma posicao filosofica, contestavel como tudo que
se refere a Filosofia, mas que tem se mostrado proficua ao
longo dos seculos.
Desde Platao, passando por Poincare e Hardy e chegando hoje
a Herman Weyl e Godel, para nao citar muitos outros belos
cerebros, muitos matematicos admitem que nao se inventa em
Matematica: nesta ciencia, tudo SE DESCOBRE ! O matematico,
por este ponto de vista, e apenas um cientista de um mundo
ideal dotado de uma realidade especial. Ele olha com o
intelecto para este mundo e nele divisa as propriedades e
relacoes entre os objetos ideais que percebe. Ser um
matematico e, assim, ser um cientista do mundo superior do
espirito ...
Ora, ninguem descreve melhor o ato de fazer ciencia do que
Newton. Ele diz : " Pois a melhor e mais segura maneira de
fazer ciencia consiste, primeiro, em pesquisar com afinco as
propriedades das coisas, corroborar estas propriedades por
intermedio de experiencias e so entao adiantar-se,
lentamente, para o campo das hipoteses relativas a sua
explicacao. As hipoteses so devem ser usadas para explicar
as experiencias e propriedades das coisas e, nao, para
postula-las ... "
O que nos vamos fazer aqui e precisamente isso. Vamos
analisar as propriedades mais notaveis das PERMUTACOES
CIRCULARES COM ELEMENTOS REPETIDOS ( PCR ) e propor
explicacoes para elas
Desde ja temos por estabelecido que o caso linear esta bem
assentado. Vale dizer, se temos X1 objetos identicos entre
si, X2 objetos identicos entre si, ..., Xn objetos identicos
entre si e se Xi # Xj se i # j ( estou usando "#" paa
simbolizar diferente ) entao o numero de permutacoes
lineares que podemos fazer e:
L{ N / X1,X2,...,XN } = N! / ( X1! * X2! *...* Xn! )
onde N = X1 + X2 + ... + Xn
No caso em que os elementos sao dois a dois distintos a cada
permutacao circular de N elementos correspondem N
permutacoes lineares. E no caso, que estamos analisando, em
que os elementos nao sao distintos, dois a dois ?
Considere os objetos A, A, B, B. Quantas permutacoes
lineares eles geram ?
L{ 4 / 2,2 } = 4! / (2!*2!) = 6
Estas 6 permutacoes lineares sao agrupadas em duas
permutacoes circulares, a saber:
AABB e ABAB.
A permutacao circular AABB gera: AABB, ABBA, BBAA e BAAB.
A permutacao circular ABAB gera: ABAB e BABA.
Como se ve, no mundo das PCR´s, nem sempre uma dada
permutacao circular gera tantas lineares quanto o seu
comprimento ou extensao !
por que sera que este fenomeno ocorre ? Claramente, olhando
a permutacao "ABAB", salta os olhos a explicacao : ela e
como uma funcao periodica. Ela e formada de blocos iguais de
"AB". Ocorreria o mesmo se a permutacao fosse, digamos:
ABABABABAB. Se uma permutacao e periodica e seu periodo tem
estensao P ela ira gerar apenas P permutacoes lineares,
independente de sua extensao. Fui claro ? Estou certo ? O
que voces acham ?
Bom. Se e correto a minha observacao entao posso enunciar o
seguinte
TEOREMA : O total de PERMUTACOES CIRCULARES COM OS ELEMENTOS
REPETIDOS X1, X2, ...,Xn e:
PCR{ N / X1,X2,...,Xn } = ( N - 1)! / X1!*X2!*...*Xn!
se MDC(X1, X2,...,XN) = 1.
Nesta formula : N = X1 + X2 + ... + Xn
Com efeito, se MDC(X1,X2,...,Xn) = 1 entao qualquer
permutacao circular nao podera ser periodica, vale dizer,
nao podera ser formada por uma quantidade finita e reiterada
de sub-sequencias, pois isto equivaleria a dizer que o MDC e
igual a quantidade de periodos. Assim, Toda Permutacao
circular dara origem a tantas permutacoes lineares com
elementos repetidos quanto a sua extensao. Ora, o total de
permutacoes lineares e L{ N / X1! * X2 * ... *Xn } e,
portanto, o total de PCR´s sera:
PCR{N / X1,...,Xn}=(X1+...+Xn - 1)! / ( X1!*...*Xn! )
Bom. Se a nossa logica esta certa, cabe agora investigar o
caso em que MDC(X1,X2,...,Xn) = P > 1.
Caso P Primo
________________________________________________
Don't E-Mail, ZipMail! http://www.zipmail.com/