17 - Partições de um Inteiro - Exercícios

Prévia do material em texto

16/4/2019 1Exercícios - Funções Geradoras e Partições
Professor: Luiz Augusto Laranjeira
luiz.laranjeira@gmail.com
AULA 17
Matemática Discreta 1
Exercícios:
Partições de um Inteiro
6/4/2019 2Exercícios - Funções Geradoras e Partições
Tabela de Funções Geradoras 
6/4/2019 3Exercícios - Funções Geradoras e Partições
Tabela de Funções Geradoras (cont.) 
6/5/2019 4Exercícios - Funções Geradoras e Partições
Funções Geradoras para Partições
Função
Geradora
Para a sequência das 
partições de n em
partes que são
ෑ
𝑘=1
∞
1 + 𝑥𝑘 distintas quaisquer
ෑ
𝑘=1
∞
1
1 − 𝑥𝑘
quaisquer
ෑ
𝑘=0
∞
(1 + 𝑥2𝑘+1) ímpares distintos
ෑ
𝑘=0
∞
1
(1 − 𝑥2𝑘+1)
ímpares
ෑ
𝑘=1
∞
1
(1 − 𝑥2𝑘)
pares
ෑ
𝑘=1
∞
(1 + 𝑥2𝑘) pares distintos
Função
Geradora
Para a sequência das 
partições de n em
partes que são
ෑ
𝑘=1
∞
(1 + 𝑥𝑘
2
) quadrados distintos
ෑ
𝑘=1
∞
1
(1 − 𝑥𝑘
2
)
quadrados
ෑ
𝑘=1
∞
(1 + 𝑥𝑘
3
) cubos distintos
ෑ
𝑘=1
∞
1
(1 − 𝑥𝑘
3
)
cubos
ෑ
𝑝 𝑝𝑟𝑖𝑚𝑜
∞
1
(1 − 𝑥𝑝) primos
Teorema 5.9: O número de partições autoconjugadas de n é igual ao número de 
partições de n em partes ímpares distintas.
p(n | autoconjugadas) = p(n | com partes ímpares distintas) 
6+6+5+5+4+2
• • • • • • 
• • • • • • 
• • • • • 
• • • • • 
• • • • 
• • 
6/6/2019 5Partições de um Inteiro
11
9
5
3
11+9+5+3
• • • • • • • • • • • 
• • • • • • • • • 
• • • • • 
• • • 
Partição 
autoconjugada
de n=28
Partição 
correspondente 
em partes 
ímpares distintas
bijeção ou
correspondência 
biunívoca
Recordação:
Partições Autoconjugadas
6/6/2019 6Exercícios - Funções Geradoras e Partições
Exercício 1
Prove que p(n), o número de partições de um inteiro positivo n, 
é ímpar, se e somente se, o número de partições de n com partes 
ímpares distintas é ímpar. Isto é:
p(n) é ímpar ⟷ p(n | com partes ímpares distintas) é ímpar
(Dica: usar o conceito de bijeção com partições autoconjugadas)
6/6/2019 7Exercícios - Funções Geradoras e Partições
Exercício 1
Prove que p(n), o número de partições de um inteiro positivo n, 
é ímpar, se e somente se, o número de partições de n com partes 
ímpares distintas é ímpar. Isto é:
p(n) é ímpar ⟷ p(n | com partes ímpares distintas) é ímpar
(Dica: usar o conceito de bijeção com partições autoconjugadas)
As partições de n que não são autoconjugadas sempre ocorrem em pares
e, portanto, o total delas é par. Se o número de partições autoconjugadas
de n for ímpar, o número total das partições de n será também ímpar.
Como o número de partições de n com partes ímpares distintas é igual
ao número de partições autoconjugadas de n, segue que 
p(n | com partes ímpares distintas) é ímpar ⟷ p(n) é ímpar 
CQD
6/6/2019 8Exercícios - Funções Geradoras e Partições
Definições
Definição E.1.
Uma partição de um inteiro positivo n é um retângulo se o seu gráfico 
de Ferrer é retangular, isto é, se o comprimento de todas as suas partes 
é o mesmo.
Definição E.1.
Uma partição de um inteiro positivo n é um retângulo longo se o seu 
gráfico de Ferrer é retangular com comprimento maior ou igual à sua 
altura.
6/6/2019 9Exercícios - Funções Geradoras e Partições
Exercício 2
Prove que o número de partições de um inteiro positivo n em que 
as partes consecutivas diferem entre si de 2 é igual ao número de 
partições de n que são retângulos longos.
p(n | partes consecutivas diferem de 2) = p(n | é retângulo longo)
(Dica: usar a transformação do gráfico de Ferrer utilizada com partições autoconjugadas)
6/7/2019 10Exercícios - Funções Geradoras e Partições
Exercício 2
Prove que o número de partições de um inteiro positivo n em que 
as partes consecutivas diferem entre si de 2 é igual ao número de 
partições de n que são retângulos longos.
p(n | partes consecutivas diferem de 2) = p(n | é retângulo longo)
(Dica: usar a transformação do gráfico de Ferrer utilizada com partições autoconjugadas)
É fácil notar que, para partições retangulares longas, a diferença entre os números de pontos 
de uma construção “linha + coluna” mais externa para a subsequente mais interna é exatamente 2 
(um ponto a menos na linha e um ponto a menos na coluna). Assim as partes consecutivas 
geradas na partição correspondente (à direita) diferirão entre si também de 2. 
• • • • • • 
• • • • • • 
• • • • • • 
• • • • • • 
9
7
5
3
6+6+6+6 9+7+5+3
• • • • • • • • • 
• • • • • • • 
• • • • • 
• • • 
bijeção ou
correspondência 
biunívoca
construções
“linha+coluna” 
Partição de 
n=24 em retângulo 
longo (6x4)
Partição 
correspondente com
partes consecutivas 
diferindo de 2
6/7/2019 11Exercícios - Funções Geradoras e Partições
Exercício 3a
Mostre que os divisores de um inteiro positivo n determinam as 
partições retangulares deste número. 
número de divisores de n = p(n | é retângulo)
(Dica: mostrar que todos os divisores de n ocorrem em pares n = di x dk,, onde i ≠ k, com 
exceção de um caso quando n é quadrado perfeito)
6/6/2019 12Exercícios - Funções Geradoras e Partições
Exercício 3a (cont.)
Mostre que os divisores de um inteiro positivo n determinam as 
partições retangulares deste número. 
número de divisores de n = p(n | é retângulo)
(Dica: mostrar que todos os divisores de n ocorrem em pares di x dj,= n, onde di ≠ dj,, com 
exceção de quando n é quadrado perfeito)
Vamos analisar os divisores de 32: 32, 16, 8, 4, 2, 1 
Vemos que cada par de divisores di x dj
corresponde a duas partições retangulares
de n, isto é, os retângulos di x dj e dj x di .
8 x 4 = 32
16 x 2 = 32
32 x 1 = 32
6/7/2019 13Exercícios - Funções Geradoras e Partições
Exercício 3a (cont.)
Mostre que os divisores de um inteiro positivo n determinam as 
partições retangulares deste número. 
número de divisores de n = p(n | é retângulo)
(Dica: mostrar que todos os divisores de n ocorrem em pares di x dj,= n, onde di ≠ dj,, com 
exceção de um caso quando n é quadrado perfeito)
Vamos analisar os divisores de 36: 36, 18, 12, 9, 6, 4, 3, 2, 1 
Ve-se que cada par de divisores di e dj, com
di x dj,= n, determina duas partições retangulares
de n, os retângulos di x dj e dj x di .
Porém como 36 é quadrado perfeito nota-se
que há um divisor (6), tal que 6x6 = 62 = 36, que
determina uma única partição quadrada (que também é retangular) de n.
9 x 4 = 36
12 x 3 = 36
18 x 2 = 36
36 x 1 = 36
6 x 6 = 36
6/7/2019 14Exercícios - Funções Geradoras e Partições
Exercício 3a (cont.)
Mostre que os divisores de um inteiro positivo n determinam as 
partições retangulares deste número. 
número de divisores de n = p(n | é retângulo)
(Dica: mostrar que todos os divisores de n ocorrem em pares di x dj,= n, onde di ≠ dj,, com 
exceção de um caso quando n é quadrado perfeito)
Em ambos os casos, isto é, seja n quadrado perfeito ou não, o número 
de divisores de n é igual ao número de partições retangulares de n.
6/6/2019 15Exercícios - Funções Geradoras e Partições
Exercício 3b
Prove que o número de divisores de um inteiro n é ímpar, se e 
somente se, n é um número quadrado perfeito. 
(Dica: usar a transformação do gráfico de Ferrer utilizada com partições autoconjugadas)
6/6/2019 16Exercícios - Funções Geradoras e Partições
Exercício 3b
Prove que o número de divisores de um inteiro n é ímpar, se esomente se, n é um número quadrado perfeito. 
Como visto no exercício anterior, os divisores de um número inteiro positivo n
ocorrem aos pares, satisfazendo a relação 
di x dj = n (i ≠ j)
exceto quando n for quadrado perfeito. Neste caso haverá um divisor dk que 
não terá um par. Este divisor satisfaz a relação
dk x dk = (dk)
2 = n.
Assim, se n não for quadrado perfeito o número de seus divisores
será par porque todos os divisores ocorrerão em pares.
Se, porém, n for quadrado perfeito o número de seus divisores será
a soma de um valor par mais 1, o que resulta em um número ímpar.
6/6/2019 17Exercícios - Funções Geradoras e Partições
Exercício 4
Prove que o número de partições de um inteiro em partes pares 
distintas é igual ao número de partições deste inteiro em partes 
que são da forma 2j, onde j é um número ímpar.
6/6/2019 18Exercícios - Funções Geradoras e Partições
Exercício 4
Prove que o número de partições de um inteiro em partes pares 
distintas é igual ao número de partições deste inteiro em partes 
que são da forma 2j, onde j é um número ímpar.
Quer-se provar que:
𝐹𝑔𝑝𝑑 =ෑ
𝑘=0
∞
1 + 𝑥2𝑘 = ෑ
𝑗 í𝑚𝑝𝑎𝑟
∞
1
1 − 𝑥2𝑗
=ෑ
𝑘=0
∞
1
1 − 𝑥2(2𝑘+1)
Desenvolvendo 𝐹𝑔𝑝𝑑 , vem:
ෑ
𝑘=0
∞
1 + 𝑥2𝑘 =ෑ
𝑘=0
∞
1 + 𝑥2𝑘 1 − 𝑥2𝑘
1 − 𝑥2𝑘
=ෑ
𝑘=0
∞
1 − 𝑥4𝑘
1 − 𝑥2𝑘
ෑ
𝑘=0
∞
1 − 𝑥4𝑘
1 − 𝑥2𝑘
=
1 − 𝑥4 1 − 𝑥8 1 − 𝑥12 1 − 𝑥16 …
1 − 𝑥2 1 − 𝑥4 1 − 𝑥6 1 − 𝑥8 1 − 𝑥10 1 − 𝑥12 1 − 𝑥14 …
𝐹𝑔𝑝𝑑 =ෑ
𝑘=0
∞
1 − 𝑥4𝑘
1 − 𝑥2𝑘
=
1
1 − 𝑥2 1 − 𝑥6 1 − 𝑥10 1 − 𝑥14 …
𝐹𝑔𝑝𝑑 =ෑ
𝑘=0
∞
1
1 − 𝑥4𝑘+2
=ෑ
𝑘=0
∞
1
1 − 𝑥2(2𝑘+1) CQD
6/6/2019 19Exercícios - Funções Geradoras e Partições
Exercício 5
Dar uma interpretação, em termos de partições, para:
a) O coeficiente de x12 na expansão de 
(1+𝑥2+𝑥4+𝑥6+𝑥8+𝑥10+𝑥12) 1+ 𝑥4+𝑥8+𝑥12 1+𝑥6+𝑥12 1+𝑥8 1+𝑥10 1+𝑥12
b) O coeficiente de x15 na expansão de
(1 + 𝑥3+𝑥6 + 𝑥9 + 𝑥12 + 𝑥15)(1 + 𝑥6 + 𝑥12)(1 + 𝑥9)
6/6/2019 20Exercícios - Funções Geradoras e Partições
Exercício 5
Dar uma interpretação, em termos de partições, para:
a) O coeficiente de x12 na expansão de 
(1+𝑥2+𝑥4+𝑥6+𝑥8+𝑥10+𝑥12)(1+ 𝑥4+𝑥8+𝑥12)(1+𝑥6+𝑥12)(1+ 𝑥8)(1+ 𝑥10)(1+ 𝑥12)
Para obter o no de partições do inteiro 12 cujas partes são pares com valor menor ou igual a 12 
obtemos o coeficiente de 𝑥12 na função geradora G(x) abaixo.
𝐺 𝑥 =ෑ
𝑘=1
6
1
(1−𝑥2𝑘)
=
1
(1−𝑥2)(1−𝑥4)(1−𝑥6)(1−𝑥8)(1−𝑥10)(1−𝑥12)
= 1+𝑥2+𝑥4+𝑥6+𝑥8+𝑥10+𝑥12…
1+𝑥4+𝑥8+𝑥12+⋯ 1+𝑥6+𝑥12+⋯
1+𝑥8+⋯ 1+𝑥10+⋯ 1+𝑥12+⋯
𝐺 𝑥 = 1+𝑥2+2𝑥4+3𝑥6+5𝑥8+7𝑥10+𝟏𝟏𝑥12+ …
O coeficiente de 𝑥12 em𝐺 𝑥 , que é 11, será igual ao número de 
partições de 12 cujas partes são pares ≤ 12.
Partição No de Partes
1 12 1
2 10, 2 2
3 8, 4 2
4 8, 2, 2 3
5 6, 4, 2 3
6 6, 6 2
7 6, 2, 2, 2 4
8 4, 4, 4 3
9 4, 4, 2, 2 4
10 4, 2, 2, 2, 2 5
11 2, 2, 2, 2, 2, 2 6
6/7/2019 21Exercícios - Funções Geradoras e Partições
Uma Curiosidade Matemática 
Relacionada ao Exercício 5a
Uma outra interpretação para o coeficiente de x12 na expansão de
𝑮 𝒙 = (1 + 𝑥2+𝑥4 + 𝑥6 + 𝑥8 + 𝑥10 + 𝑥12)(1 + 𝑥4 + 𝑥8 + 𝑥12)
(1 + 𝑥6 + 𝑥12)(1 + 𝑥8)(1 + 𝑥10)(1 + 𝑥12)
𝐺 𝑥 = 1+𝑥2+2𝑥4 +3𝑥6+5𝑥8+7𝑥10+𝟏𝟏𝑥12 + …
Pode também ser interpretado como o número
de soluções inteiras não-negativas da equação
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 = 12
Com as seguintes restrições
𝑥1 ∈ {0, 2, 4, 6, 8, 10, 12}, 
𝑥2 ∈ {0, 4, 8, 12},
𝑥3 ∈ {0, 6, 12}, 
𝑥4 ∈ {0, 8}, 
𝑥5 ∈ {0, 10} e
𝑥6 ∈ {0, 12}.
Solução No de Partes Partição
1 12, 0, 0, 0, 0, 0 1 12
2 0,12, 0, 0, 0, 0 1 12
3 0, 0, 12, 0, 0, 0 1 12
4 0, 0, 0, 0, 0, 12 1 12
5 2, 0, 0, 0, 10, 0 2 10, 2
6 8, 4, 0, 0, 0, 0 2 8, 4
7 0, 4, 0, 8, 0, 0 2 8, 4
8 4, 8, 0, 0, 0, 0 2 8, 4
9 4, 0, 0, 8, 0, 0 2 8, 4
10 6, 0, 6, 0, 0, 0 2 6, 6
11 2, 4, 6, 0, 0, 0 3 6, 4, 2
Após a multiplicação, o 
coeficiente de 𝑥12 é 11.
6/6/2019 22Exercícios - Funções Geradoras e Partições
Exercício 5 (cont.)
Dar uma interpretação, em termos de partições, para:
b) O coeficiente de x15 na expansão de
(1 + 𝑥3+𝑥6 + 𝑥9 + 𝑥12 + 𝑥15)(1 + 𝑥6 + 𝑥12)(1 + 𝑥9)
𝐺 𝑥 =ෑ
𝑘=1
3
1
(1 − 𝑥3𝑘)
=
1
(1 − 𝑥3)(1 − 𝑥6)(1 − 𝑥9)
= 1+𝑥3+𝑥6+𝑥9+𝑥12 +𝑥15 +⋯ (1+𝑥6+𝑥12+⋯)(1+𝑥9+⋯)
𝐺 𝑥 = 1+𝑥3+2𝑥6+3𝑥9+4𝑥12+𝟓𝑥15+ …
O coeficiente de 𝑥15 será igual ao número de partições
de 15 cujas partes são múltiplas de 3, isto é, 3, 6 ou 9.
Após a multiplicação, o 
coeficiente de 𝑥15 é 5.
6/6/2019 23Exercícios - Funções Geradoras e Partições
Exercício 6
Escrever a função geradora que pode ser usada para se encontrar:
a) O número de partições de 34 com partes restritas a 6, 8, 10 e 20.
b) O número de partições de 13 com partes maiores que 3.
c) O número de partições de 11 em partes ímpares distintas.
d) O número de partições de 11 em partes ímpares quaisquer.
6/6/2019 24Exercícios - Funções Geradoras e Partições
Exercício 6
Escrever a função geradora que pode ser usada para se encontrar:
a) O número de partições de 34 com partes restritas a 6, 8, 10 e 20.
𝐺 𝑥 =
1
(1−𝑥6)(1−𝑥8)(1−𝑥10)(1−𝑥20)
= 1+𝑥6 +𝑥12+𝑥18+𝑥24+𝑥30+⋯ 1+𝑥8+𝑥16 +𝑥24+𝑥32…
(1+𝑥10 +𝑥20+𝑥30+⋯)(1+𝑥20+⋯)
6/6/2019 25Exercícios - Funções Geradoras e Partições
Exercício 6
Escrever a função geradora que pode ser usada para se encontrar:
b) O número de partições de 13 com partes maiores que 3.
𝐺 𝑥 = ς𝑘=3
13 1
(1−𝑥𝑘)
=
1
1−𝑥4 1−𝑥5 …(1−𝑥13)
= 1+𝑥4+𝑥8+𝑥12 +⋯ (1+𝑥5+𝑥10+⋯)
(1+ 𝑥6+𝑥12+⋯)(1+𝑥7+⋯)(1+𝑥8+⋯)(1+𝑥9+⋯)(1+𝑥10+⋯)
(1+𝑥11 +⋯)(1+𝑥12+⋯)(1+𝑥13+⋯)
6/6/2019 26Exercícios - Funções Geradoras e Partições
Exercício 6 (cont.)
Escrever a função geradora que pode ser usada para se encontrar:
c) O número de partições de 11 em partes ímpares distintas.
𝐺 𝑥 = ς𝑘=0
5 (1 + 𝑥2𝑘+1) = (1 + 𝑥) 1 + 𝑥3 1 + 𝑥5 1 + 𝑥7 1 + 𝑥9 1 + 𝑥11
𝐺 𝑥 = 1+𝑥+𝑥3+𝑥4+𝑥5+𝑥6+𝑥7+2𝑥8+2𝑥9+𝑥10+2𝑥11+ …
d) O número de partições de 11 em partes ímpares quaisquer.
𝐺 𝑥 =ෑ
𝑘=0
5
1
(1 − 𝑥2𝑘+1)
=
1
(1 − 𝑥)(1 − 𝑥3)(1 − 𝑥5)(1 − 𝑥7)(1 − 𝑥9)(1 − 𝑥11)
= 1+𝑥+𝑥2+𝑥3+𝑥4+…+𝑥11+⋯ 1+𝑥3+𝑥6+𝑥9+⋯
(1+ 𝑥5 +𝑥10+⋯)(1+𝑥7+⋯)(1+𝑥9+⋯)(1+𝑥11+⋯)
𝐺 𝑥 = 1+𝑥+𝑥2+2𝑥3+2𝑥4+3𝑥5+4𝑥6+5𝑥7+6𝑥8+8𝑥9+10𝑥10+12𝑥11+ …
Partições de 11 em partes ímpares
quaisquer (𝑷𝒊𝒒 = 𝟏𝟐)
11 9+1+1
7+3+1 7+1+1+1+1
5+5+1 5+3+3
5+3+1+1+1 5+1+1+1+1+1+
3+3+3+1+1 3+3+1+1+1+1+1
3+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1+1
6/6/2019 27Exercícios - Funções Geradoras e Partições
Exercício 6 (cont.)
Partições de 11 em partes ímpares
distintas (𝑷𝒊𝒅 = 𝟐)
11
1+3+7
6/7/2019 28Exercícios - Funções Geradoras e Partições
Exercício 7
Prove que o número de partições de um inteiro n formadas por uma parte 
par e uma parte ímpar é igual a 0 para n par e igual a n−2 para n ímpar.
6/7/2019 29Exercícios - Funções Geradoras e Partições
Exercício 7
Prove que o número de partições 𝒌de um inteiro 𝒏 formadas por uma parte 
par e uma parte ímpar é igual a 0 para n par e igual a 
𝒏−𝟏
𝟐
para n ímpar.
Para 𝑛 par não é possível ter-se uma parte par e uma ímpar. Assim 𝒌 = 𝟎. 
Para 𝑛 ímpar o número 𝑘 de partições de 𝑛 desejado será igual ao 
coeficiente de 𝑥𝑛 resultante do seguinte produto:
𝑥 + 𝑥3 +𝑥5 +…+𝑥𝑛−4 +𝑥𝑛−2 𝑥2 +𝑥4 +……+𝑥𝑛−3+𝑥𝑛−1
Por exemplo, para 𝑛 = 9: 𝑥 + 𝑥3 +𝑥5 +𝑥7 𝑥2 +𝑥4 +𝑥6 +𝑥8
Os termos em 𝑥9 seriam 𝑥1𝑥8 +𝑥3𝑥6 +𝑥5𝑥4 +𝑥7𝑥2 e o coef. de 𝑥𝑛 seria 4.
No caso genéricoos termos em 𝑥𝑛 seriam
𝑥1𝑥𝑛−1 + 𝑥3𝑥𝑛−3 + 𝑥5𝑥𝑛−5 +⋯+ 𝑥𝑛−4𝑥4 + 𝑥𝑛−2𝑥2 e o coeficiente de 𝑥𝑛
seria igual ao no de termos 𝑘da PA com 𝑎1 = 1, 𝑎𝑘 = 𝑛 − 2 e razão 2.
Fazendo-se o cálculo obtemos: 𝒌 =
𝒏−𝟏
𝟐 CQD