Qual é a função generalizada para a seqüência \left\{c_{k}\right\}, em que c_{k} representa o número de maneiras de organizar trocos para k pesos usando notas de 10,20,50 e 100 pesos?

Passo 1

O enunciado pede a função geradora da sequência \{c_k\}, onde c_k é o número de maneiras de trocar k pesos usando notas de 10, 20, 50 e 100 pesos. O conteúdo envolvido é teoria de funções geradoras (séries de potência) e vamos usar que, para objetos independentes, a função geradora total é o produto das funções geradoras individuais.

Passo 2

Cada tipo de nota pode aparecer 0,1,2,\dots vezes, gerando uma série geométrica. Para a nota de 10 pesos:
\sum_{n=0}^{\infty}x^{10n} \;=\;\frac{1}{1 - x^{10}}.
De modo análogo, para as notas de 20, 50 e 100 pesos, temos as funções geradoras
\frac{1}{1 - x^{20}},\quad \frac{1}{1 - x^{50}},\quad \frac{1}{1 - x^{100}}.

Passo 3

Pela regra do produto para séries de potência (itens independentes), a função geradora que reúne todas as possibilidades é
G(x)\;=\;\sum_{k=0}^{\infty}c_k\,x^k \;=\;\frac{1}{(1 - x^{10})(1 - x^{20})(1 - x^{50})(1 - x^{100})}.

Resposta

G(x)=\sum_{k=0}^{\infty}c_k\,x^k =\frac{1}{(1 - x^{10})(1 - x^{20})(1 - x^{50})(1 - x^{100})}.

Exercícios de Livros Relacionados