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.

 TransferDisk := proc(src::string, via::string, 
 dest::string, ndisks::posint)
     if ndisks = 1 then
         PrintMove(src, dest);
     else
         TransferDisk(src, via, dest, ndisks -1);
         PrintMove(src, dest);
         TransferDisk(via, dest, src, ndisks -1);
     fi;
 end:

Finalmente, empacotamos em uma procedure de alto nível, Hanoi, proporcionando assim uma interface para o mecanismo recursivo.

 Hanoi := proc(ndisks::posint)
   if ndisks < 1 then
       printf(`What's wrong with this picture?`);
   else
       TransferDisk(`A`, `B`, `C`, ndisks);
   fi;
 end:

Nosso programa Hanoi consegue exibir uma solução específica para o Enigma das Torres de Hanoi para qualquer número ndisk de discos.

 Hanoi(2);
 Hanoi(3);

Tente experimentar com diferentes valores ndisk para ter uma noção do quão grande o problema se torna mesmo para valores moderadamente grandes de ndisks.

2. Resolução de recorrências com Maple

Agora que sabemos como implementar relações de recorrência em Maple, e temos trabalhado com eles um pouco, vamos ver como usar Maple para resolver certos tipos de relações de recorrência.

Maple tem um poderoso solucionador de recorrência, rsolver, que discutiremos mais tarde. A sua utilização, no entanto, pode obscurecer algumas das ideias importantes que estão envolvidas. Portanto, devemos primeiro usar algumas das instalações mais rudimentares do Maple para resolver certos tipos de relações de recorrência, um passo de cada vez.

Dada uma seqüência definida recursivamente ${r_{n}}$, o que nós gostaríamos é encontrar algum tipo de fórmula, envolvendo apenas o índice n (e, talvez, outras constantes fixas e funções conhecidas) que não dependem do conhecimento da valor de $r_{k}$, por qualquer índice k.

Para começar, vamos considerar relações de recorrência que são lineares, homogêneas, e que têm coeficientes constantes; ou seja, eles têm a forma

$r_{n}=a_{1}r_{n-1}+a_{2}r_{n-2}+\cdots +a_{k}r_{n-k}$

onde $a_{1},a_{2},\ldots ,a_{k}$ são constantes reais e $a_{k}$ é diferente de zero. Lembre-se que o inteiro k é chamado de grau da relação de recorrrência. Para ter uma núnica solução, pelo menos o k inicial deve sere especificado.

O método geral para resolver tal relação de recorrência envolve encontrar as raízes de seu polinômio característico.

$x^{k}-a_{1}x^{k-1}-a_{2}x^{k-2}-\cdots -a_{k-1}x-a_{k}$

Quando este polinômio tem raízes distintas, todas as soluções são combinações lineares das enésimas (palavra para número ordinal) potências dessas raízes. Quando não são raízes repetidas, a situação é um pouco mais complicado, como veremos.

Para começar, vamos considerar uma relação de recorrência linear homogênea com coeficientes constantes de grau dois:

$r_{n}=2r_{n-1}+3r_{n-2}$

sujeitos às condições iniciais

$r_{1}=4$ and $r_{2}=2$

Então sua equação caracerística é:

$x^{2}-2x-3$

Para resolver a relação de recorrência, temos de resolver para as raízes dessa equação. Usar Maple faz disso algomuito fácil; nós usamos a função solve em Maple para fazer isso.

 solve (x ^ 2-2 * x - 3 = 0, x);

A sintaxe diz à função que queremos os valores da variável x que satisfazem a equação quadrática.

$x^{2}-2*x-3=0.$

Agora que o Maple aponta que as soluções são $x=3$ e $x=-1$, podemos escrever a forma de a solução para a recorrência como

$r_{n}=\alpha 3^{n}+\beta (-1)^{n}$

onde \alpha e \beta são constantes que ainda temos de determinar. Podemos usar Maple para determinar as constantes \alpha e \beta. Uma vez que as condições iniciais são $r_{1}=4er_{2}=2$, sabemos que a nossa relação de recorrência deve satisfazer as seguintes duas equações.

$3\alpha -\beta =4$ $3^{2}\alpha +\beta =2$

2.1. Uma relação de recorrência linear homogênea com coeficientes constantes

Agora vamos generalizar o que temos feito e escrever um procedimento em Maple para resolver uma relação de recorrência geral homogênea com coeficientes constantes, de grau 2, considerando que as raízes do polinômio característico da relação de recorrência são distintos. Vamos escrever um procedimento RecSol2 que resolve a recorrência

$r_{n}=ar_{n-1}+br_{n-2}$

sujeito às condições iniciais

Failed to parse (unknown function "\hspace"): {\displaystyle r_{1} = u \hspace{3em}\mbox{and}\hspace{3em} r_{2} = v }

e, em seguida, retorna um procedimento que pode ser utilizado para calcular termos da sequência. Por enquanto, suponha que o polinômio característico $x^{2}-ax-b$ tem duas raízes distintas. Então, tudo o que o nosso procedimento precisa fazer é repetir os passos que fizemos manualmente no nosso exemplo anterior.

 RecSol2 := proc(a, b, u, v) 
   local evals, S, alpha, beta, ans , n;

Resolve-se a equação característica

 evals := solve(x^2 - a * x - b = 0, x);

Depois, resolve-se o sistema de equações lineares

   S := solve(alpha * evals[1] + beta * evals[2] = u,
       alpha * evals[1]^2 + beta * evals[2]^2 = v,
       alpha,beta);
   ans := subs(S,alpha*evals[1]^n + beta*evals[2]^n);
   RETURN( unapply( ans , n ) );
end:

Paraobservar como funciona, iremos tentar alguns casos de teste. Paraconstruir uma função para calcular a sequencia Fibonacci chamamos nosso novo procedimento:

 f := RecSol2(1,1,1,1,5);

O procedimento resultante ode ser usado para calcular o termo geral da sequencia Fibonacci.

 f(n);

Da mesma forma, os primeiros cinco números Fibonacci podem ser calculados da seguinte forma:

 seq(simplify(f(n)), n = 1..10);

Agora apresentamos uma resolução que pode lidar com o caso de raízes repetidas.

Antes de olharmos para a nova versão do RecSol2, vamos olhar para um exemplo envolvendo uma relação de recorrência com um valor double próprio (raiz de seu polinômio característico). A relação de recorrência

Failed to parse (syntax error): {\displaystyle r_} {n = 4 r_ {N-1} - 4 r_ {N-2} }

tem a equação característica

 char_eqn := x^2 - 4 * x + 4 = 0;

com eigenvalues?????

 evals := [solve(char_eqn, x)];

No geral, para testar um eigenvalue repetido, que é o caso para este exemplo, apenas testamos se

 evalb(evals[1] = evals[2]);

(Nota: Nós não requeremos o uso de EVALB em uma instrução condicional já que expressões são automaticamente avaliados como booleans.) Se chamarmos a raiz dupla (2 neste caso) $\ lambda$, então a relação de recorrência tem a solução explícita

$r_{n}=\alpha \lambda ^{n}+n\beta \lambda ^{n}$

para todos os positivos inteiros n, e para algumas constantes $\alpha$ and $\beta$. Assumir as condições iniciais de $r_{1}=1andr_{2}=4$, o conjunto S de equações a resolver é:

 S := alpha * evals[1] + beta * evals[2] = 1,
       alpha * evals[1]^2 + 2* beta * evals[2]^2 = 4;

Como antes, para obter as soluções, digitamos:

 rsols := solve(S, alpha, beta);

É neste ponto que a diferença com o caso de raizes distintas aparece. O nth termo da sequencia, quando á um double eigenvalue, é dado ṕor:

 subs(rsols , alpha * evals[1]^n + n * beta * evals[1]^n );

Os passos feitos neste exemplo são bem gerais Um procedimento geral para resolver uma recorrência de dois termos da forma r(n) = a r(n-1) + b r(n-2), com os valors iniciais values r(1) = u and r(2) = v é:

 RecSolver2 := proc(a,b,u,v)
   local ans, evals, S, alpha, beta, rsols, n;

resolve a equação característica

 evals := solve(x^2 - a * x - b = 0, x);

resolve o sistema de equações lineares

   S := alpha * evals[1] + beta * evals[2] = u,
       alpha * evals[1]^2 + beta * evals[2]^2 = v;
   rsols := solve(S, alpha, beta);
   if evals[1] = evals[2] then # repeated roots
     ans := subs(rsols,alpha*evals[1]^n + beta*n*evals[1]^n);
   else
     ans := subs(rsols,alpha*evals[1]^n + beta*evals[2]^n );
   fi;
   RETURN( unapply(ans , n ) );
 end:

Esta versão da nossa resolução testa primeiro raizes repetidas, e então faz o calculo apropriado baseado no resultado. É chamado da mesma forma que o RecSol2:

 g := RecSolver2(4,-3,1,2);
 i :='i': seq(simplify(g(i)), i=1..10);

Isto dá os dez primeiros termos da sequência definida pela relação de recorrência $r_{n}=4r_{N-1}-3*r_{N-2}$, com condições iniciais $r_{1}=1eR_{2}=2$.

Para resolver a recorrência <maaath> r_{n} = {N -r_-1} - r_ {N-2}</math>, com condições iniciais $r_{1}=1eR_{2}=2$, usamos A solução e os primeiros 100 termos desta sequência são

 h := RecSolver2(-1,-1,1,2);
 i := 'i': seq(simplify(h(i)),i=1..10);

Perceba que o padrão que aparece se substituirmos as condições iniciais $r_{1}=1andr_{2}=2$ com constantes simbólicas.

 k := RecSolver2(-1, -1, lambda, mu);
 i := 'i': seq(simplify(k(i)),i=1..10);

2.2. Relações de recorrência heterogêneas

Nós temos, até agora, discutido relações de recorrência lineares homogêneas com coeficientes constantes. No entanto, as técnicas utilizadas para resolvê-los podem ser extendidas para fornecer soluções para as recorrências heterogêneas deste tipo. Estas são relações de recorrência da forma

math>\ alpha_ {n} r_ {n} + \ alpha_ {n-1} r_ {n-1} + \ cdots + \ alpha_ {nk} {r_ nk} = c_ {n} </math>

onde $\ alpha_{n},\ alpha_{n-1},\ ldots,\ alpha_{nk}ec_{n}$ são constantes. A única nova problemática é que, aqui, o Failed to parse (syntax error): {\displaystyle c_ {n}<math> não precisa ser zero. Dito de outra forma, uma equação desta forma, na qual cada <math>c_ {n}} é zero é homogênea, por isso as relações homogêneas são apenas um caso especial deste tipo mais geral. Para resolver a recorrência mais geral, precisamos fazer duas coisas:

1) Encontrar uma solução específica para a recorrência heterogênea

2) Resolver a recorrência homogênea correspondente.

A recorrência homogênea correspondente é apenas a obtida substituindo a sequência Failed to parse (syntax error): {\displaystyle \ c_ {{n} \} } pela seqüência zero:

$\ alpha_{n}r_{n}+\ alpha_{n-1}r_{n-1}+\ cdots+\ alpha_{nk}{r_{n}k}=0$

Então, nós já sabemos como fazer o segundo passo.

O primeiro passo é mais difícil, mas com a ajuda do Maple, ele manejável.

 rSolve (R (0) = 0, r (n) = 3 * r (n-1) + 3 ^ N, r (n));
 normal (%, expanded);

Isso nos diz que $r_{n}=n3^{n}$ é uma solução para a relação de recorrência $r_{n}=3r_{n-1}+3^{n}$. Agora, todas as soluções são obtidos por adição de uma solução para este conjunto de soluções da recorrência homogênea correspondente.

 rSolve (r (n) = 3 * r (n-1), r (n));
 % + * 3 N ^ N;

Se temos um valor inicial para $r_{0}$, então nós temos uma solução completa.

Agora vamos resolver a Torre de Hanói

Failed to parse (syntax error): {\displaystyle H_} {n = 2H_ {N-1} + 1}

o que dá o número de movimentos necessários para resolver o enigma da Torres de Hanói com n discos. Lembre-se que $H_{1}=1.$ A relação de recorrência homogênea associada é

$h_{n}=2h_{n-1}$

com polinômio característico

$x-2$

A única raiz disso é 2, portanto, todas as soluções da relação de recorrência homogênea têm a forma

$h_{n}=\ alpha2^{n-1}$

para alguma constante $\ alfa$. (A potência de 2 é N-1, em vez de N, porque a recorrência começa no 1 em vez de 0.) Soluções para a H são obtidos a partir das soluções para h por adição de uma solução particular para H. Agora, H tem a solução constante $H_{N}}={-1$, para todo n, então todas as soluções para a H são da forma

$H_{n}=\ alpha2^{n}-1$

Usando a condição inicial

$H_{1}=1$

podemos resolver para $\ alpha$ como se segue.

 solve (alfa * 2 ^ 1 - 1 = 1, alfa);

Assim, a solução para as Torres de Hanói é $H_{n}=2^{n-1}-1$.