Lista de Análise Combinatória
Edson Prestes
2 de Dezembro de 2011
Capı́tulo 1
Questões
1.1
Questão 1
Marcam-se 5 pontos sobre uma reta R e 8 pontos sobre uma R’ paralela a R. Quantos
triângulos podem ser formados com estes pontos ?
Resposta: 220 triangulos.
1.2
Questã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
Questão 3
De quantos modos n casais podem formar uma roda de ciranda de modo que cada
homem permaneça ao lado de sua mulher?
Resposta: 2n (n − 1)!.
1.4
Questão 4
Quantas são as soluções inteiras e não negativas da inequação x + y + z ≤ 5?
Resposta: 56
1.5
Questão 5
Quantas são as soluções inteiras não negativas de x + y + z + w = 20 nas quais x > y?
Resposta:825.
2
1.6
Questão 6
Em um congresso há 15 professores de fı́sica e 15 de matemática. Quantas comissões
de 8 professores podem ser formadas havendo pelo menos 4 professores de matemática
e pelo menos 2 professores de fı́sica ?
Resposta: 3755115
1.7
Questão 7
Quantos são os anagramas da palavra MISSISSIPPI nos quais não há 2 letras I consecutivas ?
Resposta: 7350 anagramas diferentes.
1.8
Questão 8
São colocados em fila n casais. De quantas maneiras isto pode ser feito de forma que
marido e mulher nãoP
sejam vizinhos ?
n
Resposta: 2n! − i=1 Cni (2n − i)!2i (−1)i
1.9
Questão 9
Uma recepcionista recebeu n chapéus, mas estes ficaram totalmente misturados. Decidiu, então, devolvê-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
Questão 10
n
Mostre que k=0 k
xk = xn(x + 1)n−1
k
Resposta:xn(x + 1)n−1
Pn
1.11
Questão 11
Pn
Calcule k=0 Cnk 2k .
Resposta: 3n .
1.12
Questã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
Questã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
Questão 14
Calcule
S=
2
n
X
n
k
k
k=0
n−1
Resposta:nC2n−1
1.15
Questã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
Questão 16
Determine o coeficiente de x17 no desenvolvimento de (1 + x5 + x7 )20
Resposta:3420
1.17
Questão 17
63127 candidatos compareceram a uma prova do vestibular (25 questões de múltiplaescolha com 5 alternaticas por questão). Considere a afirmativa: pelo menos 4 candidatos responderam de modo idêntico as k primeiras questões da prova. Qual é o
maior valor de k para o qual podemos garantir que a afirmativa acima continue sendo
verdadeira.
Resposta: 6
1.18
Questão 18
Considere 6 pontos no espaço não havendo 3 colineares. Assuma que cada ponto está
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
existirá um triângulo com todos os lados de uma mesma cor.
4
1.19
Questão 19
Encontrar a função geradora para ar = r2 .
Resposta: x(1+x)
(1−x)3
1.20
Questão 20
Mostrar que a função geradora ordinária para a seqüência
0
0
2
4
6
2r
,
,
,
,...,
1
2
3
r
é (1 − 4x)−1/2
1.21
Questão 21
Usar funções geradoras para encontrar o número de maneiras nas quais 4 pessoas cada
uma jogando um único dado podem obter um total de 17.
Resposta: 104.
1.22
Questão 22
Mostrar a forma dos coeficientes gerados pela seguinte função
(1+4x)1/2 em
P∞ geradora
r−1
2
1/2
xr
função do número do termo. Resposta: (1 + 4x)
= r=0 C2r−1 !(−1)r−1 2r−1
1.23
Questão 23
Usar funções geradoras para avaliar a soma 1 + 2 + 3 + . . . + n Resposta:
1.24
(n+1)n
2
Questão 24
De quantas maneiras podemos acomodar 9 pessoas em 4 quartos sem que nenhum
quarto fique vazio ? Resposta:186480
1.25
Questão 25
Usar funções geradoras para avaliar a soma 12 + 22 + 32 + . . . + n2 .
Resposta: n(n+1)(2n+1)
6
5
1.26
Questão 26
Representantes de três institutos de pesquisa devem formar uma comissão de 9 pesquisadores. De quantos modos se pode formar esta comissão sendo que nenhum instituto
deve ter maioria absoluta no grupo ?
Resposta: 10
1.27
Questão 27
Usar funções geradoras para encontrar o número de soluções em inteiros da equação
x + y + z + w = 25, onde cada variável é no mı́nimo 3 e no máximo 8.
13
7
Resposta: C16
− 4C10
+ 6C41
1.28
Questão 28
Numa competiçã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
funções geradoras para encontrar o número de maneiras que os juı́zes têm para atribuir
notas de modo que um participante seja finalista.
Resposta:15.
1.29
Questão 29
Encontrar o número de maneiras de se distribuir 11 laranjas e 6 pêras para 3 crianças
de modo que cada criança receba pelo menos 3 laranjas e no máximo 2 pêras.
Resposta: 6.
1.30
Questão 30
Quantas n-tuplas de de 0’s e 1’s podem ser formadas usando-se um número par de 0’s
e um número par de 1’s ?
Resposta: 2n−1 para n par, e 0 caso contrário.
1.31
Questão 31
De quantas maneiras podemos distribuir 300 cadeiras idênticas em 4 salas de modo que
o número de cadeiras em cada sala seja 20, 40, 60, 80 ou 100 cadeiras ?
Resposta: 52
6
1.32
Exercicio 32
Calcule a seguinte relação de recorrê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 fórmula fechada para
an = 2 cos αan−1 − an−2
considerando as seguintes condições iniciais a1 = cos α e a2 = cos 2α
Resposta:an = 12 ((cos α + i sin α)n + (cos α − i sin α)n )
1.34
Questão 34
Ache a solução para a seguinte relação de recorrência
fn = 8fn−1 − 19fn−2 + 12fn−3
considerando as seguintes condições iniciais f0 = 0, f1 = 1 e f2 = 2
1.35
Questão 35
Ache a solução para a seguinte relação de recorrência
fn = −fn−1 − 3fn−2 − 3fn−3
considerando as seguintes condiçõ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
Questão 36
Encontrar o número de permutações de 1,2,3,4,5,6 nas quais as seqüências 134 e 56
não aparecem. Resposta: 582
1.37
Questão 37
De quantas podemos permutar os inteiros 1, 2, . . . , 9 de forma que nenhum inteiro par
fique em sua posição original. Resposta: 229080
7
1.38
Questão 38
Considere os algarismos do número 786415. Forme todos os números de 6 algarismos
distintos e coloque-os em ordem crescente. Qual é a posição ocupada pelo número
dado ? Resposta: 597
1.39
Questão 39
Nove cientistas trabalham num projeto sigiloso. Por questões de segurança, os planos
são guardados em um cofre protegido por muitos cadeados de modo que só é possı́vel
abrı́-los todos se houver pelo menos 5 cientistas. a) Qual é o número mı́nimo possı́vel
de cadeados ? b) Quantas chaves cada cientista deve ter ?
Resposta: a)126 cadeados. b) 70 chaves.
1.40
Questão 40
Prove
p
0
1
2
p
Cm
Chp + Cm
Chp−1 + Cm
Chp−2 + . . . + Cm
Ch0 = Cm+h
1.41
Questão 41
Prove
n
(Cn0 )2 + (Cn1 )2 + (Cn2 )2 + . . . + (Cnn )2 = C2n
1.42
Questão 42
Quantos números entre 1 e 1000000 têm exatamente a soma dos algarismos igual a 6 ?
Resposta: 210
1.43
Questão 43
De quantos modos n casais podem sentar-se ao redor de uma mesa circular de forma
que o marido eP
mulher não fiquem juntos ?
n
Resposta: i=0 (−1)i Cni 2i (2n − 1 − i)!
1.44
Questão 44
Encontrar o número de r-sequências formadas por 0, 1 e 2 onde o número de 0’s é par.
r
Resposta: 3 2+1
8