P3-2013-1

Prévia do material em texto

3a Prova - Matemática Combinatória - 18/7/2013
Questões:
1. (3.0) Resolva (justificando):
(a) Um comitê de 10 estudantes deve ser selecionado de uma turma
de 25 calouros e 35 veteranos. De quantas maneiras podemos
selecionar comitês com pelo menos um calouro?
(b) Determine o número de soluções inteiras e estritamente positivas
( > 0) da equação:
x+ y + z + w = 27 tais que x ≥ 3 e w ≥ 2.
(c) Calcule o coeficiente de a−10 no desenvolvimento de
(
4√a
b2
− 2
√
b
a
)100(
4√a
b2
+ 2
√
b
a
)100, com a > 0 e b > 0.
2. (1.5) Use o Princípio da Inclusão e Exclusão para calcular o número de
maneiras em que podemos permutar os inteiros 1, 2, . . . , 9 de modo que
nenhum inteiro par ocupe seu lugar natural. Observação: Explicite o
conjunto base e as propriedades usadas no P.I.E.
3. (1.5) Resolva a seguinte relação de recorrência:
an = 3an−1 + 5
n−1
a1 = 1
4. (4.0) Verifique se cada uma das afirmações abaixo é falsa ou verdadeira.
Se for verdadeira, prove. Se for falsa, dê um contra-exemplo (seu
contra-exemplo deve ser justificado).
(a) Se F é uma floresta com k componentes conexos, n vértices e m
arestas então m = n− k.
(b) Em qualquer grafo o número de vértices com grau ímpar é par.
(c) Se r = s então o grafo bipartido completo Kr,s é hamiltoniano.
(d) Se um digrafo G tem fonte e sumidouro então ele é acíclico.
(e) Todo grafo que contém um grafo planar como subgrafo é planar.