Lista de Análise Combinatória
Edson Prestes
2 de Dezembro de 2011
Capı́tulo 1
Questões
1.1
Questão 1
Marcam-se 5 pontos sobre uma reta R e 8 pontos sobre uma R’ paralela a R. Quantos
triângulos podem ser formados com estes pontos ?
Resposta: 220 triangulos.
1.2
Questão 2
De quantos modos podemos escolher 6 pessoas, incluindo pelo menos duas mulheres,
em um grupo de 7 homens e 4 mulheres?
Resposta: 371.
1.3
Questão 3
De quantos modos n casais podem formar uma roda de ciranda de modo que cada
homem permaneça ao lado de sua mulher?
Resposta: 2n (n − 1)!.
1.4
Questão 4
Quantas são as soluções inteiras e não negativas da inequação x + y + z ≤ 5?
Resposta: 56
1.5
Questão 5
Quantas são as soluções inteiras não negativas de x + y + z + w = 20 nas quais x > y?
Resposta:825.
2
1.6
Questão 6
Em um congresso há 15 professores de fı́sica e 15 de matemática. Quantas comissões
de 8 professores podem ser formadas havendo pelo menos 4 professores de matemática
e pelo menos 2 professores de fı́sica ?
Resposta: 3755115
1.7
Questão 7
Quantos são os anagramas da palavra MISSISSIPPI nos quais não há 2 letras I consecutivas ?
Resposta: 7350 anagramas diferentes.
1.8
Questão 8
São colocados em fila n casais. De quantas maneiras isto pode ser feito de forma que
marido e mulher nãoP
sejam vizinhos ?
n
Resposta: 2n! − i=1 Cni (2n − i)!2i (−1)i
1.9
Questão 9
Uma recepcionista recebeu n chapéus, mas estes ficaram totalmente misturados. Decidiu, então, devolvê-los a esmo. Calcular a probabilidade de que nenhum homem receba
o seu.
1
1
1
1
Resposta:n! 2!
− 3!
+ 4!
− . . . + (−1)n n!
1.10
Questão 10
n
Mostre que k=0 k
xk = xn(x + 1)n−1
k
Resposta:xn(x + 1)n−1
Pn
1.11
Questão 11
Pn
Calcule k=0 Cnk 2k .
Resposta: 3n .
1.12
Questão 12
Calcule a soma
0
C20
−
20
1
C2
C3
C4
C20
C20
+ 20
− 20
+ 20
− . . . + 20
2
3
4
2
2
2
2
2
3
Resposta:
1.13
1 20
2
Questão 13
Pn
Calcule o valor de k=0 k 2 Cnk 5k
Resposta :5n(6n−2 (5(n − 1) + 6)) = 5n(5n + 1)6n−2
1.14
Questão 14
Calcule
S=
2
n
X
n
k
k
k=0
n−1
Resposta:nC2n−1
1.15
Questão 15
Calcule
n
X
k 3 Cnk 5k
k=0
Resposta:53 n(n − 1)(n − 2)6n−3 + 3(52 )n(n − 1)6n−2 + 5n6n−1
1.16
Questão 16
Determine o coeficiente de x17 no desenvolvimento de (1 + x5 + x7 )20
Resposta:3420
1.17
Questão 17
63127 candidatos compareceram a uma prova do vestibular (25 questões de múltiplaescolha com 5 alternaticas por questão). Considere a afirmativa: pelo menos 4 candidatos responderam de modo idêntico as k primeiras questões da prova. Qual é o
maior valor de k para o qual podemos garantir que a afirmativa acima continue sendo
verdadeira.
Resposta: 6
1.18
Questão 18
Considere 6 pontos no espaço não havendo 3 colineares. Assuma que cada ponto está
conectado com os demais gerando um segmento que pode ser colorido com duas cores
azul ou vermelho. Prove que para qualquer que seja a escolha destas cores sempre
existirá um triângulo com todos os lados de uma mesma cor.
4
1.19
Questão 19
Encontrar a função geradora para ar = r2 .
Resposta: x(1+x)
(1−x)3
1.20
Questão 20
Mostrar que a função geradora ordinária para a seqüência
0
0
2
4
6
2r
,
,
,
,...,
1
2
3
r
é (1 − 4x)−1/2
1.21
Questão 21
Usar funções geradoras para encontrar o número de maneiras nas quais 4 pessoas cada
uma jogando um único dado podem obter um total de 17.
Resposta: 104.
1.22
Questão 22
Mostrar a forma dos coeficientes gerados pela seguinte função
(1+4x)1/2 em
P∞ geradora
r−1
2
1/2
xr
função do número do termo. Resposta: (1 + 4x)
= r=0 C2r−1 !(−1)r−1 2r−1
1.23
Questão 23
Usar funções geradoras para avaliar a soma 1 + 2 + 3 + . . . + n Resposta:
1.24
(n+1)n
2
Questão 24
De quantas maneiras podemos acomodar 9 pessoas em 4 quartos sem que nenhum
quarto fique vazio ? Resposta:186480
1.25
Questão 25
Usar funções geradoras para avaliar a soma 12 + 22 + 32 + . . . + n2 .
Resposta: n(n+1)(2n+1)
6
5
1.26
Questão 26
Representantes de três institutos de pesquisa devem formar uma comissão de 9 pesquisadores. De quantos modos se pode formar esta comissão sendo que nenhum instituto
deve ter maioria absoluta no grupo ?
Resposta: 10
1.27
Questão 27
Usar funções geradoras para encontrar o número de soluções em inteiros da equação
x + y + z + w = 25, onde cada variável é no mı́nimo 3 e no máximo 8.
13
7
Resposta: C16
− 4C10
+ 6C41
1.28
Questão 28
Numa competição cada um dos quatros juizes deve atribui notas de 1 a 6 para cada
participante. Para ser finalista um participante deve ter no mı́nimo 22 pontos. Usar
funções geradoras para encontrar o número de maneiras que os juı́zes têm para atribuir
notas de modo que um participante seja finalista.
Resposta:15.
1.29
Questão 29
Encontrar o número de maneiras de se distribuir 11 laranjas e 6 pêras para 3 crianças
de modo que cada criança receba pelo menos 3 laranjas e no máximo 2 pêras.
Resposta: 6.
1.30
Questão 30
Quantas n-tuplas de de 0’s e 1’s podem ser formadas usando-se um número par de 0’s
e um número par de 1’s ?
Resposta: 2n−1 para n par, e 0 caso contrário.
1.31
Questão 31
De quantas maneiras podemos distribuir 300 cadeiras idênticas em 4 salas de modo que
o número de cadeiras em cada sala seja 20, 40, 60, 80 ou 100 cadeiras ?
Resposta: 52
6
1.32
Exercicio 32
Calcule a seguinte relação de recorrência
an = 3an−1 − an−2 + 3an−3
para n ≥ 3, a0 = 3 , a1 = 3 e a2 = 7.
Resposta: an = 3n + (i)n + (−i)n
1.33
Exemplo 33
Encontre a fórmula fechada para
an = 2 cos αan−1 − an−2
considerando as seguintes condições iniciais a1 = cos α e a2 = cos 2α
Resposta:an = 12 ((cos α + i sin α)n + (cos α − i sin α)n )
1.34
Questão 34
Ache a solução para a seguinte relação de recorrência
fn = 8fn−1 − 19fn−2 + 12fn−3
considerando as seguintes condições iniciais f0 = 0, f1 = 1 e f2 = 2
1.35
Questão 35
Ache a solução para a seguinte relação de recorrência
fn = −fn−1 − 3fn−2 − 3fn−3
considerando as seguintes condições iniciais f0 = 1, f1 = 0 e f2 = 5
Resposta:
√
√
√
2 − 3i √ n
− 3i − 2
√
fn = 2(−1)n + ( √
)( 3i) + (
)(− 3i)n
2 3i
2 3i
1.36
Questão 36
Encontrar o número de permutações de 1,2,3,4,5,6 nas quais as seqüências 134 e 56
não aparecem. Resposta: 582
1.37
Questão 37
De quantas podemos permutar os inteiros 1, 2, . . . , 9 de forma que nenhum inteiro par
fique em sua posição original. Resposta: 229080
7
1.38
Questão 38
Considere os algarismos do número 786415. Forme todos os números de 6 algarismos
distintos e coloque-os em ordem crescente. Qual é a posição ocupada pelo número
dado ? Resposta: 597
1.39
Questão 39
Nove cientistas trabalham num projeto sigiloso. Por questões de segurança, os planos
são guardados em um cofre protegido por muitos cadeados de modo que só é possı́vel
abrı́-los todos se houver pelo menos 5 cientistas. a) Qual é o número mı́nimo possı́vel
de cadeados ? b) Quantas chaves cada cientista deve ter ?
Resposta: a)126 cadeados. b) 70 chaves.
1.40
Questão 40
Prove
p
0
1
2
p
Cm
Chp + Cm
Chp−1 + Cm
Chp−2 + . . . + Cm
Ch0 = Cm+h
1.41
Questão 41
Prove
n
(Cn0 )2 + (Cn1 )2 + (Cn2 )2 + . . . + (Cnn )2 = C2n
1.42
Questão 42
Quantos números entre 1 e 1000000 têm exatamente a soma dos algarismos igual a 6 ?
Resposta: 210
1.43
Questão 43
De quantos modos n casais podem sentar-se ao redor de uma mesa circular de forma
que o marido eP
mulher não fiquem juntos ?
n
Resposta: i=0 (−1)i Cni 2i (2n − 1 − i)!
1.44
Questão 44
Encontrar o número de r-sequências formadas por 0, 1 e 2 onde o número de 0’s é par.
r
Resposta: 3 2+1
8