Generalizacao

Prévia do material em texto

MA220 1oSEM-2019 F unções geradoras — Antonio Fornari & Gabriel Félix
Fórmulas importantes:
(1 + xα)N =
∑N
R=0
(
N
R
)
xαR
1
(1− xα)N
=
∑∞
S=0
(
N + S − 1
S
)
xαS
1 + x+ x2 + x3 + ...+ xN =
1− xN+1
1− x
Problema 1: De quantas formas podemos lançar D dados com F faces e obter o valor
N como soma?
Escrevendo a função geradora de cada dado di com F faces, temos que:
F (di) = x
1 + x2 + x3 + x4 + ...xF
Como o nosso problema envolve D dados, temos que a FG é dada por:
FG = (x+ x
2 + x3 + ...+ xF )D = xD(1 + x+ x2 + ...+ xF−1)D
= xD ·
[
1− xF
1− x
]D
= xD ·
N∑
r=0
(−1)r
(
D
R
)
xrF ·
∞∑
S=0
(
D + S − 1
S
)
xS
Como queremos a quantidade de formas de obter o valor N como soma, precisamos dos
coeficientes xN , dessa forma percebemos pela expressão acima que os termos de grau N são
obtidos quando F · r + S = N −D ⇐⇒ S = N −D − rF
Coefs(XN) =
N∑
r=0
(−1)r
(
D
r
)(
D + S − 1
S
)
=
N∑
r=0
(−1)r
(
D
r
)(
D + (N −D − rF )− 1
N −D − rF
)
=
N∑
r=0
(−1)r
(
D
r
)(
N − rF − 1
N −D − rF
)
Portanto, temos que a expressão que nos diz o número de possibilidades de obter a soma
N com D dados de F faces é:
Coefs(XN) =
N∑
r=0
(−1)r
(
D
r
)(
N − rF − 1
D − 1
)
MA220 1oSEM-2019 F unções geradoras — Antonio Fornari & Gabriel Félix
Problema 1: Quantas bandeiras de n cent́ımetros podemos formas com x cores de 1cm
e y cores de 2 cm?
Tamanho n # de possibilidades possibilidades
1 cm x x1, x2, x3, ..., xx
2 cm x2 + y
x1x1, x1x2, x1x3....xxxx
y1y1, y2y2, y3y3, ...yyyy
... cm ... ...
Analisando a tabela acima e representando cada cor de bandeira como um termo na
relação de recorrência, temos que:
Rn = xCn−1 + yCn−2
Em que o termo κ ·Cn−t representa κ possibilidades de pegar uma bandeira de t cent́ımetros
(e.g. x · Cn−1: x possibilidades de bandeiras com 1 cm).
Sabendo que toda fórmula de recorrência do tipo F(n) = βF(n−1) + γ(F(n−2)) tem solução
F(n) = Aα
n
1 +Bα
n
2 , tal que α1 + α2 = β e α1 · α2 = −γ, vamos obter os valores de α1 e α2
α2 = xα + y ⇐⇒ α2 − xα− y = 0 ⇐⇒ α1,2 =
x±
√
x2 + 4y
2
Pegando as ráızes α1 e α2, temos a relação de recorrência:
Cn = A
(
x+
√
x2 + 4y
2
)n
+B
(
x−
√
x2 + 4y
2
)n
Das condições iniciais, C1 e C2, temos que:
C1 = (A+B)
x
2
+ (A−B)
(√
x2 + 4y
2
)
= x
C2 = x
[
(A+B)
x
2
+ (A−B)
(√
x2 + 4y
2
)]
+ (A+B)y = x2 + y
Substituindo x de C1 em C2, temos que:
C2 = x
2 + (A+B)y = x2 + y
Logo, para equação acima ser verdadeira A+B = 1, que substituindo em C1, temos que:
C1 =
x
2
+ (2A− 1)
√
x2 + 4y
2
= x ⇐⇒ A = x+
√
x2 + 4y
2
√
x2 + 4y
e B = −x+
√
x2 + 4y
2
√
x2 + 4y
Com os valores de A e B em C(n), temos que a solução generalizada é dada por:
Cn =
(x+
√
x2 + 4y)n+1 − (x−
√
x2 + 4y)n+1
2n+1 ·
√
x2 + 4y