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 {${a_{n}}$} de valores tem de outro membro da seqüência que o precedem. Por exemplo, a famosa seqüência de Fibonacci {$F_{n}$} 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(r_{n-1},r_{n-2},\ldots ,r_{n-k})$,

em que cada termo $r_{n}$ da sequência depende de um número k dos termos que o precedem na seqüência. Por exemplo, para a sequência de Fibonacci, a função F é $f(x,y)=y+x$.

Para entender como podemos trabalhar com relações de recorrência em Maple, temos de parar por um momento e perceber que uma sequência $r_{n}$ de valores (números, matrizes, círculos, funções, etc.) é apenas uma função cujo domínio passa a ser o conjunto de inteiros (geralmente positivos). Se queremos levar este ponto de vista (e nós queremos!), então o $r$ enésimo termo $r_{n}$ de uma sequência de {$r_{n}$} seria convencionalmente escrito como $r_{(}n)$, e gostaríamos de referir à função r. Desta forma, podemos pensar na seqüência {$r_{n}$} como uma forma de representar uma função $r$ cujo domínio é o conjunto de números inteiros positivos, e cujo valor no número $n$ é apenas $r_{n}=r(n)$. Isto apenas equivale a uma mudança na notação; não há nada mais do que isso.

Uma vez que esta alteração na notação for feita, então é fácil ver como representar uma relação de recorrência como um procedimento Maple tendo argumentos inteiros.

No capítulo 3 descobrimos como representar de forma eficiente a seqüência de Fibonacci pelo procedimento:

Fibonacci := proc(n::posint) option remember;
if   n = 1  or n = 2 then RETURN( 1 ); fi;
Fibonacci2(n-1) + Fibonacci2(n-2);

Lembre-se que a primeira linha deste procedimento instrui a Maple de lembrar que quaisquer sejam os valores do processo já foram calculado na sessão atual.

Às vezes, apesar de nossos melhores esforços, uma aplicação recursiva de um algoritmo pode ser muito caro, simplesmente devido à sua própria natureza. A aplicação recursiva pode ser evitado se podemos encontrar uma fórmula explícita para o termo geral da recorrência. O processo de encontrar uma fórmula explícita é referido como resolver a recorrência. Na próxima seção, veremos como usar Maple para fazer isso por certos tipos de relações de recorrência.

1.1 Torre de Hanoi

O famoso enigma conhecido como Torre de Hanoi é discutido no texto, onde a relação de recorrência:

$H_{n}=2H_{n-1}+1,H_{1}=1$

é derivada, em que $H_{n}$ indica o número de movimentos necessários para resolver o enigma para n discos. Como discutido no texto, este tem a solução $H_{n}=2^{n}-1$

Mais tarde, veremos como usar Maple para obter esse resultado de forma simples.

Além de resolver para o número de movimentos necessários para resolver o enigma das Torres de Hanói para para n discos, podemos ilustrar a solução escrevendo um programa em Maple para calcular os movimentos necessários para resolver o dito problema, e descrevendo-os para nós. Nós vamos escrever um pequeno programa em Maple que consiste em três procedimentos: o principal programa de Hanói, a rotina utilitária PrintMove , e o mecanismo recursivo do programa TransferDisk, que faz a maioria do trabalho.

A parte mais fácil de escrever é a função PrintMove, que apenas mostra para nós a mudança para fazer em um determinado passo.

  PrintMove: = proc (src :: string, dest :: string)
  printf (`Mova disco de peg% s para peg% s`,

          src, dest);

  end:

Aqui, nós apenas chamamos o comando printf da biblioteca do Maple, que pode ser usado para saída formatada. A função printf tem uma sintaxe de chamada complexa; consulte a ajuda online para obter detalhes e informações adicionais. (Nota: Se você estiver familiarizado com a função printf em C, então você vai achar que a versão do Maple do printf é bem semelhante. Neste caso, os símbolos %s acima são substituídos pelos valores de string do segundo e terceiro argumentos, respectivamente.)

Em seguida, o procedimento recursivo TransferDisk faz a maior parte do trabalho para nós. Esta função modela a ideia de transferir um disco de um Peg para outro. Mas, porque é recursivo, precisamos fornecer a ele, como um argumento, o número total de discos a serem tratados em cada chamada.