 |
|
|
|||
 |
|||||
|
|
|
|
|||
|
|
|||||
Eduardo Gonçalves dos Santos
INTRODUÇÃO A Combinatória é um dos ramos mais ricos em problemas de enunciados simples com soluções, por vezes, bastante intrincadas. Na educação básica, ela é responsável pela ruptura de uma concepção – equivocada a nosso ver – da busca pela fórmula correta para cada tipo de problema. Isso em Combinatória é praticamente inatingível, tanto pela enorme variedade de problemas, como pelos diversos tipos de agrupamentos que podem figurar em um mesmo problema. Acreditamos que grande parte das dificuldades que os estudantes enfrentam ao estudar Combinatória advém justamente de tentar compreendê-la a partir dessa perspectiva. O tópico do qual nos propomos a falar neste texto diz respeito a um problema de contagem relacionado a caminhos em um reticulado. Nesse processo de contagem, intervêm alguns aspectos que consideramos relevantes no ensino da Matemática: a modelagem e a ligação entre os aspectos algébricos (no nosso caso, combinatórios) e aspectos geométricos de um problema. Junte-se a isso que ele serve de porta de entrada ao estudo de um mundo fascinante que é o estudo dos Números de Catalan, tema ainda hoje objeto de pesquisas. UM PROBLEMA INTRODUTÓRIO Na figura a seguir, vê-se um trecho de um bairro de uma cidade fictícia, onde aparecem 24 quadras divididas por 5 ruas verticais e 3 ruas horizontais.
Uma pessoa que está no ponto P deve movimentar-se pelas ruas até chegar ao ponto Q, utilizando-se de movimentos que lhe permitam ir à direita ou acima. A pergunta é: de quantas formas ela pode fazer esse trajeto? Se denotarmos o movimento de virar à direita por D e o de ir acima por A, notamos que o caminhante deve passar por 5 + 3 = 8 cruzamentos, sendo que em cada cruzamento ele deve adotar um movimento D ou A. Em essência, cada caminho é composto por uma sequência de 8 letras escolhidas entre D ou A, sendo que aparecem 5 Ds e 3 As. Trata-se, pois, de uma permutação de 8 objetos, sendo que um deles se repete três vezes e o outro cinco vezes. Portanto, o número de caminhos indo de P até Q, seguindo os movimentos permitidos, é:
Esse tipo de situação pode ser modelado matematicamente utilizando o plano cartesiano com os pontos de coordenadas inteiras e positivas representando as quadras. Os movimentos permitidos podem ser representados por segmentos horizontais ou verticais e os caminhos, por linhas poligonais formadas por segmentos ligando dois pontos que estejam na mesma linha horizontal ou na mesma linha vertical. Os caminhos podem ser vistos como uma escadaria (staircase walk) nesse plano, onde os degraus podem ter alturas e comprimentos variáveis. O problema traduz-se então em determinar o número possível de escadarias com o pé no ponto P e o topo no ponto Q. Na figura 2, temos dois exemplos de caminhos possíveis – um vermelho e outro amarelo.
Devemos notar que algo foi fundamental na contagem do número de trajetos possíveis: o fato de termos associado cada trajeto a uma “palavra” contendo as letras D e A. Essa associação vai se revelar muito importante, logo mais. Outra abordagem para esse problema se vale de um fato bastante simples de ser notado. O caminho vermelho está associado à palavra DADADDDA. Ele fica associado de maneira única ao subconjunto {2,4,8} de {1, 2, 3, 4, 5, 6, 7, 8}, sendo 2 a posição do primeiro passo vertical na palavra, 4 a posição do segundo e 8 a posição do terceiro. De forma recíproca, dado um subconjunto de {1, 2, 3, 4, 5, 6, 7, 8} com três elementos, podemos associá-lo a uma palavra da maneira descrita acima. Assim, a quantidade de escadarias ligando os pontos P e Q será igual ao número de subconjuntos com três elementos de {1, 2, 3, 4, 5, 6, 7, 8}, que é igual a:
CAMINHOS DE DYCK Trataremos agora de um problema semelhante ao anterior, mas cuja solução é mais engenhosa. Considere agora um trecho de quarteirão onde temos o mesmo número de ruas horizontais e verticais, ou, em outras palavras, os pontos P e Q estão em vértices opostos de um quadrado. Utilizando o mesmo tipo de movimento, gostaríamos de determinar a quantidade de caminhos possíveis para irmos do ponto P ao ponto Q, tais que, em nenhum momento, estejamos acima da diagonal mostrada na figura 3.
Caminhos desse tipo (na realidade uma categoria um pouco maior que essa) são chamados de Caminhos de Dyck (Dyck Paths), em homenagem ao matemático Walther Franz Anton von Dyck (1856-1934). Daremos duas abordagens para resolver esse problema. Uma delas se baseia em um argumento geométrico de reflexão devido ao matemático francês Desiré Andre (1840-1918). A outra vai se basear numa contagem de sequências de +1 e −1, que desaguará nos chamados Números de Catalan. O número de caminhos sem pontos acima da diagonal é igual ao número total de caminhos menos o número de caminhos com pontos acima da diagonal. Vamos chamar os caminhos sem pontos acima da diagonal de caminhos bons e os demais de maus. Observe que um caminho bom sempre começa com um D e termina com um A. Estamos tacitamente usando uma identificação entre caminhos e palavras, como fizemos anteriormente. Na figura 4, temos um exemplo de um caminho mau.
Notemos que, nesse caminho, existe um primeiro ponto, C, em que ele está acima da diagonal. Podem existir outros, mas na argumentação que se segue, o primeiro deles desempenhará um papel importante. Consideremos a reta r paralela à diagonal que passa pelo ponto C, conforme a figura 5.
Agora façamos a reflexão em torno da reta r da parte do caminho mau desde o ponto P até o ponto C. Vamos juntar essa nova parte com o restante do caminho mau anterior, unindo suas extremidades. Com essa construção, obtemos um novo caminho, formado pela parte pontilhada e o restante do caminho mau, conforme a figura 6 a seguir.
Esse novo caminho é uma escadaria que liga o ponto P' ao ponto Q. Reciprocamente, toda escadaria que ligue o ponto P' ao ponto Q pode ser associada a um caminho mau que liga os pontos P e Q. Na realidade, essa correspondência é uma bijeção, como se pode ver. Como o número total de caminhos é dado por OUTRA FORMA DE CONTAR A próxima abordagem do problema de determinar o número de Caminhos de Dyck tem um caráter mais algébrico. Consideremos as sequências a1, a2, a3, a4, a5, a6 com apenas os números +1 (três vezes) e −1 (três vezes) como termos e cuja soma de quaisquer primeiros termos (1≤ k ≤6) é não negativa (maior que ou igual a zero). Vamos determinar a quantidade dessas sequências. O argumento lembra o anterior, inclusive com uma nomenclatura meio maniqueísta! Vamos chamar de sequência boa aquela cuja soma de quaisquer k primeiros termos (1≤ k ≤6) é não negativa e a sequência será má, caso contrário. O que queremos encontrar é o número de sequências boas. O número total de sequências com seis termos, cada um deles sendo +1 (três vezes) ou −1 (três vezes), é dado pela permutação de 6 objetos, sendo que três (os três +1) e três (os três −1) podem se repetir. Agora vamos tomar uma sequência má. Sendo má, existe um k, (1≤ k ≤6) tal que a1+…+ ak < 0. Escolhamos, de todos os k para os quais isso acontece, o menor de todos. Para essa escolha, existe a mesma quantidade de +1 e de −1 distribuídos entre a1,…, ak−1. Em vista disso, a1+…+ ak−1= 0 e ak = −1. Uma particularidade desses fatos é que k é um número ímpar. Agora transformaremos essa sequência má em outra simplesmente trocando os sinais dos seus k primeiros termos e deixando o sinal dos demais fixo. Fazendo isso, teremos uma sequência de +1 e −1, com os +1 aparecendo quatro vezes e os −1 aparecendo duas vezes, isso porque mudamos o sinal de um dos −1 e as demais mudanças nada alteram. Esse processo é recíproco: se tomarmos uma sequência com quatro termos iguais a +1 e dois termos iguais a −1, podemos transformá-la numa sequência má. Basta localizar o ponto onde temos mais +1 do que −1 e inverter, até esse ponto, os sinais. Essa sequência obtida é má. Portanto, existe uma bijeção entre o conjunto das sequências más e o conjunto das sequências com quatro termos iguais a +1 e dois termos iguais a −1. O número desse último tipo de sequência é igual ao número de permutações de 6 elementos com um deles se repetindo quatro vezes e o outro duas vezes. Portanto, o número de sequências más é Como existem Na verdade, as duas formas de contagem aqui apresentadas são equivalentes: efetuar a troca de sinais nos primeiros k termos da sequência (onde k é o menor valor para o qual a1+…+ ak < 0) corresponde a refletir a porção do caminho que vai de P ao primeiro ponto visitado acima da diagonal. OS NÚMEROS DE CATALAN Tudo o que foi feito até aqui com valores particulares
pode também ser feito de uma maneira geral
para n ∈ ℕ . Por exemplo, no caso do número de
Caminhos de Dyck, poderíamos ter n ruas horizontais
e verticais. Os pontos P, Q e P' estariam
nas posições (1, 1), (n + 1, n + 1) e (0, 2), respectivamente. O número total de caminhos seria
que é conhecido como o n-ésimo Número de Catalan, em homenagem ao matemático belga Eugéne Charles Catalan (1814-1894). Esses números têm uma ubiquidade impressionante dentro da Combinatória. Para se ter uma ideia desse fenômeno, consulte [2] ou [4]. EPÍLOGO O que fizemos foi contar o início de uma história com vários desdobramentos possíveis, vários deles chegando à pesquisa de ponta em Matemática. O nosso maior interesse, entretanto, foi mostrar ao professor do ensino básico, curioso para incrementar suas aulas de Combinatória, um tema interessante e profundo, que possui interações com diversas outras partes da Matemática. Além disso, um tema altamente desafiador e propício a atividades investigativas em sala de aula, dando oportunidade ao estudante de fazer conjecturas e até mesmo provar resultados.
BIBLIOGRAFIA [1] BRUALDI, Richard A. Introductory combinatorics. 5. ed. Upper Saddle River, Pearson Prentice Hall, 2010. [2] GRIMALDI, Ralph P. Fibonacci and Catalan numbers: an introduction. Hoboken, John Wiley& Sons, Inc., 2012. [3] GRIMALDI, Ralph P. Discrete and Combinatorial Mathematics. 5. ed. Cloth, Pearson, 2004. [4] KOSHY, Thomas. Catalan numbers with applications. Oxford, Oxford University Press, 2009.
|
.
, segue que o número total de caminhos
.
sequências, o número de sequências boas é 20 − 15 = 5. Portanto, há 5 Caminhos de Dyck.
já que há n ruas verticais e n horizontais entre P e
Q) e o número de caminhos maus seria 
(já que há n + 1 ruas verticais e n − 1 horizontais
entre P' e Q). Portanto, o número de caminhos
bons seria
