15c - Funções Geradoras - Exercícios

Prévia do material em texto

15/30/2019 1Funções Geradoras - Exercícios
Professor: Luiz Augusto Laranjeira
luiz.laranjeira@gmail.com
AULA 15c
Matemática Discreta 1
Funções Geradoras - Exercícios
5/30/2019 2Funções Geradoras
Teorema 5.1 - Recordação
Teorema 5.1
Sendo f(x) e g(x) as funções geradoras das sequências (ar) e (br) 
respectivamente, temos:
i. Af(x) + Bg(x) é a função geradora para a sequência (Aar + Bbr)
ii. f(x)g(x) = 𝑎0𝑏0 + 𝑎0𝑏1 + 𝑎1𝑏0 𝑥 + 𝑎0𝑏2 + 𝑎1𝑏1 + 𝑎2𝑏0 𝑥
2 +⋯+
+ 𝑎0𝑏𝑛 + 𝑎1𝑏𝑛−1 +⋯+ 𝑎𝑛𝑏0 𝑥
𝑛
= σ𝑛=0
∞ σ𝑘=0
𝑛 (𝑎𝑘𝑏𝑛−𝑘) 𝑥
𝑛
iii. A função geradora para a sequência 𝑎0 + 𝑎1 + 𝑎2 +⋯+ 𝑎𝑟 é igual a
1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 +⋯ 𝑓(𝑥)
iv. A função geradora para (rar) é igual a xf’(x), onde f’(x) é a derivada de f(x) em relação a x.
v. ׬𝑓 𝑥 𝑑𝑥 = σ𝑛=0
∞ 𝑎𝑛
𝑛+1
𝑥𝑛+1
5/30/2019 3Funções Geradoras
Teorema 5.1 – Recordação (cont.)
Vamos focar nos itens (ii) e (iii):
ii. f(x)g(x) = 𝑎0𝑏0 + 𝑎0𝑏1 + 𝑎1𝑏0 𝑥 + 𝑎0𝑏2 + 𝑎1𝑏1 + 𝑎2𝑏0 𝑥
2 +⋯+
+ 𝑎0𝑏𝑛 + 𝑎1𝑏𝑛−1 +⋯+ 𝑎𝑛𝑏0 𝑥
𝑛
= σ𝑛=0
∞ σ𝑘=0
𝑛 (𝑎𝑘𝑏𝑛−𝑘) 𝑥
𝑛
Fazendo 𝑏𝑟 = 1, isto é, 𝑔 𝑥 =
1
1−𝑥
= 1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 +⋯ , teremos
ℎ 𝑥 = 𝑓 𝑥 𝑔(𝑥) = σ𝑟=0
∞ σ𝑘=0
𝑟 (𝑎𝑘𝑏𝑟−𝑘) 𝑥
𝑟 = σ𝑟=0
∞ σ𝑘=0
𝑟 𝑎𝑘 𝑥
𝑟 e
ℎ 𝑥 = 𝑓 𝑥 𝑔 𝑥 = 𝑓(𝑥) 1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 +⋯ e
𝑐𝑟 = 𝑎0 + 𝑎1 + 𝑎2 +⋯+ 𝑎𝑟 onde cr é a sequência gerada por h(x).
Isto, portanto, já demonstra o item (iii) seguinte.
iii. A função geradora para a sequência 𝑎0 + 𝑎1 + 𝑎2 +⋯+ 𝑎𝑟 é igual a
1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 +⋯ 𝑓(𝑥)
5/30/2019 4Funções Geradoras - Exercícios
Exercício 1 – Exemplo 5.25 do Livro
5/30/2019 5Funções Geradoras - Exercícios
Exercício 1 – Exemplo 5.25 do Livro
Temos dois termos no 
coeficiente dexn no produto
(𝑥2 + 𝑥)(1 − 𝑥)−4:
Um termo é o coeficiente 
do produto de 𝑥2 e o termo 
em 𝑥𝑛−2 de (1 − 𝑥)−4;
O outro termo será o 
coeficiente do produto de 
𝑥 e o termo em 𝑥𝑛−1 de 
(1 − 𝑥)−4.
𝒓 = 𝒏 − 𝟏 𝒓 = 𝒏 − 𝟐
5/30/2019 6Funções Geradoras - Exercícios
Exercício 2
Encontrar afunçãogeradoraordinária𝒉 𝒙 paraasequência
𝒄𝒓 =𝟏+𝟐+𝟐
𝟐+𝟐𝟑+⋯+𝟐𝒓
[Exercício 18, Cap. 5 do Livro]
5/30/2019 7Funções Geradoras - Exercícios
Exercício 2
Encontrar afunçãogeradoraordinária𝒉 𝒙 paraasequência
𝒄𝒓 =𝟏+𝟐+𝟐
𝟐+𝟐𝟑+⋯+𝟐𝒓
Usando o Teorema 5.1, item iii, entendemos que precisamos encontrar a função geradora
𝑓 𝑥 =1+2𝑥+22𝑥2+23𝑥3+⋯+2𝑟𝑥𝑟+⋯ com 𝑎𝑟 =2
𝑟
e multiplicá-la pela função 𝑔 𝑥 =
1
1−𝑥
= 1+𝑥+𝑥2+𝑥3+⋯+𝑥𝑟+⋯ com 𝑏𝑟 =1
para encontrarmos ℎ 𝑥 =𝑓 𝑥 g 𝑥 .
Com o objetivo de encontrar 𝑓 𝑥 lembramos que
1
1−𝑥
= 1+𝑥+𝑥2+𝑥3+⋯+𝑥𝑟+⋯
e substituindo 2𝑥 em lugar de 𝑥 obtemos
1
1−2𝑥
=1+2𝑥+(2𝑥)2+(2𝑥)3+⋯+ 2𝑥 𝑟+⋯=𝑓 𝑥
Daí concluimos que 𝒉 𝒙 =
𝟏
(𝟏−𝟐𝒙)
×
𝟏
(𝟏−𝒙)
5/30/2019 8Funções Geradoras - Exercícios
Exercício 3
Encontrar ocoeficiente 𝒙𝟐𝟕 em (𝒙𝟑+𝒙𝟒 + 𝒙𝟓 +⋯). [Exercício 4, Cap. 5 do Livro]
5/30/2019 9Funções Geradoras - Exercícios
Exercício 3
Encontrarocoeficientede𝒙𝟐𝟕 em (𝒙𝟑+𝒙𝟒 + 𝒙𝟓 +⋯)𝟔. [Exercício 4, Cap. 5 do Livro]
Este problema pode ser traduzido por encontrar o número de soluções em inteiros
não-negativos da equação:
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 = 27
com a restrição que 𝑥𝑖 ≥ 3.
Fazendo 𝑥𝑖 = 𝑦𝑖 + 3 temos:
𝑦1 + 𝑦2 + 𝑦3 + 𝑦4 + 𝑦5 + 𝑦6 = 27 − 18 = 9 com 𝑦𝑖 ≥ 0
O número de soluções 𝑁 desta equação é o coeficiente procurado.
𝑵 = 𝑪𝟗
𝟗+𝟔−𝟏 = 𝑪𝟗
𝟏𝟒
5/30/2019 10Funções Geradoras - Exercícios
Exercício 4
Encontrar o número de maneiras de se obter um total de 15 pontos ao se jogar,
simultaneamente,4dadosdiferentes. [ Exercício 5, Cap. 5, Livro ]
5/30/2019 11Funções Geradoras - Exercícios
Exercício 4
Encontrar o número de maneiras de se obter um total de 15 pontos ao se jogar,
simultaneamente,4dadosdiferentes. [ Exercício 5, Cap. 5, Livro ]
Neste problema precisamos encontrar o coeficiente de 𝑥𝑟 na expressão
(𝑥𝑞+𝑥𝑞+1 + 𝑥𝑞+2 +⋯𝑥𝑞+𝑧−1)𝑛 = 𝑥𝑛𝑞
1−𝑥𝑧
1−𝑥
𝑛
que é igual ao coeficiente de 𝑥𝑟−𝑛𝑞 em 
1−𝑥𝑧
1−𝑥
𝑛
.
No nosso caso 𝑛 = 4 (dados) e 𝑟 = 15 (pontos). Como em um dado os números vão
de 1 a 6 temos que 𝑞 = 1, 𝑞 + 𝑧 − 1 = 6, donde 𝑧 = 6, e 𝑟 − 𝑞𝑛 = 15 − 1.4 = 11.
Queremos o coeficiente de 𝑥11 em 
1−𝑥6
1−𝑥
4
. Para isto temos que:
1 − 𝑥6
4
= 1 − 4𝑥6 + 6𝑥12 − 4𝑥18 + 𝑥24
1−𝑥 −4 =෍
𝑟=0
∞
−4
𝑟
(−1)𝑟𝑥𝑟 = 1 +
4
1!
𝑥 +
4.5
2!
𝑥2 +
4.5.6
3!
𝑥3 +⋯
5/30/2019 12Funções Geradoras - Exercícios
Exercício 4 (cont.)
Queremos o coeficiente de 𝑥11 em 
1−𝑥6
1−𝑥
4
. Para isto temos que:
1 − 𝑥6
4
= 1 − 4𝑥6 + 6𝑥12 − 4𝑥18 + 𝑥24
1−𝑥 −4 =෍
𝑟=0
∞
−4
𝑟
(−1)𝑟𝑥𝑟 = 1 +
4
1!
𝑥 +
4.5
2!
𝑥2 +
4.5.6
3!
𝑥3 +⋯
Vemos que o coeficiente de 𝑥11 só terá dois termos:
1 ×
4.5.6.7.8.9.10.11.12.13.14
11!
𝑥11 − 4𝑥6 ×
4.5.6.7.8
5!
𝑥5 = 364 − 224 𝑥11 = 140𝑥11
O valor do coeficiente desejado é 140
5/30/2019 13Funções Geradoras - Exercícios
Exercício 5
Quantas soluções possui a equação 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 +⋯+ 𝒙𝒏 = 𝒓 se cada
variáveléiguala0ou1?
5/30/2019 14Funções Geradoras - Exercícios
Exercício 5
Quantas soluções possui a equação 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟑 +⋯+ 𝒙𝒏 = 𝒓 se cada
variáveléiguala0ou1? [ Exercício 11, Cap. 5 do Livro ]
A função geradora correspondente a esta equação é 1+𝑥 𝑛 que pelo Teorema do
Binômio é igual a σ𝑘=0
𝑛 𝑛
𝑘
1𝑘𝑥𝑛−𝑘.
Queremos o coeficiente de 𝑥𝑟 deste desenvolvimento, o que nos dá 𝑘 = 𝑛 − 𝑟.
Este coeficiente será igual a 𝑪𝒏−𝒓
𝒏 = 𝑪𝒓
𝒏
5/30/2019 15Funções Geradoras - Exercícios
Exercício 6
Nove novos técnicos são contratados por uma cia. telefônica. De quantas
maneiras pode ela alocá-los em quatro diferentes escritórios dado que um
dado escritório pode não receber nenhum técnico? [ Exercício14b,Cap.5doLivro ]
5/31/2019 16Funções Geradoras - Exercícios
Exercício 6
Nove novos técnicos são contratados por uma cia. telefônica. De quantas
maneiras pode ela alocá-los em quatro diferentes escritórios dado que um
dado escritório pode não receber nenhum técnico?
Usamos a função geradora exponencial pois os técnicos são diferentes, isto é, a distribuição { 4, 3,1, 1 }
pode ser realizada de várias maneiras permutando-se os técnicos. O número máximo de técnicos
queumescritóriopodereceberé9.Assim,a funçãogeradoraparaesteproblemaédadapor:
𝑓 𝑥 = 1 +
𝑥1
1!
+
𝑥2
2!
+
𝑥3
3!
+
𝑥4
4!
+
𝑥5
5!
+
𝑥6
6!
+
𝑥7
7!
+
𝑥8
8!
+
𝑥9
9!
4
Earespostaéocoeficientede
𝑥9
9!
em f(x),queéigualaocoeficientede
𝑥9
9!
nafunçãog(x) quesesegue
𝑔 𝑥 = 1 +
𝑥1
1!
+
𝑥2
2!
+
𝑥3
3!
+⋯+
𝑥9
9!
+⋯
4
= 𝑒𝑥 4 = 𝑒4𝑥
𝑒4𝑥 = 1 + 4𝑥 +
(4𝑥)2
2!
+
(4𝑥)3
3!
+
(4𝑥)4
4!
+ ⋯+
4𝑥 9
9!
+ ⋯+
(4𝑥)𝑟
𝑟!
+ ⋯
É fácil ver que o coeficiente buscado é igual a 𝟒𝟗 = 𝟐𝟔𝟐𝟏𝟒𝟒
5/30/2019 17Funções Geradoras - Exercícios
Exercício 7
Quantas n-uplas de 0’s e 1’s podem ser formadas usando-se um número
par de 0’se um número par de 1’s? [Exercício 13,Cap.5doLivro ]
5/30/2019 18Funções Geradoras - Exercícios
Exercício 7
Quantas n-uplas de 0’s e 1’s podem ser formadas usando-se um número
par de 0’se um número par de 1’s? [Exercício13,Cap.5doLivro ]
A função geradora exponencial para o número de dígitos 0 e o número de dígitos 1 é:
1 +
𝑥2
2!
+
𝑥4
4!
+ ⋯+
𝑥2𝑟
2𝑟 !
+ ⋯ =
1
2
𝑒𝑥 + 𝑒−𝑥
E a função geradora exponencial para o problema fica:
1
4
𝑒𝑥 + 𝑒−𝑥 2 =
1
2
+
1
4
𝑒2𝑥 +𝑒−2𝑥
1
2
+
1
4
𝑒2𝑥+𝑒−2𝑥 =
1
2
+
1
4
σ𝑟=0
∞ (2𝑥)
𝑟
𝑟!
+σ𝑟=0
∞ (−2𝑥)
𝑟
𝑟!
= 1+
1
4
σ𝑟=1
∞ (2𝑥)
𝑟
𝑟!
+σ𝑟=1
∞ (−2𝑥)
𝑟
𝑟!
= 1 +
1
22
21
𝑥1
1!
−21
𝑥1
1!
+22
𝑥2
2!
+22
𝑥2
1!
+21
𝑥3
1!
−21
𝑥3
1!
+22
𝑥4
2!
+22
𝑥4
1!
+⋯
= 1 + 21
𝑥2
2!
+23
𝑥4
4!
+25
𝑥6
6!
+27
𝑥8
8!
+…+2𝑛−1
𝑥𝑛
𝑛!
+⋯ onde 𝑛 é par
O no de de n-uplas desejado é o coeficiente de
𝑥𝑛
𝑛!
na função acima que é: 𝟐𝒏−𝟏,𝒏 par
5/30/2019 19Funções Geradoras - Exercícios
Exercício 8
Quantas n-sequências quaternárias podem ser formadas usando-se um
número par de 0’se um número par de 1’s? [Exercício 20,Cap.5doLivro ]
5/31/2019 20Funções Geradoras - Exercícios
Exercício 8
Quantas n-sequências quaternárias podem ser formadas usando-se um
número par de 0’se um número par de 1’s? [Exercício 20,Cap.5doLivro ]
No exercício 7 vimos que a função geradora exponencial para o no de dígitos 0 e 1 é:
1 +
𝑥2
2!
+
𝑥4
4!
+ ⋯+
𝑥2𝑟
2𝑟 !
+ ⋯ =
1
2
𝑒𝑥 + 𝑒−𝑥
Afunção geradora exponencial para o número de dígitos 2 e 3 é dada por:
1 +
𝑥1
1!
+
𝑥2
2!
+
𝑥3
3!
+
𝑥4
4!
+ ⋯+
𝑥𝑟
𝑟!
+ ⋯ = 𝑒𝑥
Portanto a função geradora exponencial𝑓 𝑥 para o problema será:
𝑓 𝑥 =
1
2
𝑒𝑥 + 𝑒−𝑥
2
𝑒2𝑥 =
1
2
+
1
4
𝑒2𝑥 + 𝑒−2𝑥 𝑒2𝑥 =
1
2
𝑒2𝑥 +
1
4
𝑒4𝑥 +
1
4
5/31/2019 21Funções Geradoras - Exercícios
Exercício 8 (cont.)
Afunção geradora exponencial𝑓 𝑥 para o problema é:
𝑓(𝑥) =
1
2
𝑒2𝑥 +
1
4
𝑒4𝑥 +
1
4
Sendo
𝑒2𝑥 = 1 + 2𝑥 +
(2𝑥)2
2!
+
(2𝑥)3
3!
+
(2𝑥)4
4!
+ ⋯+
2𝑥 9
9!
+ ⋯+
(2𝑥)𝑟
𝑟!
+ ⋯
𝑒4𝑥 = 1 + 4𝑥 +
(4𝑥)2
2!
+
(4𝑥)3
3!
+
(4𝑥)4
4!
+ ⋯+
4𝑥 9
9!
+ ⋯+
4𝑥 𝑟
𝑟!
+ ⋯
o coeficiente de
𝑥𝑟
𝑟!
em 𝑓 𝑥 será dado por:
𝟐𝒓
𝟐
+
𝟒𝒓
𝟒
=
(𝟒𝒓+𝟐𝒓+𝟏)
𝟒
5/30/2019 22Funções Geradoras - Exercícios
Tabela de Funções Geradoras 
5/30/2019 23Funções Geradoras - Exercícios
Tabela de Funções Geradoras (cont.)