O Uso de Funções Geradoras no Ensino Médio para Articular Conteúdos Variados em Análise Combinatória

UNIVERSIDADE FEDERAL DA GRANDE DOURADOS – UFGD FACULDADE DE CIÊNCIAS EXATAS E TECNOLÓGICAS – FACET DIONISIO NOGUEIRA NETO O USO DE FUNÇÕES GERADORAS NO ENSINO MÉDIO PARA ARTICULAR CONTÉUDOS VARIADOS EM ANÁLISE COMBINATÓRIA DISSERTAÇÃO DE MESTRADO PROFISSIONAL EM MATEMÁTICA DOURADOS – MS ABRIL – 2014 DIONISIO NOGUEIRA NETO O USO DE FUNÇÕES GERADORAS NO ENSINO MÉDIO PARA ARTICULAR CONTEÚDOS VARIADOS EM ANÁLISE COMBINATÓRIA ORIENTADOR: PROF. DR. SÉRGIO RODRIGUES Dissertação apresentada ao final do Programa de Mestrado Profissional em Matemática em Rede Nacional – PROFMAT da Universidade Federal da Grande Dourados (UFGD) como exigência parcial para obtenção do título de Mestre em Matemática DOURADOS – MS ABRIL – 2014 Dedico este trabalho a Deus, a minha família, minha esposa Jucyelly que carrega consigo um filho meu (Daniel) e ao amigo e professor Sergio Rodrigues. AGRADECIMENTOS À Deus, pelo dom da vida, pelo dom de aprender e educar, pela alegria de viver, sonhar e realizar. À minha esposa Jucyelly, pela compreensão e paciência, por acreditar, incentivar e apoiar nos vários momentos de angustia. À minha mãe, pelo amor, educação e por me fazer acreditar que tudo é possível. Aos meus irmãos, Junior, Gerson e Grace, que sempre torceram e nunca deixaram de acreditar em mim. Aos amigos que muito me apoiaram e me incentivaram, em especial, o Elton e o Roque, pela ajuda constante. Ao meu orientador Professor Doutor Sérgio Rodrigues que, com seu companheirismo, orientação e paciência, me conduziu para elaboração deste trabalho. Aos meus colegas de trabalho que acompanharam esta luta apoiando e incentivando. Às diretoras Tânia, Adélia e Helsney e ao diretor Alcides das escolas em que trabalho, que sempre me deram condições e incentivo para cursar este caminho. Aos meus amigos e irmãos da Sexta Igreja Presbiteriana Filadélfia, pelas orações e incentivo. À CAPES pelo apoio financeiro. É possível reconhecer a utilidade de uma idéia sem, contudo, compreender como usá-la adequadamente. Johann Wolfgang Goethe (1749 – 1832), poeta, romancista e teatrólogo alemão. RESUMO Considerando que as técnicas de contagem é um assunto difícil de ser absorvido pelos alunos, este trabalho tem como objetivo apresentar uma proposta de ensino de combinatória para os professores do Ensino Médio na qual farão uso de funções geradoras para solucionar alguns problemas de combinatória e articular outros conceitos ao tema, além de expandir seus conhecimentos com outros métodos de contagem. Palavras-chave: Análise Combinatória. Ensino Médio. Funções Geradoras. ABSTRACT Considering that techniques of counting is a difficult subject to be absorbed by the students, this work aims to present a proposal for teaching combinatorics for the teachers high school in which shall use generating functions to solve some problems of combinatorics and to articulate other concepts to the theme, expanding the knowledge with other methods for counting. Keywords: Combinatorial Analysis, High School, Generating Functions. SUMÁRIO INTRODUÇÃO 11 1. PANORAMA DO ENSINO DE COMBINATÓRIA NO ENSINO MEDIO 14 2. ANÁLISE COMBINATÓRIA: CONCEITOS 17 2.1. PRINCÍPIO MULTIPLICATIVO 17 2.2. FATORIAL 18 2.3. PERMUTAÇÃO SIMPLES 18 2.4. ARRANJO SIMPLES 19 2.5. COMBINAÇÃO SIMPLES 20 2.6. PERMUTAÇÃO COM ELEMENTOS REPETIDOS 20 2.7. ARRANJO COM REPETIÇÃO 21 2.8. COMBINAÇÃO COM REPETIÇÃO 21 2.9. COEFICIENTES BINOMIAIS 23 2.9.1. Propriedades dos Coeficientes Binomiais 24 2.10. BINÔMIO DE NEWTON 25 2.11. POLINÔMIOS E SÉRIES DE POTÊNCIAS 27 2.12. POLINÔMIOS DE VÁRIAS VARIÁVEIS 29 2.13. FUNÇÕES GERADORAS 30 2.14. RELAÇÃO DE RECORRÊNCIA 33 3. APLICANDO FUNÇÕES GERADORAS NO ENSINO MÉDIO 36 3.1. PROBLEMA 1 37 3.2. PROBLEMA 2 41 3.3. PROBLEMA 3 42 3.4. PROBLEMA 4 44 4. CONCLUSÃO 48 5. REFERÊNCIAS 49 11 INTRODUÇÃO Este trabalho tem por objetivo ampliar o conhecimento do professor do Ensino Médio para trabalhar o conteúdo de análise combinatória juntamente com o conceito de funções geradoras que, em geral, não faz parte dos currículos dos cursos de licenciatura em matemática. As funções geradoras são de grande importância nas técnicas de contagem. Um tipo de função geradora que abordaremos neste trabalho é dada por polinômios p( x)  an xn  an1xn1  ...  a1x  a0 no qual os coeficientes são números inteiros e o coeficiente de uma potência específica é a resposta da contagem de um problema que queremos resolver. Por exemplo o polinômio dado por (1  x)6  1  C61 x  C62 x2  C63 x3  C64 x4  C65 x5  x6 é tal que o coeficiente de x3 corresponde á combinação de 6 elementos tomados 3 a 3 . As funções geradoras que usaremos neste trabalho utilizam os polinômios dados pelo binômio de Newton para obter outros polinômios cujos coeficientes são as respostas para os nossos problemas de contagem. Desta maneira estamos integrando os conceitos de polinômios e de combinatória. As funções geradoras mais gerais são dadas por séries de potências S ( x)  a0  a1x  ...  an xn  .... com coeficientes inteiros, que podem ser pensadas como uma generalização dos polinômios, cujos coeficientes são as respostas procuradas para os problemas de contagem. Isto pode parecer que estamos fugindo dos conteúdos do Ensino Médio. Lembramos que nos textos do Ensino Médio (PAIVA, 1995) os estudantes entram em contato com a série de potências dada pela soma infinita dos termos de uma Progressão Geométrica de termo inicial 1 e razão x é tal que se | x | 1 então 1  x  x 2  ...  x n  ...  1 e esta função também é um 1 x exemplo de função geradora que usaremos. Neste trabalho mostraremos exemplos como utilizar os polinômios de mais de uma variável para descrever ou modelar problemas de contagem de tal modo que cada termo deste polinômio corresponda a uma disposição exata de todos elementos da combinatória que queremos resolver e, a partir deste polinômio, obteremos a função geradora que “conta” quantos elementos existem na configuração que estamos estudando. A este processo vamos chamar aqui de 12 mapeamento do problema combinatório. Para o leitor ter uma ideia do que estamos propondo, considere o polinômio de 6 variáveis dado por f ( x1, x2 , x3 , x4 , x5 , x6 )  (1  x1 )(1  x2 )(1  x3 )(1  x4 )(1  x5 )(1  x6 )  P0  P1  P2  P3  P4  P5  P6 Este polinômio tem 26  256 termos e em cada termo cada uma das indeterminadas aparece uma única vez e o coeficiente de todos os termos é igual a 1 . Vamos reagrupar os termos segundo o número de indeterminadas, isto é, denotar por Pk , 0  k  6 a soma de todos os monômios com k variáveis. Por exemplo, P5  x2 x3 x4 x5 x6  x1x3 x4 x5 x6  x1x2 x4 x5 x6  x1x2 x3 x5 x6  x1x2 x3 x4 x6  x1x2 x3 x4 x5 Note que em P5 cada termo deste polinômio corresponde a uma combinação de 6 elementos {x1 , x2 , x3 , x4 , x5 , x6} tomados 5 a 5 e todas as combinações destes 6 elementos 5 a 5 estão representadas uma única vez em uma parcela. Deste modo o polinômio f ( x1 , x2 , x3 , x4 , x5 , x6 ) modela o problema de todas as combinações possíveis que podemos obter com 6 elementos que forma um total de 26  256 combinações. Substituindo cada uma das variáveis por uma única variável, isto é, se x1  x2  x3 ,  x4  x5  x6  x então obtemos a função geradora p( x)  (1  x)6  1  C61 x  C62 x2  C63 x3  C64 x4  C65 x5  x6 cujos coeficientes de grau 0  k  6 contam todas as combinações possíveis de 6 elementos tomados k a k . Aparentemente pode-se pensar que estamos complicando o problema, mas esta técnica é bastante útil em outras situações mais complexas como analisaremos a seguir. Inicialmente faremos uma prévia da problemática do ensino de Análise Combinatória no Ensino Médio, buscando opções, e tentando visualizar meios para aprimorar o ensino deste tema, depois apresentaremos os conceitos básicos para os professores do Ensino Médio que serão usados para o professor trabalhar Análise Combinatória utilizando as funções geradoras. Fica como opção também trabalhar as funções geradoras dessa forma no ensino superior, na qual os alunos estarão revendo conceitos e aumentando seu raciocínio determinando outros meios de solucionar problemas. Ao final apresentaremos quatro problemas que podem ser trabalhados em 13 sala de aula como atividade de aperfeiçoamento do conteúdo de combinatória. Esses problemas são, ao mesmo tempo, sugestões para o professor de como fazer a aplicação das funções geradoras articulando o estudo da combinatória com o binômio de Newton e os polinômios e, deste modo, enriquecendo o conhecimento do aluno. 14 Capitulo 1 PANORAMA DO ENSINO DE COMBINATÓRIA NO ENSINO MÉDIO A análise combinatória é um ramo da Matemática que tem por objetivo resolver problemas que consistem, basicamente, em escolher, agrupar e contar os elementos de um conjunto e que possui aplicação direta no cálculo das probabilidades, sendo portanto, um instrumento de vital importância para as ciências aplicadas, como a Medicina, a Engenharia e a Estatística, entre outras. Segundo Sabo (2010), alguns professores evitam, ou não abordam no Ensino Médio o conceito de análise combinatória por considerarem um tema árduo para ensinar. Eles afirmam que a má estruturação do Ensino Fundamental não proporciona aos alunos habilidades para trabalhar conceitos tão sofisticados, acusam também o tempo insuficiente em sala de aula e até mesmo que eles próprios não entendem o assunto e acabam optando por outros conteúdos considerados importantes deixando então de lado este conceito. Sobre isso Sabo (2010) menciona: Um dos fatores responsáveis pela má qualidade de ensino é, sem dúvida alguma, a formação do professor. E possível dizer que a maioria dos profissionais que se formaram ou estão se formando, não tem claro o papel da escola, os objetivos da aprendizagem, a razão dos conteúdos a serem trabalhados, enfim, não tem claro o seu próprio papel de educador. (SABO, 2010, p. 14 apud LOPES, 2000, p. 12) De fato, podemos dizer que em muitos casos o professor, desde sua formação, não recebeu fundamentos matemáticos necessários para trabalhar tal assunto. O que contribui também é a questão social do professor, o meio em que vive, suas necessidades e os recursos que possui para aumentar sua capacitação. Dessa forma entendemos que os saberes do professor estão atrelados às condições sociais e de trabalho por ele vividas, como também pela sua personalidade e experiência profissional, ou seja, esses saberes estão assentados entre o que o professor é e o que ele faz e, desse modo, situam-se entre o individual e o social. (SABO, 2010, p. 34) Existe também o fato de que muitos professores possuem certa facilidade para acomodação, apóiam-se em seus livros didáticos e não buscam outros meios de se ensinar um assunto considerado difícil ou que não está no seu conhecimento. Por sua vez, os livros didáticos trazem os conteúdos de forma sucinta e, na maioria das vezes, como um pacote fechado para ser aplicado em determinada série, 15 havendo assim uma dificuldade para intercalar outros conteúdos. Um dos fatores que pode contribuir e favorecer que os professores não abordarem determinados conceitos matemáticos é a segmentação do conhecimento matemático. Cada conceito é tratado de forma pontual em uma determinada série do Ensino Médio, desta forma, não há interação entre os conhecimentos ensinados. (SABO, 2007, p. 8) No Ensino Fundamental o tema da combinatória é pouco abordado. Os livros didáticos abordam sobre o Princípio Aditivo e Multiplicativo e ainda assim resumidamente. A aplicação constante do conteúdo depende definitivamente do professor, que como já vimos, muitas vezes não o faz. O que podemos dizer é que nos tempos de hoje, com os computadores, internet, celulares avançados e os vários meios de comunicação o professor tem subsídios de busca e capacitação “[...] ele precisa assumir o papel de agente participativo e protagonista no processo de seu desenvolvimento profissional”. (SABO, 2010, p. 34). Ele pode deixar de se apoiar somente nos livros didáticos e pleitear formações continuadas, e outros recursos que abordem este e outros temas que cujo ensino deixam a desejar. Quanto aos livros didáticos, uma solução possível seria intercalar conteúdos de técnicas de contagem desde o primeiro ano do Ensino Médio, buscando novas possibilidades de resolução e de interação destes conceitos. A grande maioria dos livros didáticos do Ensino Médio segue o padrão de “encaixotamento” dos conceitos matemáticos, ou seja, cada conceito matemático é abordado pontualmente em uma determinada série, desta forma, não há interação entre os conhecimentos matemáticos ensinados. (SABO, 2007, p. 20) Também seria necessário fazer uma modificação nas técnicas abordadas, pois a maioria dos livros traz muitos exercícios que alteram apenas o enunciado, e o aluno, por sua vez, aplica a resolução de forma mecânica, não entendendo o procedimento. Este pensamento nos fez acreditar que este trabalho pode ser de grande serventia, pois damos ao professor sugestões de como trabalhar novos conceitos e revisando conteúdos que já foram transmitidos, reforçando assim o que foi ensinado. A pergunta que pode surgir: Por que utilizar o conceito de funções geradoras no Ensino Médio? Em primeiro lugar podemos responder que, deste modo, apresentaremos aos alunos do Ensino Médio problemas de contagem que não se enquadram na classificação usual de arranjo, permutação e combinação e isto pode 16 ser estimulante para os alunos e para que os professores repensem seus conceitos e métodos de ensino. Por exemplo, considere o seguinte problema que abordaremos aqui: “Um professor de Educação Física quer montar um time misto com 7 jogadores. Quantas soluções são possíveis de forma que tenha no máximo 5 meninos ou 5 meninas?” Problemas deste tipo recaem em procedimentos matemáticos que não estão previstos nos textos do Ensino Médio. Outro modo de justificar o uso de funções geradoras ordinárias é que este tópico utiliza os conceitos do binômio de Newton e de polinômios e, deste modo, estaremos integrando o ensino dos tópicos de matemática do Ensino Médio de um modo útil e inovador. Além de que, por meio das funções geradoras podemos enumerar possibilidades combinatórias de um problema de forma mais concreta e certeira. Em nossa pesquisa bibliográfica não encontramos propostas de metodologias de ensino que utilizem as funções geradoras no Ensino Médio sendo que estas constituem um tópico importante da matemática discreta e que é tema de pesquisa avançada atualmente. Nos livros, Matemática Concreta (KNUTH,1995) e Introdução à análise combinatória (SANTOS,1998) e mais recentemente como dissertação do PROFMAT (GARCIA, 2013), podemos ter contato com a importância e abrangência do assunto. 17 Capítulo 2 ANÁLISE COMBINATÓRIA: CONCEITOS Apresentaremos aqui, os conceitos e fórmulas da análise combinatória de maneira resumida, simples para consulta sendo que os detalhes poderão ser vistos em (SANTOS, 2007), (KNUTH, 1995), (IEZZI, 2010), (BARRETO, 2003) e (GARCIA, 2013). Entretanto, teremos um pouco mais de cuidado com os conceitos de polinômios e sua relação com as séries de potências e funções geradoras, pois, é através destes conceitos que faremos a integração e articulação de conhecimentos múltiplos. 2.1 Princípio Multiplicativo O princípio multiplicativo da contagem diz que um acontecimento ocorre em duas situações sucessivas e independentes, sendo que se a 1ª situação ocorre de a maneiras e a 2ª situação ocorre de b maneiras, então o número total de possibilidades de ocorrência desse acontecimento é dado pelo produto a  b . Suponha que uma seqüência seja formada por k elementos (a1 , a2 , a3 ,..., ak ) , em que:  a1 pode ser escolhido de n1 maneiras distintas;  a2 pode ser escolhido de n2 formas diferentes, a partir de cada uma das possibilidades anteriores;  a3 pode ser escolhido de n3 modos diferentes, a partir de cada uma das escolhas anteriores;  ak pode ser escolhido de nk maneiras distintas, a partir das escolhas anteriores; Então, o número de possibilidades para construir a sequência (a1 , a2 , a3 ,..., ak ) é: n1  n2  n3  ...  nk 18 Esse resultado é conhecido como uma extensão do Princípio Multiplicativo (SANTOS, 2007) e serve de base para a resolução de muitos problemas de contagem. Exemplo: (GARCIA, 2013, p.17) Podemos aplicar este princípio para contar os subconjuntos de um conjunto finito C sem usar a soma das combinações do seguinte modo: Seja o conjunto C  {x1 , x2 ,..., xn } com n elementos. Se S é um subconjunto de C podemos descrever S como uma sequência s  (a1, a2 , a3 , ..., ak ) na qual ai  1 se ai  S e ai  0 se ai  S . Por exemplo, o subconjunto S  {x1, x2} corresponde á sequência s  (1, 1, 0, ..., 0) . Como temos duas possibilidades, 0 ou 1, para cada posição e as n posições são independentes então teremos um total de 2n possibilidades o que corresponde a um 2n subconjuntos. 2.2 Fatorial Dado um número natural n , definimos o fatorial de n (indicado por n ! ) como:  n!  n .(n  1).(n  2)..3.2.1 para n  1  Se n  1 , 1!  1  Se n  0 , 0!  1 Por exemplo: 2! 2.1  2 4!  4.3.2.1  24 3!  3.2.1  6 5!  5.4.3.2.1  120 No final deste capítulo discutiremos como dar uma definição recursiva de fatorial. 2.3 Permutação Simples Dado um conjunto com n elementos S  {a1 , a2 , a3 , ..., an } então o conjunto P de todas as n-uplas ordenadas ou sequências ( x1 , x2 , x3 , ..., xn ) dos elementos de S é chamado do conjunto das permutações simples de S . P  {( x1, x2 , x3 , ..., xn ) : xi  S e xi  x j se i  j} Se denominarmos Pn o número das permutações simples dos n objetos, então: 19 Pn  n(n 1)(n  2) 1  n! P0  0!  1 . Vamos definir Um modo de se usar o princípio multiplicativo para justificar que o fatorial de n dá o número de permutações possíveis dos elementos distintos da n-upla (a1 , a2 , a3 , ..., ak ) , é que se temos n escolhas para primeira posição temos (n  1) escolhas para a segunda posição e (n  2) escolhas para a terceira posição e assim por diante restando apenas uma escolha para a última posição. 2.4 Arranjos Simples Arranjos simples de n elementos tomados p a p , onde n  1 e p é um número natural tal que p  n , são todos os grupos de p elementos distintos que diferem entre si pela ordem e pela natureza dos elementos que compõem cada grupo. Notação Anp . (SANTOS, 2007, p. 57) Usando o princípio multiplicativo vamos encontrar uma expressão matemática que caracterize Anp . Se S  {a1 , a2 , a3 , ..., an } são os elementos do conjunto então se 0  p  n , temos n possibilidades de se colocar um elemento de S na posição de x1 em ( x1, x2 , x3 , ..., x p ) e n  1 possibilidades de se colocar um elemento de S na posição de x2 sem repetir e, assim sucessivamente, temos n  ( p  1) possibilidades na posição xp . Pelo princípio multiplicativo temos então um total de n  (n  1)  (n  2)  (n  3) ... (n  ( p  1)) possibilidades no total. Portanto Anp  n  n  1 n  2    n   p  1  . Sabemos que não se altera uma igualdade se a multiplicarmos e dividirmos por um mesmo valor então: Anp  n  (n  1)  (n  2) ... (n  ( p  1))  Isto é, a fórmula de arranjo pode ser simplificada como Anp  n! . (n  p)! (n  p)! . (n  p)! 20 2.5 Combinação Simples Chamam-se combinação simples de n elementos tomados p a p , onde n  1 e p é um número natural tal que n  p , todas as escolhas não ordenadas de p n desses n elementos. Notação: Cnp    (lê-se: combinação de n p a p ). Se  p p  n , p , n inteiros, define-se Cnp  0 .(SANTOS, 2007, p. 62) Vimos que o número de arranjos simples de n elementos tomados p a p é igual ao número de maneiras de preencher p lugares com n elementos distintos disponíveis. Obtivemos: Anp  n! (n  p)! que é o número de agrupamentos que diferem entre si pela natureza e pela ordem de colocação de seus elementos no agrupamento, isto é, quem participa e o lugar que ocupa. Quando consideramos combinações simples de n elementos tomados p a p , temos agrupamentos de p elementos tomados entre os n disponíveis, que diferem entre si apenas pela sua natureza, ou seja, só importa quem participa do grupo. Neste caso, a combinação simples dos n elementos tomados p a p é dado pelo arranjo simples dos n elementos tomados p a p dividido por p ! , que é o número de permutações dos elementos que compõem cada arranjo, isto é, Cnp  n! . (SANTOS, 2007, p. 62) p !(n  p )! 2.6 Permutação com Elementos Repetidos Dada uma n-upla (a1, a2 , a3 , ..., an ) com n elementos, vamos supor que existem n1 elementos iguais a a1 , n2 elementos iguais a a2 , ∙∙∙, e nr elementos iguais a ar . Neste caso o conjunto das permutações dos elementos da n-upla é chamado de conjunto das permutações com repetição. Segue que o número de permutações distintas que se pode obter com os elementos é: ( n1 , n2 ,..., nr ) Pn  n! n1 !n2 !... nr ! 21 2.7 Arranjo com Repetição Lembrando que, (...) o número de arranjos simples de n elementos tomados p a p é dado por: Anp  n  (n 1)  (n  2) ... (n  p  1) . Este número conta todas as possíveis maneiras de se retirar, de um conjunto de n elementos distintos, p elementos, levando-se em conta a ordem dos elementos. Caso repetições sejam permitidas, pelo princípio multiplicativo, o número total de maneiras de se retirar, levando-se em conta a ordem, p dos n objetos, distintos ou não, é igual a ARnp  n p uma vez que o primeiro elemento pode ser retirado de n maneiras, o segundo também de n maneiras e assim sucessivamente até que o p-ésimo elemento seja escolhido.” (SANTOS, 2007) Podemos acrescentar que o modelo dos arranjos com repetição dos n elementos de um conjunto S  {a1 , a2 , a3 , ..., an } p a p é dado por todas as p-uplas ( x1, x2 , x3 , ..., x p ) em que xi é um elemento qualquer de S , isto é, ( x1 , x2 , x3 , ..., x p )  S  S ....  S p vezes 2.8 Combinações com Repetição O livro de Santos (2007) descreve as combinações com repetição do seguinte modo: “Suponhamos que num parque de diversões existam quatro tipos de brinquedos a , b , c e d , e que uma pessoa queira comprar dois bilhetes. É claro que ela poderá comprar dois bilhetes do mesmo tipo. Na tabela abaixo temos a lista de todas as possibilidades que, como vemos, é igual a dez. aa bb cc ab ac ad bc bd cd dd 22 Observe que este número é maior do que C42  6 , pois quando estamos considerando as combinações simples de 4 tomados 2 a 2 , não podemos tomar um mesmo objeto mais de uma vez. Dizemos ser a tabela acima a lista das combinações com repetição de 4 tomados 2 a 2 . Vamos supor que ela resolva comprar 5 bilhetes para estes 4 brinquedos. Algumas possibilidades seriam: aaaaa abbbc aacbb bbccd Estamos interessados em contar o total de elementos do tipo acima. Para sabermos quais foram os 5 bilhetes comprados, basta que a pessoa nos diga quantos bilhetes de cada tipo comprou. Se chamarmos de x1 o número de bilhetes para o brinquedo a , de x2 o número para b , de x3 para c e de x4 o número para o brinquedo d , o que estamos procurando é, nada mais nada menos, do que o número de soluções inteiras não negativas para a equação x1  x2  x3  x4  5 ” (SANTOS, 2007) Para concluir o exemplo vamos provar o seguinte resultado Proposição : Se m um inteiro positivo então a) o número de soluções inteiras e positivas de x1  x2  ...  xr  m é Cmr 11 . b) o número de soluções inteiras e não negativas de x1  x2  ...  xr  m é Cmr 1r 1 . Demonstração: a) Considere m símbolos do número “1 ” alinhados consecutivamente. Podemos representar todas as soluções positivas da equação dada reagrupando os números 1 ’s. Por exemplo a solução x1  3; x2  1; x3  3,...; xr 1  1; xr  4 pode ser representada por 3  1  3  ....  1  4  r ou 111  1  111  ....  1  1111  r Como temos (m  1) espaços entre os 1 ’s então cada solução distinta ( x1, x2 ,..., xr ) desta equação pode ser representada por uma escolha de (r  1) destes 23 espaços para se colocar os sinais de “+” separando os grupos que representam as soluções e portanto temos Cmr 11 escolhas distintas. b) A cada solução positiva distinta da equação y1  y2  ... yr  m  r corresponde a uma solução não negativa distinta da equação x1  x2  ...  xr  ( y1 1)  ( y2 1)  ...  ( yr 1)  m e reciprocamente, logo o total Cmr 1r 1 soluções para x1  x2  ...  xr  m . Desta proposição segue que a solução do problema dos bilhetes corresponde à soluções não negativas da equação x1  x2  x3  x4  5 que é igual a C83  56 . De modo geral CRnp é o número total de maneiras de selecionarmos p objetos dentre n objetos distintos onde cada objeto pode ser tomado até p vezes. Como vimos este número é igual ao número de soluções inteiras não-negativas da equação x1  x2  ...  xn  p logo CRnp  Cnp p1 Santos (2007) chama a atenção para o fato de que se consideramos as combinações simples de n elementos tomados p a p então p  n . No caso de combinações com repetição esta restrição não é necessária, como vimos no exemplo da compra dos bilhetes acima. 2.9 Coeficientes Binomiais Os coeficientes binomiais podem ser usados no cálculo diferencial para a expansão de funções (1  x)r , em série de potências, conhecido como Teorema Binomial (KNUTH, 1995, p. 122). Não vamos usar este resultado mais geral pois este foge do programa do Ensino Médio, mas ele está presente quando r  1 pois os textos apresentam a soma da PG infinita S  1  x  x 2  ...  x n  ...  1 . 1 x Primeiramente vamos definir o que vem a ser um binômio, segundo Santos (2007) chamamos de binômio qualquer expressão da forma a  b , isto é, a soma de dois símbolos distintos. Definimos como coeficiente binomial o número que representa a quantidades de vezes que um termo aparece na expansão de um produto binomial, (a  b)n . 24 n Segundo Knuth (1995), “o símbolo   denota um coeficiente binomial, assim  p chamado devido a uma propriedade importante, o teorema binomial. Lemos este símbolo como “combinação de n p a p ”, o que tem sua origem na interpretação combinatória – é o número de maneiras diferentes de combinar n coisas de p em p. De acordo com Santos (2007), “(...)vamos considerar, inicialmente, o seguinte produto: (a  b)(c  d )(e  f )  ace  acf  ade  adf  bce  bcf  bde  bdf , Que consiste de oito termos, onde cada termo consiste de três letras, cada uma selecionada de um dos binômios. Pelo princípio multiplicativo, é claro que o número total de termos é 23  8 . Para o produto (a  b)(c  d )(e  f )( g  h) , temos 16  24 termos, cada um consistindo de um produto de 4 letras, cada uma delas pertencendo a um dos 4 binômios considerados. Por exemplo, acdf e adeh são alguns dos 16 termos deste último produto. No caso do produto de n binômios, temos 2n termos. Consideremos agora o produto (a  b)(a  b)(a  b)(a  b)(a  b)(a  b) . Como temos 64 maneiras de selecionarmos 6 letras, uma de cada binômio, e como todos os binômios são iguais a (a  b) , teremos termos repetidos. Por exemplo, se tomarmos a letra a nos 4 primeiros e a letra b nos 2 últimos teremos a 4b2 , que irá aparecer toda vez que a letra a for escolhida em exatamente 4 dos 6 binômios e a letra b nos 2 restantes. Como isto pode ser feito de C64 maneiras diferentes, concluímos que o termo a 4b2 irá aparecer este número de vezes, o que equivale a dizer que o coeficiente de a 4b2 é igual a C64 .”(SANTOS, 2007) 2.9.1 Propriedades dos Coeficientes Binomiais Propriedade de simetria: Se p e q são inteiros positivos ou nulos e n  p  q 25  p  q  p  q então    e neste caso dizemos que p e q são números binomiais  p   q  complementares. Relação de Stifel. Se r  n é um número inteiro positivo ou nulo então  n   n   n 1      p   p  1   p  1 Demonstração: Desenvolveremos cada um dos membros da igualdade e chegaremos a uma identidade. n! n! (n  1)!   p !(n  p)! ( p  1)!(n  p  1)! ( p  1)![(n  1)  ( p  1)]! n !( p  1)  n !(n  p) (n  1)!  ( p  1)!(n  p)! ( p  1)!(n  1  p  1)! n !( p  1  n  p) (n  1)  n !  ( p  1)!(n  p)! ( p  1)!(n  p)! (n  1)  n ! (n  1)  n !  ( p  1)!(n  p)! ( p  1)!(n  p)! 2.10 Binômio de Newton Supondo um número natural n , podemos considerar a seguinte expressão:  n  n  n  n ( x  a)n    xn a0    x n1a1    x n2a 2  ...    x0a n  0 1  2  n Com o emprego do somatório, a fórmula fica reduzida a: n n ( x  a) n     x n  p a p p 0  p  n e   xn p a p é chamado de termo geral do binômio de Newton  p Exemplos: Considerando alguns valores para n , temos: a) n  0 0 ( x  a )0    0 b) n  1 1  1 ( x  a)1    x1a 0    x0 a1  0  1 26 c) n  2  2  2  2 ( x  a)2    x 2 a0    x1a1    x0 a 2  0 1  2 d) n  3  3  3  3  3 ( x  a)3    x3a0    x2 a1    x1a 2    x0 a3  0 1  2  3 A definição de coeficiente binomial deve ser da seguinte forma (KNUTH, 1995, p.114). Se k é um número inteiro e r um número real qualquer então definimos  r (r  1)(r  2)....(r  k  1) , r  k!     k  0,  se k  0 se k  0  1 (1)(2)(3)  1 (1)(2) Por exemplo, se r  1 então    ,    1, isto é, 2! 3! 2 3  1 k    (1) para qualquer inteiro k . No caso de r não ser um inteiro positivo k   o coeficiente binomial está definido para todo número inteiro k e, neste caso, o coeficiente binomial não tem uma interpretação combinatória. A extensão do binômio de Newton para coeficientes combinatórios mais gerais é conhecida como Teorema Binomial (KNUTH, 1995, p.120) é dada pela série binomial  r ( x  a) r     x n  p a p p 0  p  No presente trabalho vamos usar este resultado apenas no caso em que r  1     1 1  (1  ( x))1     ( x) p  (1) p ( x) p  x p  1  x  x 2  ...  x p  .... 1 x p 0  p  p 0 p 0 que é conhecida como a série geométrica e, no nosso caso, ela é uma das funções geradoras definidas a seguir. Alguns textos de matemática para o Ensino Médio (PAIVA,1995, p.45) apresentam a soma infinita de uma PG de razão r com valor absoluto menor do que 1 , isto é, se r  x e se x  1 então 27 U ( x)  1  x  x 2  x3  x 4  ...  x n  ....  1 1 x No caso do uso de U ( x ) como funções geradora, não estamos interessados quanto a convergência desta série mas apenas no seu aspecto formal (como se fosse um polinômio infinito) e não como uma função na qual podemos substituir o valor de x por um número real qualquer. 2.11 Polinômios e Séries de Potências Esses conceitos, aqui, serão tratados de modo a dar subsídios para a formulação da teoria de funções geradoras (GARCIA, 2013). Definição 2.11.1: “[...]. Uma sequência de números reais é uma função a : N  R que associa a cada número natural n um número real an , chamado de n-ésimo termo da sequência. Escrevemos a  (a1, a2 , a3 , ..., an , ...) ou (an )nN , ou simplesmente (an ) , para indicar a sequência cujo n-ésimo termo é an . Observação [...]. A sequência (an ) é diferente do conjunto {a1 , a2 , ..., an , ...} de seus termos. Por exemplo, a sequência (1, 1, 1, 1, 1) não é o mesmo que o conjunto {1} ; as sequências (0, 2, 0, 2, ...) e (0, 0, 2, 0, 0, 2, ...) são diferente mas o conjunto de seus termos é o mesmo, igual a {0, 2} .” (GARCIA, 2013) Definição 2.11.2: “[...].Um polinômio de grau n é uma expressão do tipo p( x)  a0  a1x  a2 x2  a3 x3  ...  an xn , onde an , são termos da sequência (a1, a2 , a3 , ..., an ) e x uma variável.” (GARCIA, 2013) Definição 2.11.3 “[...]. Uma série de potências é uma série infinita da forma a0  a1x  a2 x2  a3 x3  ..., onde ai , para i  0, 1, 2, 3,... , são reais e x é uma variável. Desta forma um polinômio de grau n em x é um caso particular de uma série de potências. De fato, 28 p( x)  a0  a1 x  a2 x 2  a3 x 3  ...  an x n  a0  a1 x  a2 x 2  a3 x 3  ...  an x n  0 x n 1  0 x n  2  ...    an x n n 0 Quando tivermos interessados em identificar apenas os coeficientes a0 , a1 , a2 ,..., an ,... , da série de potências a0  a1x  a2 x2  a3 x3  ..., os termos x0  1, x1 , x2 ,..., xn ,... serão meros símbolos algébricos. Nesse caso, a série de potências é chamada formal.” (GARCIA, 2013) Definição 2.11.4: “[...]. Se a0  a1x  a2 x2  a3 x3  ... e b0  b1x  b2 x2  b3 x3  ... são duas séries de potências, então a soma destas duas séries é a série de potências na qual o coeficiente de x n é an  bn e o produto destas duas séries é a série de potências na qual o coeficiente de xn é a0bn  a1bn1  a2bn2  ...  anb0 .” (GARCIA, 2013). Como no caso dos polinômios, vamos usar aqui a propriedade de que duas séries de potências são iguais se, e somente se, todos os coeficientes de mesmo grau são iguais, isto é, dadas as séries S ( x)  a0  a1x  a2 x2  a3 x3  a4 x4  ...  an xn  .... e T ( x)  b0  b1x  b2 x2  b3 x3  b4 x4  ...  bn xn  .... então: T ( x)  S ( x) se, e só se, ak  bk para todo k  0, 1, 2, ... . Vamos usar este resultado no caso da série geométrica, U ( x)  1  x  x 2  x3  x 4  ...  x n  ....  1 1 x O professor pode escolher em usar a função U ( x ) como soma de uma PG ou simplesmente fazer uma soma e multiplicação formal das séries de potências. Como xU ( x)  x  x2  x3  x4  ...  xn  ... então: 29 (1  x)U ( x)  (1  x)(1  x  x2  ...  xn )  1  0x  0x2  ...  0xn  ... Se S ( x)  a0  a1x  a2 x2  a3 x3  a4 x4  ...  an xn  .... é uma série de potências e se S ( x)  a0  a1x  a2 x2  a3 x3  a4 x4  ...  an xn  ....  (1 x)U ( x)  1  0x  ...  0x n então a0  1, a1  0, a2  0, ..., an  0,... 2.12 Polinômios de várias variáveis O conceito de polinômio de várias variáveis não é um conteúdo do Ensino Médio, mas julgamos que sua assimilação é bastante natural para os alunos que já estudaram grau de um monômio no Ensino Fundamental. Usaremos os polinômios de várias variáveis para representar de forma fiel as possibilidades combinatórias entre os objetos de um problema. Um polinômio de duas ou mais variáveis com coeficientes reais é dado por uma soma finita P  P( x1 , x2 ,..., xn )   0 jk  N ai1 ...in x1 j1 x2 j2 ...xn jn Segundo (MONTEIRO, 1969, p.318) ai1 ...in são os coeficientes, que no nosso caso podem ser reais ou inteiros, x1 , x2 , ..., xn são as indeterminadas e j1 , j2 , ..., jn inteiros positivos ou nulos são os expoentes das indeterminadas e a expressão x1 j1 x2 j2 ...xn jn é chamada de monômio. Esta definição estende a definição de polinômio de uma variável. Cada parcela da soma do polinômio ai1...in x1 j1 x2 j2 ...xn jn é chamada de termo do polinômio e dizemos que o grau de ai1...in x1 j1 x2 j2 ...xn jn é q (MONTEIRO, 1969, p.319) onde a soma j1  j2  ...  jn  q . O grau do polinômio P é definido como o maior grau de seus temos. Por exemplo P( x1, x2 )  3x1x2  x13  x2 1 é um polinômio de duas variáveis com coeficientes inteiros. Pela definição acima o grau de 3x1 x2 é dois, o grau de x13 é três, o grau de x2 é um e o grau de 1 é zero. Portanto o grau de P( x1 , x2 ) é três. Como no polinômio de uma variável, no conjunto de polinômios de várias 30 variáveis estão definidas as operações de adição e multiplicação. 2.13 Funções Geradoras Apresentaremos de uma forma geral o conceito de funções geradoras que são chamadas de ordinárias (SANTOS, 2007) que, no nosso ponto de vista, são as mais adequadas para serem usadas no Ensino Médio. Existem sim outros tipos de funções geradoras, as exponenciais, de Dirichlet que podem ser vistas nos textos do (KNUTH, 1995) e (SANTOS, 2007). Santos (2007) dá uma introdução de funções geradoras com os seguintes exemplos: “Suponhamos uma caixa contendo quatro bolas, sendo duas amarelas, uma branca e uma cinza. Representando, respectivamente, por a , b e c , as bolas de cor amarela, branca e cinza, vamos listar todas as possibilidades de tirarmos uma ou mais bolas desta caixa. Maneiras de tirar uma bola: a, b, c . Maneiras de tirar duas bolas: aa, ab, ac, bc . Maneiras de tirar três bolas: aab, aac, abc . Maneiras de tirar quatro bolas: aabc . Associamos o polinômio 1  ax  a 2 x 2 às bolas de cor amarela, e às de cor branca e cinza associamos, respectivamente, os polinômios 1  bx e 1  cx . Interpretamos o polinômio 1  ax  a 2 x 2 da seguinte forma: o termo ax significa que uma bola de cor amarela foi escolhida, o termo a 2 x 2 que duas foram escolhidas e o termo constante 1 ( x0 ) que nenhuma bola amarela foi escolhida. De forma análoga, interpretamos os polinômios 1  bx e 1  cx . Cada um destes polinômios controla, portanto a presença de bolas de uma determinada cor. Olhamos, agora, para o produto destes três polinômios: (1  ax  a2 x2 )(1  bx)(1  cx)   1  (a  b  c) x  (a2  ab  ac  bc) x2  (a2b  a2c  abc) x3  a2bcx4 . Como se pode observar esse produto nos fornece, diretamente a lista de possibilidades dada acima. O termo a 2 , que aparece no coeficiente de x 2 , surgiu ao tomarmos a 2 x 2 no primeiro polinômio, o termo 1 (que significa “não 31 pegar b ”) em 1  bx e o termo 1 ( que significa “não pegar c ”) em 1  cx , isto é, devemos tomar duas bolas amarelas, nenhuma bola branca e nenhuma bola cinza. O termo acx 2 , que surgiu do produto (ax)(1)(cx) , significa a retirada de uma bola amarela nenhuma branca e uma cinza. Observe que o expoente de x representa o número de bolas retiradas e o coeficiente, a lista destas possibilidades. Caso estivéssemos interessados, não na listagem das diferentes escolhas possíveis, mas somente no número de tais diferentes escolhas, bastaria tomarmos, no produto dos três polinômios, a  b  c  1 , obtendo: (1  x  x2 )(1  x)(1  x)  1  3x  4x2  3x3  1x4 O qual nos diz que existem 3 maneiras de retirarmos só uma bola, 4 de retirarmos 2 bolas, 3 de retirarmos 3 bolas, 1 de retirarmos as 4 bolas e 1 ( x0 ) de não retirarmos nenhuma bola. Dizemos que o polinômio 1  3x  4 x2  3x3  1x 4 é a função geradora ordinária para o problema apresentado, uma vez que a sequência formada pelos seus coeficientes, 1, 3, 4, 3, 1 , nos fornece as respostas para esse problema. Outro problema típico é o de encontrar o número de soluções inteiras da equação x1  x2  x3  12 , onde as variáveis x1 e x2 pertencem ao conjunto {2, 3, 4} e a variável x3 pertence ao conjunto {5, 6, 7} . Definimos três polinômios, um para cada variável xi , da seguinte forma: p1  x2  x3  x4 p2  x2  x3  x4 p3  x5  x6  x7 Observe que os expoentes em pi são os elementos do conjunto ao qual xi pertence. Como estamos procurando números cuja soma seja 12 e que estejam cada um , num conjunto cujos elementos são os expoentes dos polinômios acima, vamos considerar o produto p( x) destes três polinômios: P( x)  p1 p2 p3  ( x2  x3  x4 )( x2  x3  x4 )( x5  x6  x7 ) . Mostramos a seguir que a resposta ao nosso problema será o coeficiente de x12 na expansão do referido produto. Como este produto é 32 igual a: ( x2  x3  x4 )2 ( x5  x6  x7 )  x9  3x10  6x11  7 x12  6x13  3x14  x15 , A equação x1  x2  x3  12 possui 7 soluções inteiras com as restrições dadas. Um termo como x3 x 2 x 7 nos fornece a solução x1  3 , x2  2 e x3  7 . O termo x3 x 4 x5 nos fornece x1  4 , x2  3 e x3  5 . O que verificamos aqui é que cada solução deste problema corresponde a exatamente uma maneira de se obter x12 na expansão do produto dos polinômios em questão. Observamos que o polinômio x9  3x10  6 x11  7 x12  6 x13  3x14  x15 nos fornece também, a resposta para outros problemas. Como o coeficiente de x14 é igual a 3 , existem, com as restrições dadas, somente 3 soluções para a equação x1  x2  x3  14 . Na realidade pelas razões apresentadas acima o polinômio gera o número de soluções para todas as equações x1  x2  x3  m , para m  {9, 10, 11, 12, 13, 14, 15} , com as restrições impostas ás variáveis xi ’s. Definição (SANTOS, 2007): Se ar , para r  1, 2, 3, ... , é o número de soluções de um problema de combinatória, a função geradora ordinária para este problema é a série de potências a0  a1x  a2 x2  a3 x3  ..., ou, de maneira geral, dada a sequência (ar ) , a função geradora ordinária para está sequência é definida como a série de potências a0  a1x  a2 x2  a3 x3  ... . Chamamos atenção para o fato de que, apesar do nome, a função geradora é dada por uma série formal, isto é, esta pode não definir uma função no sentido estrito, pois a série pode resultar num número infinito se substituímos a variável x por um número real r , como no caso da série geométrica 1  x  x2  ...  x p  ... que só resulta num número bem definido se x  1. Em 2.8 provamos que o número de soluções inteiras e positivas de x1  x2  ...  xr  m é Cmr 11 . Note que este número coincide com o coeficiente de x m ( x1  x2  x3  x4  .....  x p  .....)r e o número de soluções inteiras e não negativas de 33 x1  x2  ...  xr  m é Cmr 1r 1 . e este número coincide com o coeficiente de x m de (1  x1  x2  x3  x4  .....  x p  .....)r 2.14 Relação de recorrência A relação de recorrência não é um tópico comum nos textos do Ensino Médio, portanto, o professor terá que explicar antes, com exemplos, o seu significado. A relação de recorrência é um tópico de fácil compreensão e é central nas ideias matemáticas, achamos que este tipo de solução é pertinente para o Ensino Médio, pelo menos para turmas onde se pode falar de tópicos especiais de matemática. O professor pode introduzir estas ideias definindo o fatorial como uma relação de recorrência como: Exemplo 2.14.1: “Sabendo que 1!  1 calcule 5! pela relação de recorrência n !  n(n  1)!” Pela relação de recorrência 5!  5.(4)! . Usando novamente a relação de recorrência, passo a passo, temos 4!  4.(3)! ; 3!  3.(2)!; 2!  2.(1)! e, por definição, 1!  1 logo, fazendo as substituições temos 5!  5.(4).(3).(2).(1)  120 . Outra situação que pode ser apresentada para os alunos como preparação para relações de recorrência mais complexas é apresentação da soma de uma progressão geométrica de razão r e termo inicial a0  1 como uma relação de recorrência Exemplo 2.14.2: Dada relação de recorrência S (n)  S (n 1)  r n e S (0)  1 calcular S (4) . Neste caso, podermos calcular S (4) usando a fórmula de recorrência S (4)  S (3)  r 4 , S (3)  S (2)  r 3 , S (2)  S (1)  r 2 , S (1)  S (0)  r e S (0)  1 por definição. 34 Substituindo os valores temos S (4)  1  r  r 2  r 3  r 4 No caso da soma de uma PG podemos obter uma fórmula chamada de r n 1  1 fórmula fechada para cada n dada por S (n)  , mas no caso do fatorial temos 1 r que fazer a multiplicação dos n números que é o mesmo processo de calcular o fatorial usando a relação de recorrência, isto é, multiplica-se o número n pelo fatorial do número anterior. Estes dois exemplos são importantes, pois são funções conhecidas (conceitos estudados) pelo estudante do Ensino Médio. O professor pode introduzir outro exemplo famoso da matemática que é sequência de Fibonacci. Exemplo 2.14.3: A sequência de Fibonacci que é dada por uma relação de recorrência da ordem 2 , isto é, o termo F (n) é a soma dos dois termos anteriores da sequência. F (n)  F (n  1)  F (n  2) e F (1)  1 e F (2)  1 então deste modo podemos calcular os termos sucessivos para n  2, 3, 4, ... F (3)  F (2)  F (1)  1  1  2 ; F (4)  F (3)  F (2)  2  1  3 ; F (5)  F (4)  F (3)  3  2  5 , etc. O professor poderá informar de que dada uma recorrência nem sempre é possível achar uma fórmula fechada como no caso da soma de uma PG. Mas em alguns casos podemos definir uma fórmula fechada para a sequência de Fibonacci, (KNUTH, 1995): 1  1 5  Fn    5  2  n 1 1  1 5     5  2  n 1 entretanto, a prova deste resultado não é objeto do Ensino Médio. Outra sugestão para mostrar uma relação de recorrência de segunda ordem e é conhecida dos estudantes é a relação dos coeficientes combinatórios que nos livros didáticos é chamada de relação de Stiefel com a qual podemos obter o triângulo de Pascal que também é bastante divulgado nos livros didáticos, (BARRETO, 2003), (IEZZI, 2010). 35  n1   n   n   k 1    k 1    k        Para abordar o problema 4 utilizando-se relações de recorrência o professor poderá fazer um problema análogo simplificando-o para ficar claro a forma com que se emprega a recorrência, exemplo: solução preliminar: 36 CAPITULO 3 APLICANDO FUNCÕES GERADORAS NO ENSINO MÉDIO Como já dissemos anteriormente, a solução de problemas de contagem e combinatória consiste de um dos tópicos mais problemáticos de ser ensinado no Ensino Médio. As soluções de problemas de combinatória utilizando-se funções geradoras são, em geral, estudadas na disciplina denominada Matemática Discreta do Ensino Superior, pois seu desenvolvimento geral envolve o conhecimento da expansão de funções em série de Taylor que não é assunto do Ensino Médio. Os textos destinados ao ensino do binômio de Newton no Ensino Médio utilizam a fórmula da combinação para calcular os coeficientes binomiais e esta é a única ligação apresentada entre o desenvolvimento do binômio de Newton para expoentes positivos e a combinatória. Os aspectos da formação dos coeficientes binomiais como um sistema de contagem, como é usado nas funções geradoras, como foi apresentado na introdução deste trabalho não é ressaltado no Ensino Médio. O objetivo deste capítulo é apresentar alguns problemas que podem ser apresentados no Ensino Médio e cujas soluções evidenciam a integração entre o desenvolvimento polinomial do binômio de Newton e da série geométrica como uma forma de contagem e que, poderão ser usados pelos professores no ensino regular ou como tópicos extras de matemática, também é uma boa opção para o ensino superior, para revisar conceitos e conteúdos de combinatória e soluções alternativas. Neste capítulo vamos selecionar alguns problemas de combinatória e contagem que estão presentes nos textos do Ensino Médio e vamos propor métodos de soluções que utilizam os coeficientes binomiais das funções geradoras de alguma forma. Alguns professores poderão nos fazer a crítica de que a proposta “complica a solução”, pois se pode dar a resposta de modo mais rápido seguindo os passos tradicionais. Entretanto nosso objetivo não é resolver o problema de modo mais rápido, mas sim, mostrar outros modos de raciocínios que buscam mapear um problema de contagem num problema de busca de coeficientes de polinômios (ou 37 séries de potências) de forma vantajosa, pois estes mapeamentos transformam o problema combinatório num problema algébrico de cálculo de coeficientes polinomiais. 3.1 Problema 1 O problema a seguir foi adaptado do livro (IEZZI, 1977), que traz a seguinte questão: “Um grupo tem 10 pessoas. Quantas comissões de no mínimo 4 pessoas podem ser formadas, com as disponíveis?”. Segue então nosso problema: Um grupo tem 5 pessoas. Quantas comissões de no mínimo 3 pessoas podem ser formadas, com as disponíveis? Proposta de desenvolvimento: Inicialmente o professor pode propor aos alunos que construam todas as comissões possíveis, por se tratar de um grupo relativamente pequeno de pessoas, a enumeração direta não é um processo trabalhoso. Depois disso o professor pode pedir para os alunos resolverem o problema por meio de combinação simples. Logo a seguir trabalhamos outra forma de solucionar este problema, que é por meio das funções geradoras, que tem o papel de mapear e integrar outros conceitos de polinômios de uma ou mais variáveis aos problemas de combinatória. Solução 1- Solução descritiva: Sempre que houver tempo encorajamos o professor a sugerir ao aluno que descreva todas as soluções nomeando-se as pessoas de um modo sugerido pelos alunos. Por exemplo, o professor pode sugerir os nomes A, B, C, D e E , então, neste caso podemos descrever explicitamente as comissões como {A, B, C}, {A, B, D}, {A, B, E}, {A, C, D}, {A, C, E}, {A, D, E}, {B, C, D} {B, C, E}, {B, D, E}, {C, D, E} comissões com 3 pessoas; {A, B, C, D}, {A, B, C, E}, {A, B, D, E}, {A, C, D, E}, {B, C, D, E} , com 4 pessoas e {A, B, C, D, E} comissão com 5 pessoas. comissões 38 As dificuldades que os alunos vão encontrar em ordenar todas as comissões de uma forma racional como foi feito acima pode valorizar de modo instrutivo a solução por função geradora que o professor vai apresentar. Fica aqui outra sugestão que pode facilitar a contagem, iremos chamar de “o pulo do gato”. Nomear as pessoas por números 1, 2, 3, 4, 5 e formar as comissões de 3, 4 e 5 pessoas com uma sequência 123 para designar a comissão {1, 2, 3} . Assim {123, 124, 125, 134, 135, 145, 234, 235, 245, 345} formam as 10 comissões com 3 pessoas e {1234, 1235, 1245, 1345, 2345} formam as comissões com 4 pessoas e {12345} a comissão com 5 pessoas formando um total de 16 comissões. Note que a ordenação dos números nas comissões pode ser uma “prova” de que nenhuma comissão foi esquecida. Está é a idéia que iremos utilizar nos polinômios para descrever todas as comissões. Solução 2: Solução tradicional: O professor pode ainda mostrar que uma comissão formada pelas pessoas A, B e C é igual a comissão formada pelas pessoas B, C e A , logo, podemos concluir que em cada comissão a ordem das pessoas não é importante. Como as comissões devem ter no mínimo 3 pessoas temos que considerar comissões com 4 e com 5 pessoas também. Logo este problema pode ser resolvido com a soma das combinações simples das cinco pessoas tomadas 3 a 3, 4 a 4 e 5 a 5. 3 4 5 5 5 5 C C C  5! 5! 5!    10  5  1  16 3!(5  3)! 4!(5  4)! 5!(5  5)! Os alunos podem comparar, neste caso, o modelo de solução descritiva com o resultado obtido nesta solução. Solução 3: Descrevendo e contando todas a soluções com polinômios. Se supormos que as pessoas são dadas pelas variáveis x1 , x2 , x3 , x4 e x5 então vamos obter a descrição de todas as comissões através de um polinômio com 5 variáveis da seguinte maneira: As comissões compostas com apenas 1 pessoa também serão identificadas por x1 , x2 , x3 , x4 e x5 . Note que se colocamos um sinal de + entre as variáveis obtemos um polinômio de grau 1 com as 5 comissões de uma pessoa. 39 p1  x1  x2  x3  x4  x5 Analogamente o conjunto das comissões com duas pessoas xi e x j podem ser denotadas pelo conjunto {x1, x2} ou pelo monômio do segundo grau x1 x2 . Deste modo o conjunto de todas as comissões com duas pessoas podem ser denotadas pelo polinômio p2 de grau dois com 10 termos sendo que cada termo representa uma comissão distinta. p2  x1x2  x1x3  x1 x4  x1 x5  x2 x3  x2 x4  x2 x5  x3 x4  x3 x5  x4 x5 O professor pode chamar a atenção de que a forma de enumeração escolhida segue uma ordem lógica dos índices que aparecem, são números na ordem crescente 12, 13, 14, ..., 45 . Deste modo podemos “certificar” que colocamos todas as comissões possíveis com duas pessoas. Analogamente, as comissões com três pessoas podem ser dadas pelo polinômio p3 , as comissões com quatro pessoas pelo polinômio p4 e as com cinco pessoas pelo polinômio p5 , descritos a seguir: p3  x1x2 x3  x1 x2 x4  x1 x2 x5  x1 x3 x4  x1 x3 x5  x1 x4 x5  x2 x3 x4  x2 x3 x5  x2 x4 x5  x3 x4 x5 p4  x1x2 x3 x4  x1x2 x3 x5  x1 x2 x4 x5  x1 x3 x4 x5  x2 x3 x4 x5 p5  x1 x2 x3 x4 x5 Como no caso das comissões com duas pessoas, escolhemos colocar os termos dos polinômios de uma certa maneira de modo que os índices apareçam numa ordem numérica crescente. Estes polinômios podem ser colocados também de uma forma mais sintética como um único polinômio que é o produto de 5 binômios de grau 1 dados por: p  (1  x1 )(1  x2 )(1  x3 )(1  x4 )(1  x5 )  1  p1  p2  p3  p4  p5 O polinômio p descreve todas as comissões possíveis com cinco elementos, isto é, cada termo deste polinômio representa uma comissão distinta e a constante 1 pode ser interpretada como associada à comissão vazia. Muito embora este polinômio descreva todas as comissões ele não fornece a resposta do problema proposto. Como cada polinômio pk descreve todas as combinações possíveis com k pessoas então se fizermos: 40 x  x1  x2  x3  x4  x5 então: p( x)  (1  x)5  C 0 k  5 5 k xk , ou,  5  5  5  5  5  5 p  x   (1  x)5    .15    .14. x    .13. x2    .12. x3    .1.1 x4    . x5  0 1  2  3  4  5 p  x   1  5x 10 x2 10x3  5x4 1x5 A solução do problema é dada pela soma dos coeficientes dos termos de graus 3, 4 e 5 do polinômio p( x) 3 4 5 5 5 5 C C C  5! 5! 5!    10  5  1  16 3!(5  3)! 4!(5  4)! 5!(5  5)! e o polinômio p( x) é chamado de função geradora ordinária. Comentários: 1- Se o aluno tentou descrever todas as soluções sem aplicar uma sistemática de contagem ele vai ter dificuldades em certificar-se de que ele descreveu todas as comissões possíveis. A solução tradicional vai lhe fornecer um número e ele poderá voltar ao problema e verificar se todas as combinações foram contadas. A solução polinomial vai ensinar ao estudante uma forma de sistematizar a contagem das comissões na forma polinomial. 2- A substituição das variáveis x  x1  x2  x3  x4  x5 que transforma o polinômio descritor numa função geradora pode ser usada para justificar que os coeficientes do Binômio de Newton ou Teorema Binomial são combinações pois, alguns textos, (BARRETO, 2003), não apresentam provas explicativas destes resultados. 3- Um dos mistérios do enunciado do problema 1 está na expressão “no mínimo 3 pessoas” que pode causar uma dificuldade de interpretação para os alunos. O professor poderá propor como exercício o mesmo problema trocando a expressão no mínimo 3 pessoas” por “no máximo 4 pessoas” (podendo ou não levar em conta a comissão vazia) ou ainda, trocar pela expressão por “no mínimo 2 e no máximo 4 pessoas”. 41 3.2 Problema 2 Existem 10 jogadores de futebol de salão, entre eles João, que por sinal é o único que joga como goleiro. Nestas condições, quantos times de 5 pessoas podem ser escalados? Proposta de desenvolvimento: Como no problema 1 pode-se primeiramente pedir aos estudantes para construir um quadro com todas as possibilidades para que estes tenham uma resposta esperada. Eles irão notar que é uma construção trabalhosa, então, logo depois pode-se pedir para que eles resolvam o problema da forma apresentada a seguir, posteriormente faremos a solução por meio das funções geradoras ordinárias que nos darão assim todas as possíveis formações de grupos com n pessoas entre as nove disponíveis. Solução 1: Solução tradicional: Observando que João, por ser o único goleiro, já tem confirmação garantida na escalação, devemos então escolher mais quatro jogadores entre os nove disponíveis, como no exemplo anterior devemos usar uma combinação simples para encontrar o resultado, pois o professor pode mostrar aos alunos que neste caso, a ordem das pessoas é irrelevante, então o correto é: C 4 9  9! 9.8.7.6   126 4!9  4! 4.3.2.1 O professor pode chamar a atenção dos alunos para mostrar que construir uma tabela de possibilidades neste caso, seria muito trabalhoso. Solução 2: Aplicando os polinômios: “Solucionar este problema utilizando funções geradoras é dar um tiro de canhão para matar uma formiguinha”.(TEIXEIRA, 2004, p. 22). Neste exercício não utilizaremos os polinômios da função geradora para mapear a situação, porque como já dissemos será um processo trabalhoso, entretanto usaremos a função geradora para articular outros conteúdos como os coeficientes binomiais, polinômios e combinação. Devemos lembrar que um jogador pode ser ou não selecionado, daí para representar uma pessoa usaremos o polinômio pn  (1  xn ) , claro que se utilizarmos 1 x1  , 1 x2  , ..., 1 x9  para nomearmos os jogadores, quando fizermos o produto deles descreveremos todas as 42 possibilidades, então faremos x  x1  x2  ...  x9 , teremos assim o produto p  x   (1 x)9 , fazendo sua expansão, agora utilizando o conceito de coeficientes binomiais temos: 9 9  9 9 9 9 9 9  9  9 p  x   (1  x)9       x    x 2    x3    x 4    x5    x6    x7    x8    x9  0 1  2  3  4  5  6 7 8 9 p  x   1 9x  36x2  84x3 126x4 126x5  84x6  36x7  9x8  x9 O resultado que queremos é o coeficiente de x 4 que é igual a 126 , que são todas as possibilidades de se escolher quatro pessoas entre nove. Segue que p( x) é a função geradora ordinária deste problema, pois nos dá todas as maneiras de escolher n pessoas dentro do grupo de nove pessoas, assim podemos agora determinar facilmente quantos grupos com 2 pessoas podemos formar com os nove disponíveis, observando-se o coeficiente de x 2 que é igual a 36 . Comentários 1- Vale lembrar que é um processo mais trabalhoso que a combinação em si, entretanto estamos aqui articulando os conteúdos e as funções geradoras nos propiciam uma integração de conhecimentos enriquecedora. 2- Teixeira (2004) chama o binômio 1  x  de “polinômio controlador”, pois o mesmo tem por objetivo determinar se um jogador é ou não selecionado. Isso se dá por que o símbolo 1 , como foi dito no exercício anterior, é interpretado com uma comissão vazia, 1  x0 , ou seja, uma pessoa não selecionada. 3.3 Problema 3 O problema a seguir retirado de (GARCIA, 2013) foi contextualizado em uma possível situação real. Um professor de Educação Física quer montar um time misto com 7 jogadores. Quantas soluções são possíveis de forma que tenha no máximo 5 meninos ou 5 meninas? Proposta de desenvolvimento: Pela simplicidade do problema é possível que o 43 professor peça aos alunos que façam a enumeração direta do problema, em um segundo momento, mapearemos o problema para ser resolvido utilizando as funções geradoras. Como estamos interessados somente no número de meninos e meninas esse problema poderia ser reformulado como: “De quantas maneiras distintas podemos resolver a equação x  y  7 com x e y inteiros positivos ou nulos menores ou iguais a 5 ?” (GARCIA, 2013). Solução 1: Solução descritiva: Fazendo a enumeração direta, utilizando uma tabela: Meninas 2 3 4 5 Meninos 5 4 3 2 Assim, existem quatro soluções para o problema. Solução 2: Descrevendo e contando todas a soluções com polinômios: Usaremos as funções geradoras para solucionar o problema. Primeiramente vamos adotar um polinômio para cada variável, que são no caso, os meninos e as meninas: pma ( x)  x0  x1  x2  x3  x4  x5 e pmo ( y)  y0  y1  y 2  y3  y 4  y 5 Observe que os expoentes das variáveis x e y em cada polinômio pertencem ao conjunto {0, 1, 2, 3, 4, 5} , cujos elementos são os possíveis valores que se podem escolher de meninas e meninos. Multiplicando os polinômios pma  x  e pmo  y  , teremos o polinômio de duas variáveis: p( x, y)  pma ( x). pmo ( y)  ( x 0  x1  x 2  x3  x 4  x5 ). ( y 0  y1  y 2  y 3  y 4  y 5 )   p0  p1  p2 ....  p9  p10 em que pk são polinômios de grau k . A parcela de p7 de p( x, y) é dada por p7  x2 y5  x3 y 4  x4 y3  x5 y 2 Como os expoentes de x e y somam 7 então as parcelas de p7 nos fornece todas as soluções inteiras da equação x  y  7 com x e y positivos ou nulos e menores ou iguais a 5 . Como no problema 1 , fazendo-se x  y no polinômio p( x, y) obtemos o 44 polinômio p( x)  1  2x  3x 2  4x3  5x 4  6x5  5x6  4x7  3x8  2x9  x10 . e a solução do nosso problema é o coeficiente de x 7 em p(x) . Dizemos que p(x) é a função geradora ordinária do problema. A função geradora p(x) cujo coeficiente de x 7 nos fornece a solução procurada poderia ser obtida de imediato multiplicando-se diretamente, como em (BOAES, 2013): p( x)  PMa ( x). PMo ( x)  ( x 0  x1  x 2  x3  x 4  x 5 ). ( x 0  x1  x 2  x 3  x 4  y 5 )   1  2 x  3x 2  4 x3  5 x 4  6 x5  5 x 6  4 x 7  3x8  2 x9  x10 Segue porém que o polinômio p( x, y) constrói todas as soluções justificando a função geradora. 3.4 Problema 4 Este problema foi adaptado de (KNUTH, 1995, p. 239) cuja solução utiliza relações de recorrência entre os coeficientes da função geradora sem usar uma “fórmula” para gerar os coeficientes. De quantas maneiras podemos dar R$ 0, 20 de troco utilizando-se moedas de 1 centavo, 5 centavos e 10 centavos? 1º passo: Trabalhando um problema bem mais simples. De quantas maneiras podemos dar R$ 0,10 de troco utilizando-se moedas de 1 centavo e de 5 centavos? Todos os estudantes são capazes de dar a resposta contando as possibilidades. O professor poderá discutir com os alunos se este problema pode ser resolvido da mesma forma que o problema 3 , isto é, se u denota a variável de um centavo e c as moedas de cinco centavos, então este problema é o mesmo que resolver a equação u  c  10 com u e c variando de 1 a 10 ?, Esta é uma abordagem equivocada, pois, esta equação tem soluções que não se adéquam ao 45 problema, por exemplo, u  7 e c  3 , neste caso corresponde à um troco de R$ 0, 22 , e isto significa que não podemos usar todos as soluções u , c que somam 10 . Vamos propor uma contagem usando os expoentes de polinômios como fizemos com o problema 3 . Para isto, vamos denotar um troco de uma, duas, três, etc. moedas de um centavo por u, u 2 , u3 , ... e vamos denotar por 1  u 0 nenhuma moeda de um centavo. Analogamente faremos o mesmo com as moedas de cinco centavos que denotaremos por c e indicaremos por u 3c 2 ou c 2u 3 um troco de duas moedas de cinco centavos e três moedas de um centavo. Vamos denotar por U  1  u  u 2  u3  ...  u10  ... Diferentemente do problema anterior, não vamos delimitar o valor máximo para cada moeda e, desta forma, o produto C  (1  c  c 2  ....) U  (1  c  c 2  ....)(1  u  u 2  u 3  ...  u10  ...)   1  u  c  u 2  uc  .....  (u 5c  u10  c 2 )  .... (3.4.0). descreve todos os trocos possíveis com as duas moedas. Para se obter a resposta desejada devemos obter as combinações das duas moedas que somam 10 centavos e, para isto, vamos substituir as variáveis u  x , c  x5 em C C ( x)  (1  x5  x10  ...)(1  x  x 2  ...  x10  ...)   1  x  x 2  x3  x 4  2 x5  2 x 6  2 x 7  2 x8  2 x9  3x10  3x11  ...  3x14  4 x15  ... (3.4.1) Deste modo C ( x) é a função geradora e o coeficiente 3 de x10 é a solução procurada. Nesta altura o professor pode induzir que os alunos cheguem a uma conclusão de que os cinco primeiros coeficientes de C ( x) é 1 e que estes aumentam de uma unidade quando a potências aumentam de 5 unidades. Para se calcular o coeficiente de um termo geral x n qualquer dividimos o número n por 5 , desprezamos a parte fracionária e acrescentamos mais um, isto é dado pela fórmula n Cn     1 5 46 n n na qual   denota o maior inteiro entre todos os inteiros menores ou iguais a . 5 5 2º passo: Solução do problema 4 por recorrência. Vamos acrescentar ao problema simplificado com duas moedas de 1 e 5 centavos mais uma moeda de 10 centavos ao troco e cada conjunto com k moedas de 10 centavos será designada por d k . Se denotamos por ui d j d k um troco com i moedas de 1 centavos, j moedas de 5 centavos e k moedas de 10 centavos então, do mesmo modo anterior, podemos obter a descrição de todos os trocos possíveis com as três moedas com a série D  (1  d  d 2  ...  d n  ...)C Na qual C é a série dos trocos com as moedas de 1 e 5 centavos da equação (3.4.0). Substituindo d  x10 , c  x5 , u  x , temos a série D( x)  (1  x10  x20  ...  x30  ...)C( x)  D0  D1x  ....  Dn xn  ... Multiplicando a equação por (1  x10 ) e como (1  x10 )(1  x10  x20  ...  x30  ...)  1 , então (1  x10 ) D( x)  C( x) Coletando os coeficientes de mesmo grau em (1  x10 ) D( x) temos (1  x10 ) D( x)  D0  D1 x  ...  D9 x9  ( D10  D0 ) x10  ( D11  D1 ) x11  ....  ( Dn  Dn 10 ) x n  ....  C0  C1 x  C2 x 2  ...  Cn x n  . de onde temos uma relação de recorrência entre os coeficientes de C ( x) e D ( x ) dada por D0  C0 , D1  C1, ..., D9  C9 e Dn  Dn10  Cn , se n  10 Deste modo podemos dar a resposta para o problema que é saber de quantas maneiras são possíveis de dar um troco de 20 centavos com as 3 moedas. Pela relação de recorrência.  20  Pela (3.4.1), C10  3 e C20     1  5 então D10  D0  C10  1  3  4 5 e portanto a resposta do problema é C20  D10  C20  4  5  9 Conclusão: Temos 9 possibilidades de troco com as três moedas. Neste caso 47 podemos descrever os 9 trocos possíveis como: {d 2 , dcc, dcu5 , du10 , c4 , c3u5 , c2u10 , cu15 , u 20} . Note que com a relação de recorrência Dn  Dn10  Cn podemos calcular o número de trocos distintos de n centavos quaisquer com os três tipos de moedas. O leitor poderá encontrar uma solução deste problema aumentando as moedas de troco com valores de R$ 0, 25 e R$ 0,50 em (KNUTH, 1995, p.239 ). 48 CONCLUSÃO A Análise Combinatória é de fato um instrumento de vital importância na matemática e nas ciências aplicadas, logo podemos afirmar que é um conhecimento necessário que deve receber seu devido valor, o que muitas vezes não ocorre. Vimos que existem algumas falhas na formação, ou, até mesmo no professor que torna o ensino de combinatória um trabalho um pouco mais complicado, talvez a falta, por parte de professor, de continuar em constante processo de capacitação. Podemos dizer também que muitas vezes o livro didático não dá o suporte necessário, e que, não aborda o conteúdo de uma forma metódica, isto é, a partir do ensino fundamental de forma gradativa. Os problemas aqui apresentados ficam como uma opção aos professores do Ensino Médio e Ensino Superior, para que em suas aulas eles possam estar integrando outros conteúdos ao ensino de combinatória. Trabalhar com funções geradoras nos dá essa oportunidade para introduzir outros conceitos, como binômio de Newton, polinômios, séries geométricas, que são alguns dos exemplos apresentados. Esperamos assim que o professor possa ir mais além capacitando-se em busca de sabedoria, pois quando seu conhecimento cresce a educação dada por ele cresce também. Sobre o ensino de combinatória podemos concordar com Garcia (2013) quando ele diz: A Análise Combinatória contribui significativamente para a elaboração de situações problemas que podem ser discutidas através de conjecturas e discussão de idéias, promovendo o desenvolvimento da capacidade de argumentação em diferentes níveis de ensino. (GARCIA, 2013, p. 63) Assim cremos que trabalhando funções geradoras no Ensino Médio, com certa prudência, pode tornar o ensino de combinatória mais espontâneo e atraente para o aluno. 49 REFERÊNCIAS BARRETO FILHO, Benigno; SILVA, Cláudio X. Matemática aula por aula. 1. Ed. São Paulo: FTD, 2003. BRASIL. Ministério da Educação. Secretaria de Educação Média e Tecnológica. Parâmetros Curriculares Nacionais: Ensino Médio. Brasília: MEC, 2000. GARCIA, Domingos Boaes. Resolução de Problemas Combinatórios Utilizando Funções Geradoras. São Luís: Universidade Federal do Maranhão Centro de Ciências Exatas e Tecnologia, 2013. Disponível em: <http://bit.profmatsbm.org.br/xmlui/handle/123456789/134/browse?value=DOMINGOS+BOAES+GAR CIA&type=author>. Acesso em: 29 de março de 2014. IEZZI, Gelson et al., Matemática: Ciência e Aplicações, 2: ensino médio. 6. Ed. São Paulo: Saraiva, 2010. IEZZI, Gelson et al. Fundamentos de Matemática Elementar. Vol.5. 3. Ed. São Paulo: Atual Editora, 1977. KNUTH, D. E.; GRAHAN, J.; PATASHNIK, O. Matemática Concreta: Fundamentos para a Ciência da Computação. 2. Ed. Rio de Janeiro: Ltc, 1995. MONTEIRO, L. H. J. Elementos de álgebra. Rio de Janeiro, Ao Livro Técnico, 1969. PAIVA, M.R. Matemática.v2. São Paulo, Moderna, 1995. SABO, Ricardo Dezso. Saberes Docentes: A análise combinatória no Ensino Médio. São Paulo: Pontifícia Universidade Católica de São Paulo – PUC/SP, 2010. Disponível em: <http://www.sapientia.pucsp.br//tde_busca/arquivo.php?codArquivo=10692>. Acesso em: 29 de março de 2014. SABO, Ricardo Dezso. Análise dos livros didáticos do Ensino Médio: Um estudo dos conteúdos referentes à Combinatória. Santo André: Centro de PósGraduação, Pesquisa e Extensão do Centro Universitário Fundação Santo André, 2007. Disponível em: <http://www.pucsp.br/~cileda/Monografia_RicardoSabo.pdf>. acesso em: 29 de março de 2014. SANTOS, J. Plínio O.; MELLO, Margarida P.; MURARI, Idani T. C. Introdução à Análise Combinatória. 4. Ed. Rio de Janeiro: Editora Ciência Moderna Ltda., 2007. SANTOS, J. Plínio O.; ESTRADA, Eduardo Luis Problemas Resolvidos de Combinatória. 2. Ed. Rio de Janeiro: Editora Ciência Moderna Ltda., 2011. TEIXEIRA, Cleidemar dos Santos. Um Estudo Sobre Funções Geradoras. Florianópolis: Universidade Federal de Santa Catarina Centro de Ciências Físicas e Matemáticas, 2004. Disponível em: <https://repositorio.ufsc.br/xmlui/handle/123456789/96722>. Acesso março de 2014. em: 29 de