FUNÇÕES GERATRIZES II
Vamos relembrar o que a gente fez semana passada. Dada uma sequência
fn , nós associamos a série
F (x) = f0 + f1 x + f2 x2 + . . .
Por exemplo, se fn é a sequência de Fibonacci, definida por
(1) f0 = f1 = 1
(2) fn+2 = fn+1 + fn , para n ≥ 0.
então
1
1 − x − x2
A gente pode reinterpretar essa identidade como
X
1
=
(x + x2 )k
1 − (x + x2 )
k≥0
X
X
=
xa1 +a2 +...+ak
F (x) =
k≥0 a1 ,a2 ,...,ak ∈{1,2}
Portanto
Fn = #{a1 + a2 + . . . + ak = n | ai ∈ {1, 2}}
que é a interpretação usual dos números de Fibonacci: Fn é o número de
maneiras de preencher um tabuleiro 2 × n com dominós.
Exercício 1. 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 2. Mostre que
X
(2a1 −1 − 1) . . . (2ak −1 − 1) = F2n−2
onde a soma é sobre todas as composições a1 + . . . + ak = n.
Exercício 3. Mostre que
X
2{#i | ai =1} = F2n+1
onde a soma é sobre todas as composições a1 + . . . + ak = n.
Date: Terça Feira, 26 de Junho de 2012.
1
2
G. BUJOKAS
1. Filtrando os expoentes
Lema 1.1 (Filtrar expoentes mod k). Se
X
an xn
A(x) =
n≥0
e χ = e2πi/k , então
k−1
X
1X
an xn
A(χi x) =
k
i=0
k|n
Exemplo 1.1. Seja p um número primo ímpar. Vamos calcular o número de
subconjuntos de {1, 2, . . . , p} tal que a soma dos elementos divisível por p.
Considere
X
ak xk
F (x) = (1 + x)(1 + x2 ) . . . (1 + xp ) =
k≥0
Observe que ak é igual ao número de subconjuntos de {1, 2, . . . , p} com
soma k. Nós queremos calcular a0 + ap + a2p .
Seja ω = e
2πi
p
. Então
1
F (1) + F (ω) + . . . + F (ω p−1 )
p
Agora, F (1) = (1 + 1)(1 + 1) . . . (1 + 1) = 2p . E, para i = 1, . . . , p − 1,
a0 + ap + a2p =
F (ω i ) = (1 + ω i )(1 + ω 2i ) . . . (1 + ω pi )
= (1 + ω)(1 + ω 2 ) . . . (1 + ω p )
= 1p + 1 = 2
Aqui a gente usou a identidade:
z p + 1 = (z + 1)(z + ω)(z + ω 2 ) . . . (z + ω p−1 )
Portanto,
a0 + ap + a2p =
2p + (p − 1) × 2
p
Exercício 4 (IMO). Calcule o número de subconjuntos S ⊂ {1, 2, . . . , 2p}
tal que
(a) |S|
P =p
(b)
x∈S x é múltiplo de p
2. Representando conjuntos nos expoentes
Esse é um tipo bem diferente de função geratriz. Para um subconjunto
S ⊂ {1, 2, . . . n}, nós construímos a função
X
xs
s∈S
Vamos usar essa idéia nos próximos exercícios.
Exercício 5. Os inteiros positivos
a1 , a2 , . . . , an , b1 , b2 , . . . , bn , com n ≥ 2,
tem a propriedade que as n2 somas ai + aj são as mesmas que as n2 somas
bi + bj (em alguma ordem). Mostre que n é uma potência de 2.
FUNÇÕES GERATRIZES
3
Exercício 6. Seja A1 , A2 , . . . e B1 , B2 , . . . sequências de conjuntos definidos
por
(1) A1 = ∅, B1 = {0}
(2) An+1 = {x + 1 | x ∈ Bn }
(3) Bn+1 = (An ∪ Bn ) − (An ∩ Bn )
Determine todos os valores de n tal que Bn = {0}.
Essa técnica é especialmente útil para problemas do tipo: quando é possível cobrir um tabuleiro n × m com peças de um algum tipo. A gente
pode usar funções geratrizes para achar pinturas do tabuleiro de um jeito
estruturado.
Exemplo 2.1. Vamos mostrar que se nós podemos preencher um retângulo
n × m com peças a × b, então a divide n ou m. Por exemplo, é ímpossível
preencher um tabuleiro (12i + 6) × (4j + 2) com peças 3 × 4 .
Para o tabuleiro n × m, a gente associa a função
Tn,m (x, y) =
n−1
X m−1
X
xi y j = (1 + x + . . . + xn−1 )(1 + y + . . . + y n−1 )
i=0 j=0
Vamos supor que é possível preencher o tabuleiro n × m com peças 3 × 4:
colocando peças deitadas 3×4 em D = {(i0 , j0 ), (i1 , j1 ), . . . , (ik , jk )}, e peças
de pé 4 × 3 em P = {(ī0 , j̄0 ), (ī1 , j̄1 ), . . . , (īk , j̄k )}. A gente define
D(x, y) =
X
xi y j
(i,j)∈D
P (x, y) =
X
xi y j
(i,j)∈P
Agora observe que
Tn,m (x, y) = T3,4 (x, y)D(x, y) + T4,3 (x, y)P (x, y)
Agora a gente substitue valores para x e y para encontrar relações. Por
exemplo, x = y = 1 mostra que
12 | nm
(o que é óbvio, já que cada peça tem 12 quadradinhos).
Substituindo x = y = i, a gente conclui
0 = (1 + i + . . . + in−1 )(1 + i + . . . + im−1 )
o que implica que 4 divide n ou m.
Exercício 7. (IMO 2004) Determine que retângulos m × n podem ser cobertos por peças com formato de gancho (você pode refletir e rotacionar essa
peça):
×
×
4
G. BUJOKAS
Figura 1. Gancho
3. Usando funções geratrizes para demonstrar identidades
Exercício 8. 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
, para n ≥ 0
2n−k =
3
2k
k
X mn + k X mn
=
2k
k
m
k
k
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
4. 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]