ANÁLISE COMBINATÓRIA
A principal finalidade da Análise Combinatória é estabelecer métodos de contagem.
I. Princípio Fundamental da Contagem (P.F.C.)
O P.F.C. , ou princípio multiplicativo, determina o número de maneiras distintas de
ocorrência de um evento composto de duas ou mais etapas. Pode ser enunciado da seguinte forma:
Se um evento A pode ocorrer de m maneiras diferentes, para cada maneira de A
ocorrer, um evento B pode ocorrer de n maneiras diferentes; e para cada maneira de A e B
ocorrerem, um evento C pode ocorrer de p maneiras diferentes; então, o número de maneiras
diferentes de ocorrerem A, B e C é m ⋅ n ⋅ p .
Exemplo 1: Quantos e quais são os possíveis resultados quando lançamos uma moeda três vezes
consecutivas ?
Resolução: Vamos representar os resultados por meio de escrita (Árvore das possibilidades)
tomando
k = cara e C = coroa
10 lançamento
20 lançamento
30 lançamento
Resultados
K
K
C
(K,K,K)
(K,K,C)
C
K
C
(K,C,K)
(K,C,C)
K
C
K
C
(C,K,K)
(C,K,C)
(C,C,K)
(C,C,C)
K
K
C
C
Assim, cada terno ordenado acima representa um possível resultado: (K,K,K), (K,K,C),
(K,C,K), (K,C,C), (C,K,K) , (C,K,C), (C,C,K), (C,C,C) . Para efeito de cálculos devemos levar em
consideração que cada lançamento representa um evento (lançar uma moeda) e em cada um deles
existem dois resultados possíveis K e C, logo o total de resultados é dado pelo produto entre os
números que indicam a quantidade de resultados possíveis em cada um desses eventos :
10 L
possibilidades
2
20 L
.
2
30 L
.
2
= 8
www.chiquinho.org
ANÁLISE COMBINATÓRIA
Exemplo 2: (ENEM/02) O código de barras, contido na maior parte dos produtos industrializados,
consiste num conjunto de várias barras que podem estar preenchidas com cor escura ou não. Quando
um leitor óptico passa sobre essas barras, a leitura de uma barra clara é convertida no número 0 e a
de uma barra escura, no
número 1. Observe abaixo um exemplo simplificado de um código em um sistema de código com 20
barras.
Se o leitor óptico for passado da esquerda para a direita irá ler: 01011010111010110001
Se o leitor óptico for passado da direita para a esquerda irá ler: 10001101011101011010
No sistema de código de barras, para se organizar o processo de leitura óptica de cada código, devese levar em consideração que alguns códigos podem ter leitura da esquerda para a direita igual à
da direita para a esquerda, como o código 00000000111100000000, no sistema descrito acima.
Em um sistema de códigos que utilize apenas cinco barras, a quantidade de códigos com leitura da
esquerda para a direita igual à da direita para a esquerda, desconsiderando-se todas as barras
claras ou todas as escuras, é
(A) 14
(B) 12
( D) 6
(C) 8
(E) 4
Resolução: Da esquerda para a direita ou da direita para a esquerda temos 2 possibilidades
para os três primeiros algarismos e para os dois seguintes apenas uma possibilidade para
cada um deles, visto que os algarismos eqüidistantes dos extremos devem ser iguais. Assim:
DM UM C D U
2 . 2 .2.1. 1=8
possibilidades
Dentre as 8 possibilidades acima temos um código formado por todas as barras claras e um
outro com todas as barras escuras, logo apenas 6 códigos satisfazem ao problema.
Exemplo 3: Dados os algarismos 0, 1, 2, 3, 4 e 5 , determine quantos números naturais podemos
formar com 3 algarismos distintos.
Resolução: Lembrando que o algarismo das centenas não pode ser zero devido ao fato de que
nenhum número, em nosso sistema de numeração decimal, pode começar por zero (Salvo placas de
carro, senhas e outros), então:
0,1,2, 4 ou 5
1,2, 3 ,4 ou 5
centenas
possibilidades
5
0,1,2 ou 4
dezenas
.
5
unidades
.
4
= 100
www.chiquinho.org
ANÁLISE COMBINATÓRIA
Obs.: O algarismo sublinhado e em negrito indica, supostamente, que foi o escolhido dentre as
opções .
Exemplo 4: (ENEM/04) No Nordeste brasileiro, é comum encontrarmos peças de artesanato
constituídas por garrafas preenchidas com areia de diferentes cores, formando desenhos. Um
artesão deseja fazer peças com areia de cores cinza, azul, verde e amarela, mantendo o mesmo
desenho, mas variando as cores da paisagem (casa, palmeira e fundo), conforme a figura. O fundo
pode ser representado nas cores azul ou cinza; a casa, nas cores azul, verde ou amarela; e a
palmeira, nas cores cinza ou verde. Se o fundo não pode ter a mesma cor nem da casa nem da
palmeira, por uma questão de contraste, então o número de variações que podem ser obtidas para a
paisagem é
(A) 6
( B) 7
(C) 8
(D) 9
(E) 10
Resolução: Este é um problema que deve ser feito por partes, pois fixando cada uma das
possibilidades para o fundo resultará em um número de diferentes possibilidades para casa e para a
palmeira , veja:
Azul
possibilidades
Verde
ou
amarela
Verde
ou
cinza
fundo casa palmeira
1 . 2 .
2
=4
ou
fundo casa palmeira
possibilidades
1 . 3 .
1
=3
Cinza
Verde
Verde ,
amarela
ou azul
Então o número de variações que podem ser obtidas para a paisagem é 4 + 3 = 7.
www.chiquinho.org
ANÁLISE COMBINATÓRIA
Exemplo 5: Brenda possui 4 blusas diferentes e 5 saias diferentes. De quantos modos distintos ela
pode se vestir ?
Resolução:
possibilidades
blusas saias
4 .
5 = 20
Podemos apresentar os resultados acima através da árvore de possibilidades , veja:
B1
B2
B3
B4
S1 ( B1 ,S1 )
S2 ( B1 ,S2 )
S3 ( B1 ,S3 )
S4 ( B1 ,S4 )
S5 ( B1 ,S5 )
S1 ( B2 ,S1 )
S2 ( B2 ,S2 )
S3 ( B2 ,S3 )
S4 ( B2 ,S4 )
S5 ( B2 ,S5 )
S1 ( B3 ,S1 )
S2 ( B3 ,S2 )
S3 ( B3 ,S3 )
S4 ( B3 ,S4 )
S5 ( B3 ,S5 )
S1 ( B ,S )
S2 ( B4 ,S1 )
S3 ( B44 ,S32 )
S4 ( B4 ,S4 )
S5 ( B4 ,S5 )
Cada par ordenado acima representa uma possibilidade da Brenda se vestir.
II. Permutações Simples
Permutação simples de n elementos distintos é qualquer grupo ordenado desses n
elementos.
Para calcularmos uma permutação simples de n elementos usamos a seguinte fórmula:
Pn = n!
Exemplo 6 : Quantos são os números de 4 algarismos distintos que podemos formar com os
algarismos do número 2456 ?
Resolução: Este é um problema que consiste em apenas permutar os algarismos do número 2456 ,
então o total de números é dado por P4 = 4! = 24 .
www.chiquinho.org
ANÁLISE COMBINATÓRIA
Exemplo 7: (UERJ) Observe o quadrinho abaixo:
(O GLOBO , 03/01/93)
As quatro pessoas que conversavam no banco da praça poderiam estar sentadas em outra
ordem.
Considerando que o fumante ficou sempre numa das extremidades, o número de
ordenações possíveis é:
(A) 4
(B) 6
(C)
12
(D) 24
(E)
48
Resolução: O problema consiste em fixar o fumante nas extremidades e logo a seguir permutar
as outras pessoas nos lugares restantes. Veja:
F ___ ___ ___
possibilidades 1 . 3 . 2 . 1 = 6
ou
+
___ ___ ___ F
3 . 2 . 1 .1=6
P3 = 3!
P3 = 3!
Logo o número de ordenações possíveis é 12.
Exemplo 8: Com relação aos anagramas da palavra VIDA, qual é o número total deles ?
Obs.: Anagramas são palavras que se formam, com as letras de uma determinada palavra, mesmo
que não tenham significado. (Permutamos as letras da palavra primitiva)
Resolução: Como cada anagrama é uma permutação simples das letras V, I, D e A , então P4 = 4! = 24
Exemplo 9:(UFF) Com as letras da palavra PROVA podem ser escritos X anagramas que
começam por vogal e Y anagramas que começam e terminam por consoante. Os valores de X e Y
são , respectivamente:
(A)
48 e 36
(B) 48 e 72
(C) 72 e 36
(D) 24 e 36
(E) 72 e 24
www.chiquinho.org
ANÁLISE COMBINATÓRIA
Resolução: Primeiramente vamos determinar X:
A ou O
____ ___ ___ ___ ___ = 2. 24 = 48
Possibilidades 2 .
P4 = 4! = 24
P,R ou V
e determinaremos agora Y :
P ou V
___ ___ ___ ___ ___ = 3.6.2 = 36
Possibilidades 3 .
. 2
P3 = 3! = 6
Exemplo 10: (ESPM - SP) Permutam-se os algarismos 2,3,4,5,6 e 8 de todos os modos
possíveis sem repeti-los e escrevem-se os números assim obtidos em ordem crescente de
grandeza. Que posição ocupa o número 546 823 ?
Resolução: Para resolver esse tipo de problema, analisamos as possibilidades de cada
algarismo, em cada casa , separadamente ou não. Assim teremos um maior controle sobre a
posição de 546 823 .
2 ,3 ou 4
___ ___ ___ ___ ___ ___ (todos menores que 500 000) = 3 . 120 = 360
possibilidades 3
P5 = 5! = 120
2 ou 3
5 ___ ___ ___ ___ ___ (todos menores que 540 000) = 2 . 24 = 48
possibilidades 1 . 2 .
P4 = 4! = 24
2 ou 3
5 4 ___ ___ ___ ___
possibilidades 1 . 1 . 2 .
(todos menores que 546 000) = 2 . 6 = 12
P3 = 3! = 6
2 ou 3
5 4 6 ___ ___ ___
possibilidades 1 . 1 . 1 . 2
(todos menores que 546 800) = 2 . 2 = 4
P2 = 2! = 2
www.chiquinho.org
ANÁLISE COMBINATÓRIA
5 4 6 8 2 3
possibilidades 1 . 1 . 1 . 1 . 1 . 1 = 1
A posição do número 546 823 é 4250 , pois temos 360 + 48 + 12 + 4 = 424 números menores
que ele.
III. Permutações com elementos repetidos
Para calcularmos uma permutação com elementos repetidos usamos a fórmula:
n!
Pnn1 ,n 2 ,n3 ,...,n k =
, onde
n1 ! ⋅ n 2 ! ⋅ n 3 ! ⋅ ... ⋅ n k !
n1 + n 2 + n 3 + ... + n k = n .
Exemplo 11: Quantos são os anagramas da palavra PAPAI ?
Resolução: Em PAPAI temos 2 vezes a letra P ( n1 = 2 ) , 2 vezes a letra A ( n 2 = 2 ) e
somente um I ( n 3 = 1 ) , então:
5!
120
P52,2,1 =
=
= 30
2! ⋅ 2! ⋅ 1!
4
Exemplo 12: Quantos são os anagramas da palavra BANANA que começam e terminam por A ?
Resolução: Quando for fixado nos extremos a letra A , não haverá repetições para essa letra nas
outras posições e assim só haverá repetições para a letra N:
A ___ ___ ___ ___ A
Possibilidades 1 .
1
P42,1,1 =
= 12
4!
24
=
= 12
2! ⋅ 1! ⋅ 1! 2
Exemplo 13: Um menino se encontra numa extremidade O de uma sala retangular de 6 passos de
comprimento por 4 passos de largura, conforme a figura.
(Norte)
O
A
(Leste)
www.chiquinho.org
ANÁLISE COMBINATÓRIA
Se ele só pode dar um passo de cada vez, para o norte (N) ou para o leste (L) ,
calcule quantos caminhos existem da origem O ao ponto A. (Obs.: A figura mostra dois caminhos
diferentes)
Resolução: Observe que em cada caminho o menino deu dez passos, sendo 6 para o Leste e 4 para
o Norte, caracterizando assim uma permutação com elementos repetidos, pois esta regra será
comum para qualquer caminho que o menino escolha. Assim o total de caminhos é
P106,4 =
/
10! 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6!
=
= 210 .
/ ⋅ 4!
6!⋅ 4!
6!
IV. Arranjos simples
Arranjos simples de n elementos distintos, p a p, é todo agrupamento ordenado formado por
p elementos distintos escolhidos entre os n elementos dados.Calculamos o número de arranjos
simples da seguinte forma:
n!
A n,p =
(n − p)!
Exemplo 14: Com os algarismos 2, 4, 6, 8 e 9 quantos números de dois algarismos distintos
podemos formar ?
Resolução: Usando os algarismos 2 e 4, por exemplo, podemos formar os números 24 e 42,
assim temos um problema de arranjos simples , pois a ordem importa. O total de números
5!
5! 5 ⋅ 4 ⋅ 3!
/
= =
= 20 .
de dois algarismos é dado por A 5,2 =
(5 − 2)! 3!
3!
/
Exemplo 15: (CESGRANRIO) Durante a Copa do Mundo, que foi disputada por 24 países, as
tampinhas de Coca-cola traziam palpites sobre os países que se classificariam nos três
primeiros lugares (por exemplo : 10 lugar : Brasil ; 20 lugar : Nigéria ; 30 lugar : Holanda).
Se , em cada tampinha, os três países são distintos, quantas tampinhas
diferentes poderiam existir ?
(A) 69
(B) 2024
(C) 9562
( D)
12144
(E) 13824
Resolução: No exemplo citado acima temos uma das 6 possibilidades de resultados com
aqueles três países (basta permutá-los: P3 = 3! = 6 ), ou seja, a ordem é importante . Assim o
24!
24 ⋅ 23 ⋅ 22 ⋅ 21!
=
= 12.144
número de tampinhas diferentes é dado por A 24,3 =
(24 − 3)!
21!
Obs.: O problema acima pode ser feito pelo princípio multiplicativo, veja:
10 C
20 C 30 C
Possibilidades: 24 . 23 . 22 = 12.144
www.chiquinho.org
ANÁLISE COMBINATÓRIA
V. Combinações simples
Combinação simples de n elementos distintos, p a p , é todo agrupamento nãoordenado formado por p elementos distintos escolhidos dentre os n elementos dados.
Calculamos o número de combinações simples da seguinte forma:
n!
Cn,p =
p!(n − p)!
Exemplo 16: (UNIRIO/2003) O bufê de saladas de um restaurante apresenta alface, tomate,
agrião, cebola, pepino, beterraba e cenoura.
Quantos tipos de saladas diferentes podem ser preparadas com cinco desses
ingredientes, de modo que todas as saladas contenham alface, tomate e cebola ?
(A) 4
(B) 12
(C) 8
(D) 3
(E)
6
Resolução: Devemos escolher dois dos ingredientes restantes (agrião, pepino, beterraba e cenoura),
sem se importar com a ordem, para completar as saladas. Desse modo o total de saladas é dado por :
C4,2 =
/ 12
4!
4 ⋅ 3 ⋅ 2!
=
= =6
/ ⋅ 2!
2!⋅ (4 − 2)! 2!
2
Exemplo 17: (UERJ- 20 E.Q – 2007) Sete diferentes figuras foram criadas para ilustrar, em grupos
de quatro, o Manual do Candidato do Vestibular Estadual 2007. Um desses grupos está apresentado
a seguir.
Considere que cada grupo de quatro figuras que poderia ser formado é distinto de outro somente
quando pelo menos uma de suas figuras for diferente. Nesse caso, o número total de grupos distintos
entre si que poderiam ser formados para ilustrar o Manual é igual a:
(A) 24
( B)
35
(C) 70
(D) 140
Resolução: Como a ordem em que as figuras vão estar expostas não importa, então temos um
agrupamento que representa uma combinação. O número total de grupos é dado por :
C7,4 =
7!
7 ⋅ 6 ⋅ 5 ⋅ 4!
= 35
=
4!⋅ 3!
4! ⋅ 6
Exemplo 18: A partir de um grupo de 5 rapazes e 4 moças, quantas comissões de 4 elementos
podem ser formadas, havendo pelo menos uma moça na comissão ?
www.chiquinho.org
ANÁLISE COMBINATÓRIA
Resolução: Podemos determinar o total de grupos de 4 pessoas que podemos formar com as 9
pessoas, sem se importar com a ordem, e depois subtrair o número de grupos que só tem rapazes,
restando então os grupos com pelo menos uma moça. Veja :
2
Total de grupos : C9,4
9!
9 ⋅ 8 ⋅ 7 ⋅ 6 5! 9 ⋅ 8 ⋅ 7
=
=
=
= 126
4!⋅ 5!
24 4 ⋅ 5!
4
Número de grupos formados apenas por rapazes: C5,4 =
5!
5 ⋅ 4!
=5
=
4!⋅1! 4! ⋅1
Portanto o total de grupos com pelo menos uma moça é 126 – 5 = 121.
VI . Permutações Circulares
São as maneiras de se dispor elementos ao redor de um círculo.
Calculamos o número de permutações circulares da seguinte forma:
PC ( n ) = ( n − 1) !
Exemplo 19: De quantas maneiras diferentes 3 pessoas podem sentar-se ao redor de uma mesa
circular?
Resolução: Vamos observar os deslocamentos ordenados , no sentido anti-horário, de três pessoas
:A , B e C.
C
A
Observe que nas três situações ao lado todas as
pessoas possuem os mesmos vizinhos à esquerda e à
direita. As permutações apresentadas são idênticas.
B
C
A
B
B
C
A
Nas três situações seguintes todas as pessoas possuem os mesmos vizinhos à esquerda e à direita,
porém em relação às situações acima os vizinhos estão em posições contrárias.. As permutações
abaixo são idênticas entre si , mas distintas em relação as sequências anteriores.
Qualquer tentativa de se dispor as três pessoas de
maneira distintas ao redor de uma mesa circular acaba
repetindo uma das duas sequências: ABC (ABC CAB
BCA) ou ACB (ACB BAC CBA)
B
A
C
B
A
C
C
B
Deste modo existem apenas duas maneiras distintas
de três pessoas sentarem ao redor de uma mesa circular.
Usando a fórmula teremos : PC (3) = ( 3 − 1) ! = 2! = 2
www.chiquinho.org
A
ANÁLISE COMBINATÓRIA
VII . Partições Ordenadas e Partições não Ordenadas
Vamos considerar um conjunto A e n subconjuntos de A não vazios A1 , A 2 , ... , A n , tais que:
a) A i ∩ A j = ∅ ( para i ≠ j)
b) A1 ∪ A 2 ∪ ... ∪ A n = A
- Chamaremos de uma partição ordenada do conjunto A à sequência de conjuntos: ( A1 , A 2 , ... , A n )
Em uma sequência a ordem dos elementos (subconjuntos) é importante.
- Chamaremos de uma partição não ordenada do conjunto A ao conjunto: {A1 , A 2 , ... , A n }
A ordem dos elementos(subconjuntos) de um conjunto não é importante.
Vamos resolver alguns problemas combinatórios com auxílio dos conceitos acima.
Exemplo 20: De quantas maneiras podemos dividir 9 pessoas em uma barraca de 5 lugares e duas
de 2 lugares ?
Resolução: Cada uma das maneiras de se distribuir as 9 pessoas nas 3 barracas é uma partição
ordenada, ou seja, depende da ordem com que escolhemos as barracas para a distribuição:
__ __ __ __ __
barraca 1
__ __
barraca 2
__ __
barraca 3
Primeiramente escolheremos as 5 pessoas entre as 9 para ficarem na barraca 1. Isto pode ser feito
de C9,5 maneiras. (A ordem com que escolhemos as pessoas não importa).
Em seguida, entre as 4 pessoas restantes, escolheremos 2, para ficarem na barraca 2. Isto pode
ser feito de C4,2 maneiras.
Finalmente as 2 pessoas restantes podem ser escolhidas de C2,2 maneira para ocuparem a barraca
3..
Como para cada uma das combinações na barraca 1 tereemos C4,2 maneiras de dispor 2 pessoas
na barraca 2 e C2,2 maneira de dispor 2 pessoas na barraca 3, então o total de partições é:
C9,5 ⋅ C4,2 ⋅ C2,2 =
9! 4! 2!
⋅
⋅
= 756
5!4! 2!2! 2!0!
Isto é, existem 756 modos de dispormos as 9 pessoas nas 3 barracas.
Exemplo 21: (UFRJ-2007-N.Esp) Nove pessoas serão distribuídas em três equipes de três para
concorrer a uma gincana. O número de maneiras diferentes de formar as três equipes é menor
do que 300?
Resolução: Cada uma das maneiras de se distribuir as 9 pessoas nas 3 equipes é uma partição não
ordenada, ou seja, a ordem com que iremos formar as equipes não é importante devido ao fato do
www.chiquinho.org
ANÁLISE COMBINATÓRIA
número de pessoas ser igual em cada uma delas e assim permitir que três quaisquer das 9 pessoas
façam parte de qualquer uma das equipes :
__ __ __
equipe 1
__ __ __
equipe 2
__ __ __
equipe 3
Primeiramente escolheremos as 3 pessoas entre as 9 para compor a equipe 1. Isto pode ser feito
de C9,3 maneiras. (A ordem com que escolhemos as pessoas não importa).
Em seguida, entre as 6 pessoas restantes, escolheremos 3, para compor a equipe 2 . Isto pode ser
feito de C6,3 maneiras.
Finalmente as 3 pessoas restantes podem ser escolhidas de C3,3 maneira para compor a equipe
3...
Como para cada uma das combinações na equipe 1 teremos C6,3 maneiras de compor a equipe 2
e C3,3 maneira de compor a equipe 3, então o total de partições é:
C9,3 ⋅ C6,3 ⋅ C3,3 =
9! 6! 3!
⋅
⋅
= 1680
3!6! 3!3! 3!0!
Como, por exemplo , as três pessoas que estão na formação inicial da equipe 1 poderiam estar na
formação das equipes 2 ou 3, então há repetições desses grupos nas formações das equipes, por isso
precisamos dividir o número acima por 3! = 6 (permutação das equipes). Logo o número de partições
1680
não ordenadas é
= 280 e assim o número de maneiras de se formar as três equipes é menor que
6
300.
VIII . Soluções inteiras não negativas de uma equação linear
Teorema: O número de soluções inteiras não negativas da equação x1 + x 2 + ... + x n = k é:
( n + k − 1)!
r!( n − 1) !
Iremos em sala de aula desenvolver uma técnica de se calcular o número de soluções inteiras
não negativas e soluções inteiras positivas sem o uso da fórmula.
Exemplo 22:(UNIRIO) Uma pessoa quer comprar 6 empadas numa lanchonete. Há empada de
camarão, frango, legumes e palmito. Sabendo-se que podem ser compradas de zero a 6 empadas de
cada tipo, de quantas maneiras diferentes esta compra pode ser feita ?
Resolução: Considerex o número de empadas de camarão y o número de empadas de frango z o
número de empadas de legumes w o número de empadas de palmito , onde x, y, z e w ∈ ` e
x+y+z+w =6
Então o número de soluções inteiras não negativas da equação x + y + z + w = 6 é a solução do
problema.
www.chiquinho.org
ANÁLISE COMBINATÓRIA
( n + k − 1)! = ( 4 + 6 − 1)! = 9! =
r!( n − 1) !
6!( 4 − 1) ! 6!3!
3
4
9 ⋅ 8 ⋅ 7 ⋅ 6!
= 84
6! ⋅ 6 2
www.chiquinho.org