INTRODUÇÃO A
FUNÇÕES GERATRIZES
Nos seguintes exercícios, an é uma sequência, e
X
an xn
A(x) =
n≥0
é a função geratriz correspondente.
Exercício 1. Calcule A(x) para as seguintes sequências:
(1) an = 1
(2) an = n
(3) an = 2n
n
(4) an = 3 ×
2 +1
n
(5) an = k
Exercício 2. Calcule A(x), para as seguintes sequências, e ache uma “fórmula fechada” para an .
(1) an = 2an−1 + 1, a0 = 1
(2) an = 2an−1 + n, a0 = 1
(3) an+2 = an+1 + an , a0 = a1 = 1
(4) an+2 = 3an+1 − 2an , a0 = 2, a1 = 5
Exercício 3. Seja
A(x) =
X
an xn
n≥0
B(x) =
X
bn xn
n≥0
Calcule B(x) como uma função de A(x) se
(1) bn = 2an
(2) bn = an + 3
(3) bn = 2n an
(4) bn = an+1 − an
(5) bn = an+3
(6) bn = nan
Exercício 4. Seja f1 , f2 , . . . a sequência definida por
(a) f1 = 1
(b) f2n = fn
(c) f2n+1 = fn + fn+1
Seja
X
F (x) =
fn xn−1
n≥1
Date: Quarta Feira, 20 de Junho de 2012.
1
2
G. BUJOKAS
Mostre que
F (x) =
∞ Y
j
j+1
1 + x2 + x2
j≥0
Exercício 5. Se p(n) é o número de partições de n, então
Y
X
1
p(n)xn =
1 − xn
n≥1
n≥0
1. Técnicas um pouco mais avançadas
P
Lema 1.1 (Produto). Se cn = i+j=n ai bj , então



X
X
X
bn xn 
an xn  
cn xn = 
n≥1
n≥1
n≥1
Exercício 6. Lembre que a sequência de Catalan Cn satisfaz
X
Cn+1 =
Ci Cn−i e C0 = 1
i
Calcule
C(x) =
X
Cn x n
Lema 1.2 (Binômio de Newton). Para qualquer α,
X α
α
(1 + x) =
xk
k
k≥0
Exercício 7. Mostre que
X 2n
1
xn = (1 − 4x)− 2
n
n≥0
Exercício 8. Ache uma fórmula fechada para a sequência de Catalan Cn .
Exercício 9. Mostre que, para n ≥ 0,
n X
2k
2(n − k)
= 4n
k
n−k
k=0
Lema 1.3 (Filtrar expoentes mod k). Se
X
A(x) =
an xn
n≥0
e χ = e2πi/k , então
k−1
X
1X
A(χi x) =
an xn
k
i=0
k|n
Exercício 10. Seja p um número primo ímpar. Calcule o número de subconjuntos de {1, 2, . . . , p} tal que a soma dos elementos divisível por p.
FUNÇÕES GERATRIZES
3
2. Mais exercícios
Exercício 11. Demonstre as seguintes identidades.
X k = Fn+1 , onde Fn é a sequência de Fibonacci.
n−k
k≥0
X n + k 2k (−1)k
n−1
=
m + 2k
k k+1
m−1
k
X n+k
22n+1 + 1
2n−k =
, para n ≥ 0
3
2k
k
X mn + k X mn
2k
=
k
k
k
m
k
k
X n2 2n
=
k
n
k
X 2n + 1 m + k 2m + 1
=
2k
2n
2n
k
X n k
n j
xk =
x (1 + x)n−j
j
j
k
k
Exercício 12. Mostre que
X
a1 a2 . . . ak = F2n
onde a soma é sobre todas as composições a1 +. . .+ak = n, e F• é a sequência
de Fibonacci.
Exercício 13. Mostre que
X
(2a1 −1 − 1) . . . (2ak −1 − 1) = F2n−2
onde a soma é sobre todas as composições a1 + . . . + ak = n.
Exercício 14. Mostre que
X
2{#i | ai =1} = F2n+1
onde a soma é sobre todas as composições a1 + . . . + ak = n.
3. Onde aprender mais
Uma boa introdução é o livro generatingfunctionology, do Herbert S.
Wilf. Tem uma edição de graça disponível na internet. Muitos dos problemas
acima são desse livro.
Um texto mais avançado é o excelente Enumerative Combinatorics do
Richard Stanley.
E-mail address: [email protected]