Técnicas Avançadas de Contagem

Neste capítulo vamos descrever como usar Maple para trabalhar com três temas importantes na contagem: relações de recorrência, inclusão-exclusão e funções geradoras. Começamos por descrever como Maple pode ser usado para resolver relações de recorrência, incluindo a relação de recorrência para a sequência de números de Fibonacci. Em seguida, mostramos como resolver o enigma da Torre de Hanói e encontramos o número de movimentos necessários para n discos. Descrevemos como Maple pode ser utilizada para resolver as relações lineares homogêneas de recorrência com coeficientes constantes, bem como as relações de recorrência não-homogêneas relacionadas. Depois de descrever como resolver estes tipos especiais de relações de recorrência com Maple, vamos mostrar como usar a resolução geral de recorrência Mapple. Nós ilustramos o uso dessa resolução geral demonstrando como usa-la para resolver divide and conquer relações de recorrência. Depois de estudar relações de recorrência, vamos mostrar como usar bordo para ajudar a resolver problemas usando o princípio da inclusão e exclusão. Ao fim, discutimos como Maple pode ser usado para trabalhar com funções geradoras, um tema abordado no Apêndice 3 no texto.

1. Relações de recorrência

Uma relação de recorrência descreve uma relação que um membro de uma sequência de an de valores tem de outro membro da seqüência que o precedem. Por exemplo, a famosa seqüência de Fibonacci satisfaz a relação de recorrência

F_ {n} = F_ {n-1} + F_ {N-2}

Juntamente com as condições iniciais F_ {1} = 1 e F_ {2} = 1, esta relação é suficiente para definir toda a seqüência \ {F_ {n} \}.

Em geral, podemos pensar em uma relação de recorrência como uma relação do formulário r_} {n = f (N-R_ {1}, {N-R_ 2}, \ ldots, R_ {N-k})