31
edits
Changes
Jump to navigation
Jump to search
Técnicas Avançadas de Contagem (view source)
Revision as of 09:32, 2 December 2015
, 09:32, 2 December 2015no edit summary
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
<math> F_ {n} = F_ {n-1} + F_ {N-2} \ hspace {3EX} \ mbox {e} \ hspace {3EX} F (0) = 1, F (1) = 1 </math>
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 seqüência de seus coeficientes. Maple fornece uma maneira de acessar um coeficiente arbitrário em uma série de potências formal. Isto é feito como se segue. Para Maple, cada série de potências formal é, na verdade, um procedimento, que leva argumentos inteiros. O valor retornado por uma série de potências formal, quando dado um inteiro n como argumento é o coeficiente de <math> x ^ {n}</math> . Assim, por exemplo, o quinto número de Fibonacci pode ser produzido chamando a série de potência formal 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 seqüê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 <math> x ^ 5</math>, 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 <math>5 x ^ 4</math>. 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.
