^{Imagem de capa: Imaginemos um varal. [Imagem produzida por Carlos Iago Bueno]} 

Por Eduardo Mathias de Souza

Vamos começar esse texto de divulgação com um exemplo simples e prático: Imagine que você se depara com uma sequência tal como (1,3,5,7,9,…). Você consegue perceber de cara que se trata da sequência infinita de números ímpares. Agora, o que você faz se pedem para você responder qual é o 100º ou o 479º ou o enésimo termo dessa sequência?

Você pode pensar em ver essa sequência como uma recorrência de forma que o enésimo termo (a_n) é o termo anterior (a_n-1) “a” somado com 2, com o primeiro termo dessa recorrência (a₀ ) começando em 1. Assim, a_n= a_n-1 + 2 | n ≥ 1 e a₀ =1. No entanto, para descobrirmos o enésimo termo, aqui temos uma dependência de descobrir o termos antes desse e assim por diante. 

No curso de graduação em Computação, aprendemos que para resolver essa recorrência, ou seja, achar uma fórmula livre de recorrência para essa equação, bastaria expandi-la e utilizar a fórmula geral a_n= a_n-u + 2u, tal que u : min {k ∈ N | n – k < n₀} — para entender um pouco mais, veja o livro “Elementos de Matemática Discreta para Computação” de Anamaria Gomide e Jorge Stolfi. 

Se você é estudante de computação, ou tem interesse no assunto, na sequência demonstrarei uma outra maneira de lidar com sequências que considero tão eficaz quanto e que é pautada apenas na álgebra de funções – que é bem conhecida e economiza linhas para os alunos. Vamos lá?

Funções geradoras são uma forma de codificar sequências como uma série formal de potência infinita. Numa analogia, Wilf (2009) pede para imaginarmos que estamos pegando os números de nossa sequência e pendurando em um varal, na qual cada pregador é um x^n. 

Logo, para a sequência apresentada:

Σ_n>=0 f(x)xⁿ = 1x⁰ + 3x¹ + 5x² + 7x³+ … +(2n+1)xⁿ+ … 

 Cada elemento da série se torna um coeficiente de termo da série formal. 

Seguindo no caminho das funções geradoras, imagine que deixamos as recorrências de lado e recebemos  outra pergunta, por exemplo, com um problema de contagem: quantas maneiras posso tirar 1 coroa em 3 lançamentos de moeda? 

Também temos resposta para essa pergunta, já que a resolução de problemas de contagem também pode ser vista como forma de representar sequências! Siga o raciocínio:

• 1 vez podemos tirar apenas caras  (Ca Ca Ca), 
• 3 vezes podemos tirar 1 cara e 2 coroas (Ca Co Co, Co Ca Co, Co Co Ca), 
• 3 vezes podemos tirar 1 coroa e 2 caras (Co Ca Ca, Ca Ca Co, Ca Co Ca), e 
• 1 vez apenas tirar apenas coroas (Co Co Co). 

Logo, representamos por (1, 3, 3, 1), uma sequência finita. Por se tratar de uma sequência finita, existe tal função geradora que é identidade dessa sequência: f(x) = 1 + 3x + 3x^2 + x^3 + 0x^4 +…..

Na contagem, a potência de x na função geradora representa o número de elementos que queremos contar, e o coeficiente de x representa o número de maneiras de contar esses elementos. 

Vamos recapitular?

O quê?

Uma função geradora é uma forma de codificar uma sequência infinita de números (a_n) ao tratá-los como os coeficientes de uma série formal de potência. Dada uma sequência numérica (a_n) com n>=0, definimos a função geradora dessa sequência como sendo a série formal de potências:

Σ_n>=0 a_nxⁿ = a₀x⁰ + a₁x¹ + a₂x² + a₃x³+ … +a_nxⁿ+ …

Como?

Para tratar uma recorrência como uma função geradora, como trouxemos no exemplo da sequência de números ímpares, precisamos multiplicar a recorrência por x^n e somá-la sobre n. 

Assim: 

1) a_n+1xⁿ = a_n-1xⁿ + 2xⁿ (Multiplicar a recorrência por x^n)
2) Σ_n>=1 a_nxⁿ = Σ_n>=1 a_n-1xⁿ + Σ_n>=1 2xⁿ (Somar sobre n) 

Realizando as manipulações algébricas necessárias, chegamos que a função geradora Σ_n>=0 a_nxⁿ =(1+x)²/(1-x)​. Se desejarmos encontrar o termo a_n, realizamos a Expansão de Taylor  desta equação e temos (2n + 1).

Para o problema de contagem de quantas maneiras posso tirar 1 coroa em 3 lançamentos de moeda, definamos coroa como x^1 e a ausência de coroa como x^0. 

A cada lançamento de moeda, podemos ou não tirar uma coroa, logo, temos a função geradora (x^0 + x) = (1+x) para um lançamento. Repare que o + aqui realiza o papel lógico do OU.

Se lançarmos a moeda 3 vezes, teremos a função geradora (1+x)x(1+x)x(1+x). Repare novamente que a multiplicação faz o papel lógico do E. 

Expandindo essa função, o coeficiente de x^1 representa a maneira de tirar 1 coroa. Logo, a partir de 1 + 3x + 3x^2 + x^3, podemos observar que existem 3 maneiras de tirar 1 coroa em 3 lançamentos de uma moeda. 

Por quê?

Funções geradoras são uma alternativa para solucionar problemas de sequências: sejam eles apresentados como recorrências ou como contagem. Ter alternativas à forma clássica de resolver esses problemas pode muitas vezes sair menos custoso ao aluno, economizando tempo e manipulações algébricas complicadas. O uso das funções geradoras é tão eficaz quanto às alternativas apresentadas em computação algébrica e muitas vezes, mais sucinto.

Manipular sequências de forma crua pode ser uma tarefa difícil: às vezes é complicado visualizar a sua forma fechada e até podem exigir cálculos da álgebra moderna. 

Utilizar uma identidade como as funções geradoras para manipular estas sequências é uma saída: podemos usar toda a álgebra sobre funções para manipular a identidade e depois chegar à solução do problema original de uma maneira eficiente: economizando linhas de papel para o estudante.

Interessante, não?

Agora que você conhece essa forma alternativa, tente utilizá-la para resolver o problema de recorrência da Torre de Hanoi, dado por a_n+1 = 2*a_n + 1, tal que a₀ = 0; n ≥ 0. Resolva e depois veja a resposta aqui: resolução_exemplo.pdf

Referências

BOAS GARCIA, Domingo. Resolução de Problemas Combinatórios Utilizando Funções Geradoras. Disponível em: <https://sca.profmat-sbm.org.br/profmat_tcc.php?id1=331&id2=37752>. Acesso em: 19 outubro 2024.

FLAJOLET, Philippe; SEDGEWICK, Robert. Analytic Combinatorics. 2009.Disponível em:<https://algo.inria.fr/flajolet/Publications/book.pdf>. Acesso em: 18 outubro 2024.

GOMES, Carlos Funções geradoras, funções que contam! – Nível 3 (OBM). Disponível em:<https://www.obm.org.br/content/uploads/2021/11/N3_FunGeradoras_Carlos_Gomes_SO2021.pdf>. Acesso em: 19 outubro 2024.

GOMIDE, Anamaria; STOLFI, Jorge. Elementos de Matemática Discreta para Computação. Disponível em: <https://www.ic.unicamp.br/~stolfi/fmc-book/2018-01-02-js/livro.pdf>. Acesso em 19 outubro 2024.

KAUERS, Manuel; Paule, Peter. The Concrete Tetrahedron – Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. janeiro 2011.

LOPES, Hélio Bernardo. Momentos e funções geradoras. 2010.

TEIXEIRA, Cleidemar dos Santos Um estudo sobre funções geradoras Disponível em: <https://repositorio.ufsc.br/handle/123456789/96722>. Acesso em: 19 outubro 2024.

WILF, Helbert GeneratingFunctionology 2009. Disponível em: <https://www2.math.upenn.edu/~wilf/gfology2.pdf>. Acesso em: 19 outubro 2024

Autoria

Eduardo Mathias de Souza: sou mestrando em Informática na Universidade Federal do Paraná (UFPR), atualmente atuando na área de teoria da computação. Gosto de livros, séries, filmes e de me descrever. Meu contato para quaisquer dúvidas ou comentários é eduardomsouza@ufpr.br

Agradecimentos: Agradeço às revisões de Vinícius Tikara, Carlos Iago Bueno e Roberto Pereira. E especialmente, agradeço duplamente Carlos Iago Bueno pela produção da imagem de capa. 

Como citar essa matéria:
SOUZA, Eduardo Mathias de. Funções Geradoras: o quê, como e por quê? SBC Horizontes. ISSN 2175-9235. outubro de 2024. Disponível em: <url>.  Acesso em: dd mês aaaa.

Compartilhe: