Make your own free website on Tripod.com

Home

O que é Combinatória

A Análise Combinatória trata de vários tipos de problemas e dispõe alem das combinações, arranjos e permutações, de outras técnicas para atacá-los: o principio da inclusão-exclusão, o principio das gavetas de Dirichlet, as funções geradoras, a teoria de Ramsey são exemplos de técnicas poderosas da Analise Combinatória.

Dois freqüentes tipos de problemas que ocorrem são:

1)      Demonstrar a existência de subconjuntos de elementos de um conjunto finito dado e que satisfazem certas condições.

2)    Contar ou classificar os subconjuntos de um conjunto finito e que satisfazem certas condições dadas.

Esse é um dos encantos desta parte da matemática, em que problemas fáceis de enunciar revelam-se por vezes difíceis, exigindo uma alta dose de criatividade para sua solução.


A Origem da Combinatória

Foi a necessidade de calcular o número de possibilidades existentes nos chamados jogos de azar que levou ao desenvolvimento da Analise Combinatória, parte da matemática que estuda os métodos de contagem. Estes estudos foram iniciados já no século XVI, pelo matemático Niccollo Fontana (1500-1557), conhecido como Tartaglia. Depois vieram os franceses Pierre de Fermat(1601-1665) e Blaise Pascal (1623-1662).

A analise combinatória visa desenvolver métodos que permitam contar – de uma forma indireta – o número de elementos de um conjunto, estando esses elementos agrupados sob certas condições.

A analise combinatória é utilizada no estudo do calculo das probabilidades, são essencialmente problemas de contagem, ou seja, consistem na determinação do número de elementos de conjuntos finitos sujeitos a leis de formação bem definidas.


UM POUCO DE HISTÓRIA

MORGADO, Augusto César de Oliveira ed alli. Análise combinatória e probabilidade .

                                                  Rio de Janeiro, Coleção do Professor de Matemática - SBM, 1991.

O desenvolvimento do binômio (1+x)nestá entre os primeiros problemas estudados e ligados à Análise Combinatória. O matemático hindu Báskara (1114-1185?), conhecido geralmente pela "fórmula de Báskara" para a solução de equações do 2º grau, sabia calcular o número de permutações, de combinações e de arranjos de n objetos. O mesmo aconteceu com o matemático e filósofo religioso francês Levi ben Gerson (1288-1344), que nasceu e trabalhou no sul da França, e que entre outras coisas, tentou demonstrar o 5º Postulado de Euclides. 

Abraham De Moivre (1667-1754), Daniel Bernoulli (1700-1782) e Jacques Phillipe Marie Binet (1786-1856) mostraram como achar diretamente os números de Fibonacci (também conhecido por Leonardo de Pisa (1175?-1250?)), sem ser necessário calcular todos eles, até o que desejamos. Para isso, De Moivre utilizou pela primeira vez uma técnica extremamente poderosa, a das funções geradoras. Esta técnica, para estudar sucessões recorrentes, foi bastante desenvolvida por Euler (1707-1783), em seu livro clássico Introductio in Analysin Infinitorum, onde ele utiliza para atacar o problema das partições de um inteiro. O interesse de Euler por este problema surgiu devido a uma pergunta que lhe foi feita pelo matemático francês Phillipe Naudé, que trabalhava em Berlim, em uma carta, na qual, entre outras coisas, perguntava de quantas maneiras um número pode ser escrito como soma de inteiros positivos distintos. Esta pergunta, prontamente respondida por Euler, foi a origem da "teoria das partições" ou "partitio numerorum", como escreveu Euler. Várias obras suas, muitas delas sobre probabilidades, contêm resultados importantes da Análise Combinatória. Em particular, devemos a ele o enunciado e a solução do Problema das Sete Pontes de Königsberg , um teorema da Teoria dos Grafos, parte muito importante, atualmente, da Análise Combinatória.

A Análise combinatória tem tido um crescimento explosivo nas últimas décadas. A importância de problemas de enumeração tem crescido enormemente, devido a necessidades em teoria dos grafos, em análise de algorítmos, etc. Muitos problemas importantes podem ser modelados matematicamente como problemas de teoria dos grafos (problemas de pesquisa operacional, de armazenamento de informações em bancos de dados nos computadores, e também problemas de matemática "pura", como o famoso problema das 4 cores).

Já em 1937 o matemático húngaro-americano George Pólya (1887-1985) introduziu nova e importante técnica de enumeração, que se tem prestado às mais variadas aplicações, permitindo tratar, de maneira unificada, desde a enumeração do número de isômeros de uma substância, até a enumeração de grafos.A aplicação da teoria do Pólya é o de determinar o número de tetraedros regulares "diferentes" com faces pintadas com duas cores, preto e branco, por exemplo. Outra teoria importante de combinatória foi criada pelo lógico inglês F. P. Ramsey (1903-1930); ela garante a existência de certas configurações.

Jaime Bernoulli foi o primeiro de uma longa linhagem de matemáticos e sábios de uma família suíça. Seu diário mostra que ele começou a interessar-se pelos problemas de combinatória e de probabilidades em torno de 1685. Manteve longa correspondência sobre o assunto com Leibniz, que levantava objeções ao Teorema de Bernoulli.


Curiosidades

Manuscrito milenar revela que Arquimedes fazia análise combinatória há 2.200 anos

O texto que segue foi extraído da Folha de SP, Maio, 21/12.  Deve ser de muito interesse aos matemáticos, uma vez que, como sabemos, as descobertas  relacionadas a análise combinatória  são recentes. Como Arquimedes viveu antes de Cristo, é desconhecido aos matemáticos que Arquimedes tenha ocupado deste tema.  Uma outra coisa interessante a ser observada é o uso do computador em pesquisas arqueológicas. Este casamento pode render bons frutos como vocês podem observar ao ler o texto a seguir:

__________________________________________________________

Eureka nas entrelinhas: Manuscrito milenar revela que Arquimedes fazia análise combinatória há 2.200 anos.

Imagem realçada por computador mostra vestígios do tratado 'Stomachion',de Arquimedes, em original de cerca de mil anos sobrescrito várias vezes.

Gina Kolata escreve para o 'The New York Times':

Dois mil e duzentos anos atrás, o grande matemático grego Arquimedes escreveu um tratado chamado 'Stomachion'. Diferentemente de seus outros escritos, logo caiu na obscuridade.

Pouco dele sobreviveu, e ninguém sabia o que pensar dele, mas agora um historiador da matemática em Stanford, EUA, examinando antigos pergaminhos sobrescritos por monges e quase destruídos pelo mofo,parece ter resolvido o mistério sobre o assunto do tratado.

No processo, ele abriu uma surpreendente nova janela sobre o trabalho do gênio que é mais lembrado (talvez apocrifamente) por seu grito de 'Eureca!' ao descobrir um modo inteligente de determinar se uma coroa real era mesmo de ouro puro.

O 'Stomachion', conclui o historiador Reviel Netz, estava bem à frente de seu tempo: um tratado sobre análise combinatória, campo que não voltou a emergir até o surgimento das ciências da computação.

A meta da análise combinatória é determinar de quantos modos um dado problema pode ser resolvido. E encontrar o número de modos pelos quais o problema no 'Stomachion' pode ser resolvido é tão difícil que, quando Netz pediu a uma equipe de quatro especialistas para fazê-lo, tomou seis semanas.

Embora Netz reconheça que suas descobertas não podem ser provadas com certeza absoluta, ele apresentou o trabalho a outros especialistas, e eles disseram concordar com sua interpretação.

Numa recente e nevada manhã de domingo na Universidade de Princeton, três dúzias de acadêmicos se reuniram para ouvir Netz e em seguida o parabenizaram, dizendo que seus argumentos faziam sentido.

'Estou convencido', disse Stephen Menn, um historiador de matemática antiga na Universidade McGill, numa entrevista após a sessão de duas horas.

Entre todos os trabalhos de Arquimedes, o 'Stomachion' foi o que menos atenção atraiu, ignorado ou dispensado como sem importância ou ininteligível.

Apenas um pequeno fragmento da introdução sobreviveu e, até onde se podia dizer, parecia ser sobre um quebra-cabeça infantil antigo - também conhecido como Stomachion - que envolvia colocar faixas de papel juntas de diversas maneiras para compor diferentes formas.

Não fazia sentido que um homem da estatura de Arquimedes se ocupasse com tal jogo.

Como resultado, afirma Netz, 'as pessoas diziam, 'Não sabemos do que ele trata'.

Na realidade, de acordo com Netz, a sabedoria predominante estava baseada numa interpretação errônea. Arquimedes não estava tentando juntar peças de papel em formas diferentes; ele estava tentando ver de quantos modos as 14 faixas irregulares poderiam ser reunidas para formar um quadrado.

A resposta -17.152- exigia uma contagem cuidadosa e sistemática de todas as possibilidades.

'Foi difícil', disse Persi Diaconis, um estatístico de Stanford que trabalhou nele com a colega Susan Holmes, que também é sua mulher, e um segundo casal de matemáticos combinatórios, Ronald Graham e Fan Chung, da Universidade da Califórnia em San Diego.

De maneira independente, um cientista da computação, William H. Cutler,da companhia Chicago Rawide, em Elgin, Illinois, escreveu um programa que confirmou a correção da resposta obtida pelos matemáticos.

Talvez tão marcante quanto a descoberta de que Arquimedes conhecida análise combinatória seja a história de um manuscrito que data de 97, escrito em grego num pergaminho.

É um dos três conjuntos de cópias dos trabalhos de Arquimedes que estiveram disponíveis durante a Idade Média (os outros foram perdidos, e nenhum deles continha o 'Stomachion').

'Para Arquimedes, como para todos os outros da Antiguidade, não temos os trabalhos originais', diz Netz. 'O que temos são cópias das cópias das cópias.'

Os cientistas avaliam as cópias comparando os textos que elas têm em comum e procurando por passagens exclusivas, que podem atrair algum interesse em particular.

Por esses parâmetros, o manuscrito era valioso.

Mas foi quase perdido. No século 13, explica Netz, monges cristãos,precisando de material para compor um livro de orações, despedaçaram o manuscrito, apagaram seu conteúdo, dobraram suas páginas ao meio e cobriram com texto religioso.

Após séculos de uso, o livro de orações -conhecido como palimpsesto, porque contém texto que foi sobrescrito - terminou em um monastério de Constantinopla.

O Santo Sepulcro: Johan Ludvig Heiberg, um estudioso dinamarquês, o encontrou em 1906 na biblioteca da Igreja do Santo Sepulcro, em Istambul. Ele notou traços suaves de matemática sob as orações. Usando uma lente de aumento,transcreveu o que podia e fotografou cerca de dois terços das páginas.

Aí o documento desapareceu, perdido com outros preciosos manuscritos no conflito entre gregos e turcos. Ele reapareceu nos anos 1970, nas mãos de uma família francesa que o comprara em Istambul, no início da década de 1920, e o guardara por cinco décadas antes de tentar vendê-lo.

A família teve problemas para encontrar um comprador, no entanto, em parte porque havia alguma dúvida sobre se havia adquirido legalmente o manuscrito, para começar, mas também porque ele parecia horrível. Foi consumido pelo mofo, nos anos em que a família o reteve, e estava áspero e feio. Em 1998, um bilionário anônimo o adquiriu por US$ 2 milhões e o cedeu ao Museu de Arte Walters, em Baltimore, onde ele ainda está.

'É preciso enfatizar quanto a situação é incrivelmente incomum', diz Netz. Com o manuscrito em mãos, o pequeno grupo de estudiosos passou a reconstruir o texto original em grego. Não foi fácil.

'Você olha a olho nu e não vê nada, absolutamente nada', conta Netz. Luz ultravioleta revelou leves traços de escrita, mas incluía tanto as orações quanto a matemática.

'O maior problema é a combinação do fato de que muitos caracteres estão escondidos com o fato de que muitos são tão suaves que ficam invisíveis', afirma Netz. E, ainda por cima, há as lacunas das páginas que foram arrancadas ou consumidas pelo mofo.

Ruído filtrado

Imagens por computador ajudaram. Roger Easton, do Instituto deTecnologia de Rochester, Keith Knows, da Boeing, e William Christens-Barry, da Universidade Johns Hopkins, conseguiram desenvolver programas para separar a escrita do 'ruído' em torno dela, e em muitos lugares as letras gregas saltaram da tela do computador.

'O produto do software é incrível', disse Netz. Mas também tinhalimitações, especialmente perto das pontas rasgadas das páginas.

Para reconstruir os textos, Netz e Nigel Wilson, um professor de estudos clássicos na Universidade de Oxford, estão usando cada ferramenta disponível: luz ultravioleta, imagens de computador, as fotografias de Heiberg e seu próprio conhecimento íntimo de textos gregos antigos.

Ainda assim, em algumas áreas, 'o texto provavelmente permanecerá uma conjectura', segundo Netz.

Foi a sorte que o levou a seu primeiro lampejo acerca da natureza do'Stomachion'.

Em agosto, quando estava preste a começar a transcrever uma das páginas do manuscrito, ele conta que recebeu um presente pelo correio, um modelo recortado em vidro azul de um quebra-cabeça Stomachion.

Ele havia sido feito por um negociante aposentado da Califórnia que localizou Netz pela internet como um estudioso renomado de Arquimedes.

Olhando para o modelo, Netz percebeu que um diagrama na página que estava transcrevendo era na verdade um rearranjo das peças do quebra-cabeça Stomachion. De repente, ele viu aonde Arquimedes queria chegar.

O diagrama envolvia 14 peças, e a palavra 'profusão' parecia associada a ele. Heiberg e os que o seguiram pensavam que isso significava que seria possível montar muitas figuras com o rearranjo das peças.

'Isso é parte da razão pela qual as pessoas não entendiam sobre o que versava aquilo', diz Netz. Mas a velha interpretação parecia trivial,dificilmente digna do tempo de Arquimedes.

Conforme ele foi examinando as páginas do manuscrito e montando o texto,percebeu que o que Arquimedes estava realmente perguntando parecia ser:

'De quantos modos você pode juntar as peças para formar um quadrado?'

Essa questão, para Netz, 'tem significado matemático'.

'As pessoas presumiram que não havia combinatória na Antiguidade',continua. 'Não provocou, portanto desconfiança alguma que Arquimedes tenha dito que existiam muitos arranjos e que ele iria calculá-los.

Mas foi isso que Arquimedes fez; suas introduções vão sempre ao ponto.'

Arquimedes teria resolvido o problema? 'Estou certo de que ele resolveu,ou não o teria apresentado', afirma Netz. 'Eu não sei é se ele resolveu corretamente.'

Com relação ao nome, derivado da palavra grega para estômago, os matemáticos estão incertos. Mas Diaconis tem um palpite. 'Vem de 'virar o estômago' ', disse. 'Se você se envolve com ele, é o que acontece.'

 


Conclusão

        A partir deste trabalho podemos ampliar nossos conhecimentos matemáticos com algo tão importante que é o princípio de contagem da Análise Combinatória.

Home