md_lista8_2014_1

Prévia do material em texto

UERJ - Universidade do Estado do Rio de Janeiro 
Instituto de Matemática e Estatística 
Departamento de Matemática Aplicada 
Disciplina: Matemática Discreta 
Professor: Augusto César de Castro Barbosa 
8a lista de exercícios 
__________________________________________________________________ 
 
 
Princípio de Inclusão e Exclusão e Funções Geradoras 
 
 
1 – De quantas maneiras se podem comprar 15 latas de refrigerantes se existem 4 
tipos disponíveis e há somente 6 latas de cada tipo? 
 
2 – Encontrar a função geradora ordinária para cada uma das sequências abaixo: 
 
(a) ,...)0,0,0,1,1,1( 
(b) ,...)0,0,0,3,2,0,0,1( 
(c) ,...)1,1,1,3,1,1,1( 
(d) ,...)1,0,1,0,1,0( 
(e) 





−−− ,...
!5
1
,
!4
1
,
!3
1
,
!2
1
,1,1 
 
3 – Encontrar a sequência gerada pelas funções geradoras ordinárias dadas 
abaixo: 
 
(a) 41)(x + 
(b) xex + 
(c) 12 x)3(1x −− 
(d) 22x xxe ++ 
 
4 – Quantas são as soluções inteiras não negativas de 
 
30xxxx 4321 =+++ , 
 
se cada variável deve estar compreendida entre 4 e 9? 
 
 
 
 
 
Respostas 
 
 
 
1 – Seja a equação 
 
15xxxx 4321 =+++ 
 
e os conjuntos =iA {compras de 15 latas nas quais 7x i ≥ }, onde ix é o número 
de latas do tipo i que foram compradas. Assim, devemos retirar 
)AAAn(A 4321 UUU do número de soluções inteiras não negativas da 
equação acima; esse número de soluções corresponde ao caso em que existem 
tantas latas quanto queiramos de cada tipo. Temos então 816 – 636 = 180 
maneiras. 
 
 
2 – (a) 2xx1 ++ 
 (b) 43 x3x21 ++ 
 (c) 
x1
1
x2 3
−
+ 
 (d) 2x1
x
−
 
 (e) xe− 
 
 
3 – (a) )(1,4,6,4,1 
 (b) 





,...
!k
1
,...,
!4
1
,
!3
1
,
!2
1
,2,1 
 (c) ),3,3(0,0,1,3,3 432 
 (d) 





,...
!5
2
,
!4
2
,
!3
2
,3,3,1
543
 
 
 
4 – A função geradora que controla cada uma das quatro variáveis é dada por 
 
987654 xxxxxx +++++ . 
 
Portanto, o número de soluções da equação dada corresponde ao coeficiente de 
30x no desenvolvimento de 
 
440342822164987654 )x1)(xx4x6x4x()xxxxx(x −−+−+−=+++++ . 
 
Em 4)x1( −− necessitamos, portanto, apenas dos coeficientes de 14x , 8x e 2x . 
Assim, o coeficiente de 30x na expressão acima é 
80C6C4C 2 1248 18414 1144 =⋅+⋅− −+−+−+ .