As Raízes da Combinatória

02/12/2011 16:50

 

“AS RAÍZES DA COMBINATÓRIA”

 

Cristiane Maria Roque Vazquez[1]

José Carlos Nogueira

 

Introdução

 

     A análise combinatória foi um tanto negligenciada pela HISTÓRIA DA MATEMÁTICA. São poucos os livros e artigos que tratam do assunto, o que vem dificultar ainda mais seu estudo. Porém, há boas razões para estudá-la, pois, como uma espécie de subcultura matemática ela surgiu como suporte para efetuar alguns cálculos enquanto a álgebra, a geometria e a aritmética estavam freqüentemente presentes em trabalhos mais relevantes.

      Hoje em dia, a combinatória é foco de muita atenção, pois há pouca literatura com uma definição satisfatória para esta ciência e suas ramificações.

      Podemos dizer que o período central para o desenvolvimento da Análise Combinatória se deu no final da Idade Média ao início da Renascença na Europa, com destaque para os matemáticos Luca Pacioli, Girolamo Cardano, Niccolo Tartaglia, Pierre Fermat e Blaise Pascal.

 

CONTAGEM

     

      Para Wilson (1990), as regras básicas de contar e suas aplicações têm sido enfatizadas, desde as civilizações mais antigas por exemplos absurdos onde era destacada a elusiva propriedade da memorização, como o Problema 79 do Papiro Egípcio de Rhind (cerca de 1650 a.C.) onde números aparecem ao lado de desenhos de alguns hieróglifos que podem, aproximadamente, traduzido como segue:

Casas                                   7

Gatos                                   49

Ratos                        343

Trigo                          2401

Medidas                   16807

                        19607

      Leon Rodet, em 1881, sugeriu a seguinte interpretação para esse problema:

      “Há sete casas, cada uma com sete gatos, cada gato mata sete ratos, cada rato teria comido sete safras de trigo, cada qual teria produzido sete medidas de grãos; quantos itens têm ao todo?”.

      É impossível dizer que essa interpretação é a correta, mas a existência de problemas similares tem algumas implicações.

      Como exemplo, temos uma poesia infantil que parece ter sobrevivido em várias culturas e que serve para introduzir o campo de problemas combinatórios (Biggs, 1979):

“Quando eu estava indo para St. Ives,

Eu encontrei um homem com sete mulheres,

Cada mulher tem sete sacos,

Cada saco tem sete gatos,

Cada gato tem sete gatinhos,

Gatinhos, gatos, sacos e mulheres,

Quantos estavam indo para St. Ives?”

 

      Essa adivinhação é usualmente interpretada como uma brincadeira, pois se o narrador estava indo para St. Ives os outros estavam em sentido oposto e a resposta é nenhum. Se aplicada ao narrador é um. Porém poderia ter servido a propósitos mais sérios ou até mesmo ser um bom padrão de exercício aritmético sem sentido.

      Tal especulação apóia-se na existência de um problema similar encontrado no Liber Abaci (Livro do Ábaco ou do Cálculo), escrito por Fibonacci em 1202, que assim foi traduzido:

      “Sete mulheres velhas estão indo para Roma; cada uma delas têm sete mulas; cada mula carrega sete sacos; cada saco contém sete pães; cada pão tem sete facas; e cada faca tem sete bainhas. Qual é o número total de coisas?”

É difícil negar a possibilidade de uma conexão entre o problema de Fibonacci e a poesia infantil. Também é sabido que versões do Liber Abaci foram usadas por vários séculos e há a possibilidade de que o problema 79 do Papiro de Rhind pode ser 3000 anos mais velho que o de Fibonacci. Nesses casos estamos lidando com a somatória de uma série de potências de sete.

 

PERMUTAÇÕES E COMBINAÇÕES

 

É o estudo dos arranjos e subconjuntos de um conjunto de objetos. Há uma certa dificuldade sobre essa terminologia sendo que essas palavras têm adquirido sentido matemático preciso, mas que não são observados no uso da língua.

Em estudos históricos essa dificuldade se dá pelo fato que tradutores de palavras antigas usam um sentido vago e casual, em vez de somente matemático.

O aspecto mais simples desse conteúdo é a enumeração de cordas de r símbolos, cada uma das quais pode ser dada por um conjunto de n símbolos. Com a aplicação da contagem multiplicativa há n^r de tais cordas.

O 1º exemplo disso ocorre no famoso livro chinês I Ching, originado por ditados e crenças sobre presságios para o tempo e outras características básicas da vida dos camponeses e consiste em regras para investigação, previsão e explicação para quase tudo.

O sistema I Ching é baseado em dois símbolos, o Yang (-) e o Yin (- -).

Estes símbolos foram combinados em:

• Trigramas (conjunto de três símbolos),
• Hexagramas (conjunto de seis símbolos)

Dessa forma existem 2³ trigramas e 2⁶ hexagramas chegando as n^r regras para a combinação com repetição.

Se o Yang representa a número 1 e o Yin representa o zero, então a última ordenação corresponde exatamente a ordem numérica binária.

Não há evidências de que os chineses tenham usado os símbolos antes de sua descoberta por Leibniz e outros. Leibniz acabou ficando com a falsa impressão que a ordenação binária foi utilizada no I Ching nos tempos antigos e creditou aos antigos chineses a prioridade na descoberta da aritmética binária.

Parece que, há muito tempo, os hindus já consideravam questões envolvendo permutações e combinações.

Um exemplo disso surge do tratado médico de Susruta que data do século VI a.C., embora sem muita certeza. Neste tratado encontramos discussões das várias espécies de demonstração que podem ser feitas pela combinação básica entre: doce, ácido, salino, pungente, amargo e adstringente. Há uma lista sistemática de combinações: 6 tomadas separadamente, 15 de dois em dois, 20 de três em três, 15 de quatro em quatro, 6 de cinco em cinco e 1 tomados todos juntos.

Regras para encontrar respostas a problemas combinatórios sem a necessidade de listar todos os casos foram surgindo e tomando lugar ao longo do tempo.

O número de combinações de n coisas tomadas r duas a duas é dado pela fórmula:

 

E o número de permutações de um grupo de n objetos é:

n! = n.(n – 1)...2.1.

Acredita-se que a fórmula para o nº de combinações já era conhecida pelos hindus no século VI d.C.

No tratado de Brahmagupta (livro com 20 capítulos escrito por Brahmagupta (598? – 670?) sobre astronomia, cálculo aritmético e álgebra) há alguns indícios sobre o conhecimento hindu nesse tempo, porém, os capítulos mais relevantes para a combinatória não haviam sido traduzidos para o inglês.

Somos felizardos por haver uma tradução fidedigna de partes relevantes do livro Lilavati, escrito pelo grande matemático indiano Bhaskara em 1150, onde há uma grande evidência de que ele conhecia a fórmula de combinações e também o n! da regra para permutações.

 

QUADRADOS MÁGICOS

 

Para Wieleitner (1932), o problema mais antigo que se relaciona com a teoria dos números e com a Análise Combinatória é o da formação dos quadrados mágicos.

Biggs (1979) diz que o termo quadrado mágico (de ordem n) é um arranjo dos números 1, 2, 3, ... , n² em uma tabela quadrada n x n, de tal modo que cada linha, cada coluna e cada diagonal têm a mesma soma.

 

O 1º exemplo registrado de um quadrado mágico é o diagrama LO SHU de um antigo chinês:

 

=

4          9          2   3          5          7   8          1          6

Este diagrama está associado às 9 salas do palácio mítico de Ming Thang onde vários ritos eram realizados, sendo que a substituição destes símbolos por números inteiros determina o famoso quadrado mágico denominado Saturn. Este quadrado causava uma grande fascinação para a maioria das pessoas, pois nesta época, mesmo a mais simples aritmética era algo espantoso. Needham (1959) diz que este quadrado data do século I d.C. e Berge (1971) acredita que pode ter sido escrito por volta de 2000 a.C.

Não se sabe nem como e nem quando a idéia de quadrados mágicos foi transmitida aos árabes. Sabe-se que eles tinham grande interesse em quadrados mágicos e suas contribuições foram importantes.

Quadrados maiores que o Lo Shu foram encontrados no 2º livro da Enciclopédia compilada (cerca de 990 d.C.) por estudantes árabes sendo que vários trabalhos sobre quadrados mágicos foram escritos e regras para construir quadrados de uma dada ordem foram desenvolvidas.

Num trabalho de al-Buni aparece uma técnica de fronteira, porém, acredita-se que ele não descobriu sozinho os métodos que descreve e, provavelmente, estes se originaram na Pérsia.

Não há nenhuma evidência de que os chineses têm prioridade sobre os árabes na construção de quadrados de ordem superior ao Lo Shu.

O manuscrito de Moschopoulos escrito em 1315 foi o 1º trabalho sobre quadrados mágicos em uma linguagem ocidental.

Os árabes viam os quadrados mágicos mais como objetos de mistério enquanto Moschopoulos tratou-os matematicamente.

Agrippa (1486 – 1535), um famoso ocultista, designou quadrados de ordens 3, 4, 5, 6, 7, 8 e 9 para os “planetas” astrológicos: Saturno, Júpiter, Marte, o Sol, Vênus, Mercúrio e a Lua.

No século XIV nós encontramos um quadrado mágico de ordem 4 em Melancolia I por Albrecht Dürer associado a Júpiter.

Podemos perceber a simetria que existe a partir do centro do quadrado, a soma dos vértices é 17 e também 10 + 7, 11 + 6, 2 + 15, 3 + 14 sendo que na última fileira temos 1514, data em que ele criou seu retrato.

 Outro exemplo é o quadrado mágico de SATOR encontrado em uma parede da Pompéia, mas especificamente em uma parede no banheiro de Paquius Proculus.

 

                           

Acredita-se que esse quadrado mágico esteve adotado por cristãos como um símbolo oculto, pois as letras que o compõem podem ser rearranjadas como uma cruz com o Pater Noster escrito nele e alfa e ômega nas bordas significando o começo e o fim de todas as coisas.

 

Em 1693, Frenicle , um matemático francês, apresentou todos os 880 quadrados de ordem 4 e em 1691, seu compatriota De La Loubère, descreveu um método de construção de quadrados de ordem ímpar conhecido como “método de fronteira”, que aprendeu com o povo de Sião (atual Tailândia).

A construção de quadrados através desse método é feita da seguinte forma:

Vamos construir um quadrado 3 x 3. Desenhe um quadrado e o divida em 9 celas. Contorne o quadrado com celas ao longo de suas bordas superior e direita e sombreie a do canto direito. Escreva 1 na cela central superior do quadrado original. A regra geral consiste em proceder diagonalmente para cima e para a direita com os inteiros sucessivos. As exceções a essa regra ocorrem quando essa operação nos leva para fora do quadrado original ou a uma cela já ocupada. Na primeira dessas situações voltamos ao quadrado original deslocando o número que cairia fora, ou de cima para baixo ou da direita para a esquerda, conforme seja o caso, para a última cela em branco da fila correspondente. Na segunda situação escrevemos o número na cela imediatamente abaixo da última a ter sido preenchida e prosseguimos com a regra geral. Deve-se considerar ocupada a cela sombreada. Em nossa ilustração, então, a regra geral indica que se deve colocar o 2 diagonalmente acima do 1 na terceira cela do contorno superior do quadrado. Portanto, deve-se deslocar o 2 para a terceira cela da linha de baixo do quadrado original. Prosseguindo com a regra geral quando se chega ao 3 atinge-se a segunda cela do contorno lateral direito do quadrado. Deve-se, então, deslocar o 3 para a segunda cela da primeira coluna do quadrado original. A regra geral colocaria o 3 na cela já ocupada pelo 1; portanto, ele deve ser escrito na cela exatamente abaixo da do último número registrado, ou seja, o 4. E assim por diante, teremos então:

 

	9	2
8	1	6	8
3	5	7	3
4	9	2

 

Os quadrados mágicos fornecem exemplos bem antigos de uma importante faceta da combinatória moderna, fixando condições para o estudo dos arranjos. Neste campo, há uma outra velha idéia: o quadrado latino.

A         B         C         D

B         C         D         A

C         D         A         B

D         A         B         C

 

Neste quadrado, cada letra surge uma só vez em cada linha e em cada coluna. Porém, é muito mais difícil encontrar pares ortogonais. Veja:

              

 

Provavelmente a forma mais antiga deste problema apareceu em 1723 no Ozanam’s Récréations Mathématiques sobre a questão de arranjar 16 cartões da corte em um quadrado contendo um ás, um rei, uma rainha e um valete sendo cada um deles de copas, de ouro, de paus e de espada.

Portanto, temos que os dois aspectos principais da combinatória são a contagem e o arranjo e os exemplos mais antigos são os quadrados mágicos.

Há também vários tabuleiros antigos que envolvem vagamente pensamentos de combinatória, o xadrez e os quebra-cabeças combinatórios que são de origem mais recente e alguns problemas como:

• O velho problema do lobo, da cabra e do repolho (cerca de 775 d.C.) que é atribuído a Alcuin (735 – 804) e diz:

“Um certo homem tinha que transportar para o outro lado de um rio, um lobo, uma cabra e um repolho. O único barco que encontrou podia carregar somente duas coisas cada vez. Por essa razão ele procurou um plano que pudesse permiti-lo levar todos para o outro lado totalmente ilesos. Diga a ele, quem é competente, como pode ser possível transportá-los seguramente?”

• O problema de Josephus que está associado ao historiador judeu Josephus Flavius (século I d.C.) que diz:

“A bordo de um navio estavam 15 turcos e 15 cristãos que se atrapalharam em mares violentos. A metade deles tem que ser sacrificada. Como isso poderia ser arranjado para que todos os cristãos fossem salvos?”

Josephus Flavius

Entre os cristãos havia um homem experimentado em contas e os dispôs de forma que todos ficaram vivos:

A disposição foi a seguinte: começando por 4 cristãos, depois 5 turcos, mais 2 cristãos, depois 1 turco, mais 3 cristãos, depois 1 turco, mais 1 cristão, depois 2 turcos, mais 2 cristãos, depois 3 turcos, mais 1 cristão, depois 2 turcos, mais 2 cristãos e finalmente mais 1 turco.

Assim, em roda ficaram dispostos todos os 30 e começando a contar primeiro pelos 4 cristãos em diante até chegar ao 9. Este seria lançado ao mar e assim de 9 em 9, todos os outros sucessivamente sem voltar atrás.

O problema é creditado a ele, pois é dito que salvou sua vida por fazer a escolha certa em uma situação similar.

 

PARTIÇÕES

 

Consideremos uma r-partição de um número inteiro positivo n como sendo o conjunto dos r inteiros positivos cuja soma é n. Por exemplo, há duas 3-partições do número 5:

3 + 1 + 1         e       2 + 2 + 1

Os primeiros estudos sobre partições aconteceram no reino dos jogos e nos jogos de azar, sendo necessário conhecimentos sobre os elementos da partição, combinação e probabilidade. Muitas dessas idéias foram desenvolvidas no livro Games, Gods, and Gambling de David (1962).

No tempo dos antigos egípcios (cerca de 3500 a.C.), o astragali (osso que liga a tíbia ao calcanhar) de certos animais era usado para determinar os movimentos nos jogos. Mais tarde, gregos e romanos chegaram ao resultado de que ao arremessar um astragali, este pode cair em um dos quatro caminhos e, portanto, com quatro ‘astragali’ há 35 diferentes possibilidades.

Provavelmente os estudantes gregos e romanos não analisaram esses resultados, pois consideravam-nos como eventos desorganizados.

Outros estudos sistemáticos sobre jogos de dados aconteceram em um famoso poema latino, De Vetula, do século XIII ou XIV que lista o número de possibilidades em que 3 dados podem cair, mostrando um simples cálculo combinatório que também foi usado pelos hindus há muito tempo.

O poema diz o seguinte:

“Se todos os três dados estão iguais há somente um modo para cada número; se dois estão iguais e outro diferente, há três modos; e se todos estão diferentes há seis modos.” (Katz, 1993, p.409, tradução nossa)

 

           

(Manuscript page from De Vetula showing all 56 ways three dice can fall.)

 

Esses resultados também podem ser apresentados como na tabela abaixo:

Assim temos  possibilidades distintas.

Para Biggs (1979), a falta de um conceito claro de probabilidade significa que o estudo dos jogos de azar não era ainda parte da ciência matemática.

 

O TRIÂNGULO ARITMÉTICO

 

Outra forma de se escrever a combinação dos números  surge como coeficientes na expansão binomial:

A história desses coeficientes é meio obscura e provavelmente tão antiga, que é praticamente impossível traçar suas origens. Os hindus estavam interessados nas raízes n-ésimas e assim desenvolveram a expansão da diferença . Isso é confirmado por uma passagem encontrada no trabalho do matemático árabe Omar Khayyam, escrito por volta de 1100:

“Os hindus tinham métodos para encontrar os lados de quadrados e cubos, baseados em um simples jogo de números, que é dizer o conhecimento dos quadrados dos nove dígitos 1², 2², 3², e assim por diante, junto com os produtos formados pela multiplicação deles ao mesmo tempo, duas e três de uma vez. Eu tenho escrito um trabalho que estabelece a precisão destes métodos, e eu tenho demonstrado que eles realmente têm conduzido para a conclusão desejada. Eu também tenho estendido o método para o caso de 4ª, 5ª, 6ª... raízes (tão grande quanto você quer), que não tem sido feito previamente. As provas que eu tenho dado nesse assunto são puramente ariméticas, baseadas na aritmética dos Elementos (de Euclides)”.

(Luckey 1947, 218, tradução nossa)

 

Não é sabido se esse trabalho continha a regra para encontrar os coeficientes binomiais por meio do triângulo aritmético. Consideremos esse triângulo como sendo uma tabela que é construída de cima e leva cada novo número para ser a soma dos dois imediatamente superiores. Assim:

 

 

 

1

1          1

1          2          1

1          3          3          1

1          4          6          4          1

1          5          10       10       5          1

....

 

Esta regra é equivalente à fórmula:

que tem uma prova combinatória direta quando os números são considerados como combinação de números.

Singh (1936), afirma que o triângulo aritmético era conhecido pelo estudante hindu Pingala, por volta de 200 a.C. Acredita-se que Pingala discutiu questões sobre metros poéticos, ou as formas de combinação de sílabas longas e curtas para produzir os ritmos desejados. É bastante provável que ele tenha obtido este resultado, ou pode ter simplesmente listado os vários casos. Não podemos nos precipitar e atribuir a ele o conhecimento do triângulo aritmético

O triângulo aritmético é apresentado, e sua construção é explicada, em um manual de Aritmética escrito pelo matemático e astrônomo árabe al-Tusi em 1265. O autor usa o triângulo como uma ferramenta na extração de raízes, e explica como se fosse uma técnica demonstrada, em vez de uma nova descoberta. Assim poderíamos dizer que as observações de Omar Khayyam estavam certas e que ele realmente teve algum conhecimento do método.

Recentemente, outros fatos sugerem que o triângulo aritmético foi conhecido por outro matemático árabe, al-Karagi, que morou alguns anos antes da época de Omar Khayyam, porém, o trabalho no qual al-Karagi pode ter desenvolvido o método está perdido, mas é referido em outro tratado pelo mesmo autor.

Há várias referências mais recentes para o triângulo aritmético em textos árabes, sendo que em todos os casos, os números na tabela são usados no contexto da expansão binomial, como parte de uma técnica para encontrar raízes. Acredita-se que os números que aparecem também eram os números combinatórios, mas não podemos apontar para alguma menção explícita do fato em um trabalho árabe deste período.

Os matemáticos da Europa medieval seguiram o caminho dos árabes e o triângulo aritmético não é encontrado em trabalhos europeus até o século XVI, quando aparece no tratado de Apianus (1527), e na Integra Aritmética de Stifel (1544). Estes livros, especialmente o último, eram extremamente conhecidos por toda a Europa ocidental. A partir daí, pode-se assumir que o triângulo aritmético era conhecimento comum entre matemáticos europeus. Os números eram usados na extração de raízes, mas o reconhecimento de sua interpretação combinatória pode ter sido ocultada por muito tempo.

Em 1653, Pascal escreveu seu Traité du Triangle Arithmétique, mas só foi publicado em 1665. Pascal construiu seu "triângulo aritmético", onde qualquer elemento é a soma de todos os elementos da linha anterior situados exatamente acima ou à esquerda do elemento desejado.

 

Por exemplo, na terceira linha temos 15 = 5 + 4 + 3 + 2 + 1. O triângulo é obtido desenhando-se a diagonal como na figura ao lado. Uma das aplicações que Pascal fazia do seu triângulo era a determinação dos coeficientes binomiais. Por exemplo, os números ao longo da quarta diagonal 1,3, 3,1 são os coeficientes sucessivos da expansão de (a + b)³.

O triângulo aritmético às vezes tem sido conhecido como triângulo de Pascal, apesar do fato de que ele não foi o primeiro a discuti-lo. Há muitas coisas importantes e úteis no livro de Pascal, mas, provavelmente, muito pouco delas parece ser suas próprias descobertas originais. O grande mérito do livro é sua claridade. Pascal deixou bastante claro que os números no triângulo aritmético são importantes, tanto quanto coeficientes binomiais como números combinatórios. Ele usava-o para em questões sobre jogos, e em particular, na solução do famoso “Problemas de Pontos” que ele tinha conhecido no curso de correspondência com Fermat.

O Tratado de Pascal contém o que é provavelmente o 1º tratamento moderno reconhecido dos elementos pelo jovem Leibniz, que, apesar de seu título, é tanto quanto um tratado sobre lógica e filosofia quanto sobre matemática. A partir daí, a “Combinatória” passou a ser um  ramo aceito de aprendizagem.

 

CONSIDERAÇÕES FINAIS

 

A combinatória originou-se nas civilizações orientais e não somente no Ocidente e era freqüentemente associada com aspectos incomuns ou não convencionais da erudição.

Vimos um pouco da contribuição das variadas combinações dos hindus, dos “místicos” quadrados mágicos dos chineses e dos árabes e verificamos que a Matemática também tem sido estimulada por problemas de incontestada profundidade e seriedade.

Atualmente, a Combinatória tem encontrado uma variedade de usos, nas ciências puras e aplicadas, e tem se tornado foco de muita atenção.

 

BIBLIOGRAFIA

 

BERGE, C. Principles of Combinatorics. Vol 72. New York: Academic Press,1971. p.1-11.

BIGGS, N. L. The roots of combinatorics. Revista Historia Mathematica. Vol 6. 1979. p.109-136.

WIELEITNER, H. Historia de la Matematica.Barcelona: Labor. 1932. p.134

WILSON, R. J.; LLOYD, E. K. Combinatorics. 1990. p.952-965.

URL: https://mathworld.wolfram.com/MagicSquare.html (versão 14/01/2004).

URL:https://www.malhatlantica.pt/mathis/Problemas/Josephus/Josephus.htm(versão 07/06/2004)

URL: https://www.malhatlantica.pt/mathis/Problemas/Ives/Ives.htm (versão 07/06/2004)