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çaremos 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, mostraremos como resolver o enigma da Torre de Hanoi e encontramos o número de movimentos necessários para n discos. Descreveremos 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 Maple. Nós ilustramos o uso dessa resolução geral demonstrando como usá-la para resolver relações de recorrência com o método “Divide and Conquer”. Depois de estudar relações de recorrência, vamos mostrar como usar Maple para ajudar a resolver problemas usando o princípio da inclusão e exclusão. Ao fim, discutiremos 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 sequência que o precedem. Por exemplo, a famosa sequê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 sequê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. 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 sequê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 sequê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 Hanoi 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, que, posteriormente, os descreverá. Nós vamos escrever um pequeno programa em Maple que consiste em três procedimentos: o principal programa de Hanoi, 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 pino para outro. Mas, uma vez sendo 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, compilamos como um procedimento 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 mecanismo 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 sequê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 ú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 caracterí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 algo muito 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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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:

Para observar como funciona, iremos tentar alguns casos de teste. De modo a construir uma função para calcular a sequencia Fibonacci, chamamos nosso novo procedimento:

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

O procedimento resultante pode 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 autovalor

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

No geral, para testar um autovalor 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 raízes distintas aparece. O enésimo termo da sequência, quando há um double autovalor, é dado por:

 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 raízes repetidas, e então faz o cálculo 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 $r_{n}={N-r_{-}1}-r_{N-2}$, 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 estendidas para fornecer soluções para as recorrências heterogêneas deste tipo. Estas são relações de recorrência da forma

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

onde $/alpha_{n},/alpha_{n-1},\ ldots,/alpha_{nk}ec_{n}$ são constantes. A única nova problemática é que, aqui, o $c_{n}$ não precisa ser zero. Dito de outra forma, uma equação desta forma, na qual cada $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 $c_{n}$ pela sequê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 Hanoi

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 Hanoi 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 Hanoi é $H_{n}=2^{n-1}-1$.

2.3. Resolvendo recorrências em Maple

Agora que vimos como é possível usar Maple para implementar um algoritmo para resolver relações de recorrência simples, é hora de introduzir próprios utilitários do Maple para trabalhar com relações de recorrência. Já vimos o comando Maple solve para trabalhar com equações e sistemas de equações polinomiais. Da mesma forma, há um comando rSolve em Maple, que é especialmente projetado para lidar com relações de recorrência. É uma versão sofisticada de nosso procedimento RecSol2, que pode lidar com relações de recorrência de grau arbitrário, e pode lidar com raízes repetidas, bem como relações de recorrência não-lineares. Para usar rSolve, você precisa dizer a ele qual é a relação de recorrência, e algumas condições iniciais. Você também deve especificar o nome da função recursiva para resolver. Por exemplo, para resolver a recorrência Fibonacci, você pode digitar

 rSolve (f (n) = f (n-1) + f (n-2), F (0) = 0, f (1) = 1, f (n));
 normal (%, expanded);

Não é realmente necessário especificar as condições iniciais para uma relação de recorrência. Se eles não estiverem presentes, o Maple ainda vai resolver a equação, inserindo constantes simbólicas (aqui, G (0) e g (1)) em lugar das constantes numéricas, como o exemplo a seguir ilustra.

 rSolve (g (n) = 2 * g (n-1) - 6 * g (n-2), g (n));

Vemos, nesta fórmula, que Maple utiliza o símbolo I para denotar a unidade imaginária $(/sqrt{-1})$.

A função rSolve pode lidar com vários tipos de diferenças de relações de recorrência. Em Maple V, Release 4, esta lista inclui:

1. relações de recorrência lineares com coeficientes constantes;

2. sistemas de relações de recorrência lineares com coeficientes constantes;

3. “Divide and Conquer” relações de recorrência com coeficientes constantes;

4. muitas relações de recorrência lineares de primeira ordem;

5. algumas relações de recorrência não-lineares de primeira ordem.

As capacidades do rSolve, como outras funções do Maple, estão constantemente a serem melhoradas e ampliadas. Se você tiver uma versão posterior do Maple você pode achar que a sua versão do rSolve tem capacidades para além das enumeradas acima. No entanto, rSolve não é um algo mágico para resolver todos os problemas; você pode facilmente encontrar relações de recorrência que o rSolve é incapaz de resolver. Quando rSolve é incapaz de resolver uma relação de recorrência, ele simplesmente retorna “unevaluated”.

Muitas vezes é o caso que um problema, tal como apresentado, não dá qualquer indicação de que uma solução pode ser encontrada usando recorrências. Vamos ver como podemos usar Maple para resolver um problema real; isto é, um que não esteja explicitamente expresso como um que exige a utilização de recorrência para a sua solução. Em quantas regiões é o plano dividido por 10000 linhas, assumindo que nenhuma das duas linhas são paralelas, e nenhuma das três são coincidentes? Tal situação pode ocorrer, numa tentativa de modelar fissuras no fundo do oceano, ou em qualquer outra parte da superfície da terra.

Para começar, podemos tentar descobrir a resposta para um número menor de linhas. Assim, para generalizar o problema, poderemos perguntar o número de regiões produzidas por n linhas, onde n é um número inteiro positivo. É bastante óbvio que uma única linha (que corresponde ao caso em que n = 1) divide o plano em 2 regiões. Duas linhas, se não forem paralelas, pode ser facilmente vistas para dividir um plano em 4 regiões. (Duas linhas paralelas distintas produzem apenas três regiões.) Se chamarmos o número de regiões produzidas por n linhas, duas das quais são paralelas, e três das quais são coincidentes $r_{n}$, então temos $r_{1}=2$ e $r_{2}=4$. Até agora, ele está começando a se parecer com $r_{n}=n^{2}$. Mas não vamos ter pressa. O que acontece quando a situação se torna semelhante semelhante a n = 3? A figura mostrada aqui é representativa da situação.

Figure: file = ch05 / 3lines.eps

Neste caso, o número $R_{3}$ das regiões é 7, de modo que a estimativa inicial que$R_{n}$ é $n^{2}$ não pode ser certa. Para encontrar $r_{4}$, temos de acrescentar uma quarta linha para o diagrama. Isto sugere tentar calcular $r_{4}$ em termos de $r_{3}$, para que possamos pensar em Failed to parse (syntax error): {\displaystyle \ {r_ {n} \} } como uma relação de recorrência. A figura mostra que a situação parece quando uma quarta linha é adicionada a três linhas existentes.

Figure: file = ch05 / 4lines.eps

A partir dos pressupostos que nem duas das linhas podem ser paralelas e que nenhuma das três passam através de um único ponto, segue-se que a nova linha deve interceptar cada uma das três linhas existentes em exatamente um ponto. Isto significa que a nova linha passa através de exatamente três das regiões formadas pelas três linhas originais. Cada região que é atravessada é dividida em duas zonas, de modo que o número total de novas regiões adicionados através da adição da quarta linha é 3. Assim, $R_{4}=r_{3}+3$. Argumentos semelhantes para uma configuração geral de linhas revelam que $R_{n}$ satisfaz a relação de recorrência

$R_{n}=N-R_{1}+(n-1)$

Além disso, já calculamos a condição inicial $r_{1}=2$. Este é o suficiente para resolver esta recorrência.

 rSolve (
   r (n) = r (n-1) + (n-1),

   R (1) = 2,

 r (n));
 simplify(%);

2.4. Relações de dividir e conquistar

Um bom exemplo de relações de “Divide and Conquer” é a fornecida pelo algoritmo de busca binária. Aqui, vamos considerar uma aplicação prática deste algoritmo em uma implementação de uma busca binária em uma lista ordenada de números inteiros. O algoritmo procura por chave no IList.

 BinSearch := proc(ilist::list(integer), key::integer)
   local mid, lo, hi;
   hi := nops(ilist);
   lo := 0;
   while hi - lo > 1 do
     mid := floor((lo + hi) / 2);
       if key <= ilist[mid] then hi := mid;
     else lo := mid; fi;
   od;
   if ilist[hi] = key then RETURN(hi);
   else RETURN(false); fi;
 end:

A variável IList é a lista de números inteiros para a busca, e o parâmetro key é o número inteiro para procurar. A posição na lista é retornada se ele for encontrado, e o valor false é retornado em caso contrário. Para testar Binsearch, usamos o seguinte passo com uma lista de amostras para pesquisa.

 a := [3,5,7,12,34,546,5324,5346753];
 for i in a do
   if a[BinSearch(a, i)] <> i then
     print(`Socks for President in '96!`);
   fi;
 od;

Infelizmente para Socks, o nosso programa funcionou muito bem.

Vamos agora fazer a análise do algoritmo para ver como relações de recorrência "Divide and Conquer" são geradas. Em geral, uma relação de recorrência do tipo dividir e conquistar tem a forma

Failed to parse (syntax error): {\displaystyle {r_} {n = a r_ {n / K} + b }

para algumas constantes a, K e b. Agora, a rotina Maple rSolve não tem absolutamente nenhuma dificuldade para lidar com até mesmo o tipo mais geral de relação dividir e conquistar.

 rSolve (r (n) = a * r (n / k) + b, r (n));

Se sabemos que, dado $r_{1}=4$, então podemos calcular

 Subs (R (1) = 4,%);

Cada chamada para o algoritmo de busca binária produz listas a = 2, e cada um é metade do tamanho da lista original (k = 2). Portanto, o multiplicador e o período, no caso de um algoritmo de busca binária são ambos iguais a 2 e, portanto, obtemos

 Subs (a = 2, k = 2,%);

Finalmente, se sabemos que b = 2, podemos calcular

 Subs (b = 2,%);
 simplify(%);

3. Inclusão – Exclusão

Nós vamos começar a ver, nesta seção, a segunda das duas principais técnicas de contagem abrangida no Capítulo 5 desse texto – O princípio de inclusão e exclusão. Vamos ver como usar Maple para resolver problemas com essa técnica. No cerne do princípio de inclusão e exclusão está a fórmula

$|A\cup B|=|A|+|B|-|A\cap B|$

a qual diz que, para dois conjuntos finitos A e B, o número de elementos da união AUB de dois conjuntos devem ser encontrados primeiramente ao adicionar os tamanhos |A| de A e |B| de B, e depois subtrair o numero de elementos comuns a ambos A e B, senão seria contado duas vezes. Esta fórmula pode ser generalizada para contar o número de elementos da união de qualquer número finito de conjuntos finitos.

Para trabalhar com fórmulas como esta em Maple, é necessário aprender primeiro como representar conjuntos em Maple. Já que Maple é especialmente projetada para fazer matemática, isto é feito muito naturalmente: para representar um conjunto de elementos, simplesmente listamos estes elementos, separando-os por vírgulas, e incluindo toda a construção em chaves. Por exemplo, para representar o conjunto {2,3,5} cujos membros são os números 2, 3 e 5, nós podemos usar notação matemática comum.

 2, 3, 5;

Em Maple, um conjunto é a estrutura de dados de primeira classe. Você pode atribuir um conjunto a uma variável:

 A := 2, 3, 5;

Perceba que a ideia do Maple de um conjunto corresponde precisamente a uma notação matemática. Assim, não existe uma ordem implícita entre os membros de um conjunto, nem existe qualquer noção de multiplicidade para membros do conjunto. Para problemas que requerem este tipo de informação adicional, outras estruturas de dados, como listas e arranjos, devem ser usadas. Podemos ver isso em Maple com os exemplos a seguir:

 A := `Alice`, `Bob`, `Eve`;
 B := `Bob`, `Alice`, `Eve`;
 evalb(A = B);
 C := `Alice`, `Bob`, `Eve`, `Eve`;
 evalb(A = C);

O procedimento evalf avalia uma expressão booleana, e retorna verdadeiro ou falso, de acordo com a veracidade da falsidade da expressão. Então, Maple considera os três conjuntos A, B e C como o mesmo conjunto. O primeiro exemplo mostra que a ordem em que são listados os membros de um conjunto é irrelevante, enquanto o segundo mostra que, apesar de listar a string ‘Eve’ duas vezes, Maple só a vê uma vez. (Experimento com estes exemplos usando listas, que são delimitadas com colchetes em vez de chaves, para ver a diferença entre conjuntos e listas in Maple).

Para determinar o tamanho de um conjunto (o número de objetos dentro dele) in Maple, usamos o procedimento Maple nops (pense nisso como n operandos)

 A := `Alice`, `Bob`, `Eve`;
 nops(A);
 C := `Alice`, `Bob`, `Eve`, `Eve`;
 nops(C);

Os operadores teóricos de conjuntos (união) e (interseção) são representados em Maple pela escrita de seus nomes – union e intersect (em inglês), respectivamente.

 A := 1, 2, 3, 4, 5: B := 4, 5, 6, 7, 8:
 A union B;
 A intersect B;

Além disso, a diferença teórica de conjuntos é denotada pelo operador Maple minus.

 A minus B;

Vamos usar as operações para verificar o princípio de inclusão e exclusão em um exemplo particular.

 Flintstones := `Fred`, `Wilma`, `Pebbles`;
 Rubbles := `Barney`, `Betty`, `Bam Bam`;
 Husbands := `Fred`, `Barney`;
 Wives := `Wilma`, `Betty`;
 Kids := `Pebbles`, `Bam Bam`;

Se este fosse um censo completo, então o número de crianças morando em Bedrock seria

 nops(Kids);

enquanto que o número de habitantes de Bedrock que também são Flintstones ou criança é

 nops(Flintstones union Kids);

De acordo com o princípio de inclusão e exclusão, este número também deveria ser

 nops(Flintstones) + nops(Kids)
   - nops(Flintstones intersect Kids);

que, claro, que é!

Como outro exemplo, considere um problema de determinar o número de inteiros positivos menor ou igual a 1000 que não são divisíveis por 2 ou 111 ao mesmo tempo. Primeiro, nós geraremos um conjunto de inteiros positivos menor ou igual a 1000.

 hundred := seq(i, i = 1..1000):

Isto mostra como você pode usar o iterador Maple seq para gerar os membros de um conjunto. A seguir, vamos nos livrar dos elementos que são divisíveis por 2.

 A := hundred minus seq(2 * i, i = 1..1000):

E daqueles que são divisíveis por 7:

 B := hundred minus seq(7 * i, i = 1..1000):

(Perceba o uso combinado dos operadores seq e minus; eles trabalham bem convenientemente juntos aqui) Nós estamos procurando por inteiros que pertencem a um ou ambos de A e B, que é a união deles, então queremos o tamanho de um conjunto , o qual é nops(A union B);

De acordo com o princípio de inclusão e exclusão, este valor também pode ser computado como

 nops(A) + nops(B) - nops(A intersect B);

O mesmo princípio pode ser usado para exemplos maiores. Aqui, descrevemos o que precisa ser feito para determinar o número de inteiros positivos menor que 10.000 que são indivisíveis pelos primos 2, 3, 5 e 7. Para fazer isso, vamos usar o princípio da inclusão e exclusão para contar esses inteiros menor que 10000, que são divisíveis por, ao menos, um destes quatro números primos, e depois subtraí-los de 10000.

Primeiro, criamos um conjunto de inteiros positivos menor ou igual do que um mil.

 th := seq(i, i=1..10^3):

Agora, os inteiros menores que 10000 que são divisíveis por um dos 2, 3, 5 e 7 são os da união dos conjuntos

 th2 := th intersect seq(2*i, i=1..1000):
 th3 := th intersect seq(3*i, i=1..1000):
 th5 := th intersect seq(5*i, i=1..1000):
 th7 := th intersect seq(7*i, i=1..1000):

(Note que não temos que permitir o índice i para alcançar 10000 em cada um destes, mas é mais simples deste modo, uma vez que irá descartar os valores desnecessários por tomar a interseção).

A seguir, criamos conjunto de inteiros que são divisíveis por estes quatro primos em pares.

 th_2_3 := th intersect seq(2*3*i, i=1..1000):
 th_2_5 := th intersect seq(2*5*i, i=1..1000):
 th_2_7 := th intersect seq(2*7*i, i=1..1000):
 th_3_5 := th intersect seq(3*5*i, i=1..1000):
 th_3_7 := th intersect seq(3*7*i, i=1..1000):
 th_5_7 := th intersect seq(5*7*i, i=1..1000):

Contamos também os inteiros menores que 10000 que são divisíveis pelos números em triplas.

 th_2_3_5 := th intersect seq(2*3*5*i, i=1..1000):
 th_2_3_7 := th intersect seq(2*3*7*i, i=1..1000):
 th_2_5_7 := th intersect seq(2*5*7*i, i=1..1000):
 th_3_5_7 := th intersect seq(3*5*7*i, i=1..1000):

Finalmente, contamos os números menores que 10000 que são divisíveis por todos os quatro número 2, 3, 5 e 7. th_2_3_5_7 := th intersect seq(2*3*5*7*i, i=1..1000): Agora, para calcular os números inteiros menores que 10000 que são divisíveis por pelo menos um dos 2, 3, 5 e 7, nós calculamos como se segue.

 nops(th2) + nops(th3) + nops(th5) + nops(th7);
 % - (nops(th_2_3) + nops(th_2_5) + nops(th_2_7));
 % - (nops(th_3_5) + nops(th_3_7) + nops(th_5_7));
 % + (nops(th_2_3_5) + nops(th_2_3_7) + nops(th_2_5_7));
 % + nops(th_3_5_7) - nops(th_2_3_5_7);

Portanto, o número de inteiros menores que 10000 que não são divisíveis por 2, 3, 5 ou 7 é

 1000 - %;

4. Funções geradoras

Funções geradoras são ferramentas poderosas para modelar conjuntos de objetos e suas construções. Por exemplo, se um conjunto de objetos é construído a partir de dois outros através da realização de um produto cartesiano de dois conjuntos subjacentes, em seguida, a função geradora para o novo conjunto é muitas vezes apenas o produto das funções geradoras pelos dois conjuntos subjacentes. Assim, saber como um conjunto é construído pode nos ajudar a construir a sua função geradora.

Se você pensar nas funções geradoras como polinômios, em seguida, cada objeto do conjunto original está representado nesta expansão do produto dos dois polinômios por um monômio como $x^{5}$. Várias combinações diferentes pode levar a um $x^{5}$. O coeficiente de $x^{5}$ na função geradora expandido indica o número de tais objetos no novo conjunto.

Os coeficientes da função geradora expandida forma uma sequência de números - o número de objetos em seu conjunto de cada tamanho. Assim, muitas vezes nos referimos a uma função geradora como a função geradora para a sequência --- seus coeficientes. Em particular, tais sequências também podem ser descritas por relações de recorrência. Aqui, vamos discutir como usar as funções geradoras para nos ajudar a resolver essas relações de recorrência.

A função geradora $g(x)$ para uma sequência Failed to parse (syntax error): {\displaystyle {\ r_ {{n} \}} é a série de potência formal

$\ sum_{k=0}^{\ infty}r_{k}x^{k}=r_{0}+r_{1}x+r_{2}x^{2}+r_{3}x^{3}+\ cdots+r_{n}x^{n}+\ cdots$

Ele é chamado formal, porque não estamos mesmo interessados em avaliá-lo como uma função de x. Todo o nosso foco está em encontrar fórmulas para seus coeficientes. Em particular, isto significa que não há problemas de convergência a serem investigados.

Maple fornece extensas habilidades para a manipulação de séries de potências formais (ou seja, as funções geradoras). Pertencem ao pacote powseries do Maple, de modo que parar acessa-las, você deve carregar este pacote.

 with (powseries);

A primeira coisa que precisamos fazer é aprender a criar uma série de potência. Para isso, o Maple fornece a função powcreate. Ela toma como argumentos uma sequência de equações que definem o coeficiente geral. As equações especificam uma maneira de calcular o coeficiente kth em $\ sum_{k=0}^{\ infty}a_{k}x^{k}$. Por exemplo, a função exponencial formal, o que tem de representação de série de potência

$\ exp(s)=\ sum_{n=0}^{\ infty}\ frac{s^{n}}{n!}$

pode ser criado em Maple emitindo a chamada

 powcreate (e (n) = 1 / N!);

O que torna isto especialmente útil para trabalhar com relações de recorrência é que o coeficiente geral não precisa ser especificado na forma fechada (como foi acima). Você pode especificar uma relação de recorrência satisfeita com os coeficientes, em conjunto com suficientemente muitas condições iniciais para garantir uma solução única para a recorrência.

Vamos ver um exemplo disso. Para criar a função geradora para a sequência de Fibonacci, a qual é definida pela relação de recorrência

$F_{n}=F_{n-1}+F_{N-2}\ hspace{3EX}\ mbox{e}\ hspace{3EX}F(0)=1,F(1)=1$

podemos entrar

 powcreate (f (n) = f (n - 1) + f (n - 2), F (0) = 1, F (1) = 1);

Agora, a única informação interessante em uma função geradora é a sequência de seus coeficientes. Maple fornece uma maneira de acessar um coeficiente arbitrário em uma série de potências formais. Isto é feito como se segue. Para Maple, cada série de potências formais é, na verdade, um procedimento, que leva argumentos inteiros. O valor retornado por uma série de potências formais, quando dado um inteiro n como argumento é o coeficiente de $x^{n}$ . Assim, por exemplo, o quinto número de Fibonacci pode ser produzido chamando a série de potências formais f acima com '5' como argumento.

 f (5);

De fato, o coeficiente geral pode ser obtido fazendo passar o argumento especial _k

 F (_K);

Para exibir uma função geradora, é melhor usar a função tpsform do Maple. Esse procedimento converte uma série de potências formal sobre uma série de potência truncada de grau especificado. Por exemplo, para exibir os dez primeiros termos da função geradora para a nossa sequência de Fibonacci, podemos usar tpsform, como se segue.

 tpsform (F, X, 9);

Funções geradoras são mais do que apenas uma forma conveniente para representar sequências numéricas e seus conjuntos de objetos associados. Eles são uma ferramenta poderosa para a solução de relações de recorrência, bem como outros tipos de problemas de contagem. Este poder deriva de nossa capacidade de manipulá-los, mais ou menos, como séries de potência comuns de Cálculo e de interpretar essas manipulações em termos de sua ação sobre os conjuntos.

Assim como é feito em Cálculo com a série de potência comum, funções geradoras podem ser adicionadas, multiplicadas, multiplicadas por escalares e polinômios, compostas, avaliadas e mesmo diferenciadas e integradas. É importante reconhecer que estamos falando aqui de diferenciação formal e integração --- não há limites para se preocupar.

É ainda mais importante, associar estas operações algébricas com operações combinatórias que você pode realizar no conjunto de objetos implicitamente representadas pela função geradora. Por exemplo, considerando a união de dois conjuntos disjuntos de objetos corresponde a adição de suas funções geradoras. Cada uma das operações são muitas vezes melhor pensadas em termos do seu efeito sobre os monômios que representam os objetos individuais do conjunto subjacente de objetos. Por exemplo, se um único objeto feito de de cinco sub-objetos é representado por $x^{5}$, então existem exatamente 5 maneiras de escolher uma dessas sub-objetos para remoção. O conjunto de objetos produzidos através disso de todas as maneiras possíveis seriam representados por $5x^{4}$. Assim, em um sentido muito real, esta operação combinatória de dividir um único objeto desta forma corresponde à operação conhecida de diferenciação em sua função geradora.

Todas as operações mais comuns que você pode realizar em séries de potência comum têm interpretações combinatórias úteis e podem ser realizadas em nossas séries de potência formal. Em cada caso, pode especificar o que tal efeito terá sobre o coeficiente da série. Maple fornece habilidades para a realização de todas estas manipulações, e muito mais.

Estas habilidades são melhor demonstradas pelo trabalhar através de um exemplo. Usaremos Maple para resolver a recorrência Fibonacci com funções geradoras.

Se multiplicarmos ambos os lados da recorrência Fibonacci

$F_{n}=F_{n-1}+F_{N-2}$ por $x^{n}$, obtemos

$F_{n}x^{n}=f_{n-1}x^{n}+f_{n-2}x^{n}$

Agora soma de n = 1 rende

$\ sum_{n=1}^{\ infty}f_{n}x^{n}=\ sum_{n=1}^{\ infty}f_{n-1}x^{n}+\ sum_{n=1}^{\ infty}{f_{n}-2}x^{n}$

O lado esquerdo desta equação difere da função geradora apenas o primeiro termo (em que n = 0), e as somas no lado direito podem ser fatoradas, assim que obtemos

$g(x)-1=XG(x)+x^{2}g(x)$

Agora, resolver esta equação para g (x) produz

$g(x)=\ frac{-1}{x^{2}+x-1}$