Análise combinátoria

Prévia do material em texto

Análise 
combinatória
Fatorial de um número natural
◼ Se n é um número natural (n ≥ 2), o produto de
todos os naturais de n até 1, é chamado de fatorial
de n (símbolo: n!). Ou seja, é a multiplicação de
todos os números naturais de 𝒏 até 𝟏.
❖ 3! = 3.2.1 = 6
n! = n(n – 1)(n – 2). ... .3.2. 1
❖ 6! = 6.5.4.3.2.1 = 720
Em geral,
Propriedade do fatorial
◼ O fatorial de um número natural é igual ao produto
deste pelo fatorial do seu antecessor.
❖ 6! = 6.5.4.3.2.1
❖ 10! = 10.9.8.7.6.5.4.3.2.1 = 10.9.8!
❖ 15! = 15.14! = 15.14.13! = 15.14.13.12! = ...
n! = n(n – 1)! = n(n – 1)(n – 2)! = ...
Em geral
= 6.5!
Exemplos
◼ A propriedade anterior é útil na simplificação do
cálculo de expressões que envolvem o fatorial.
❖
15!
13!
=
15.14.13!
13!
= 15.14 = 210
❖
10! + 8!
8!
=
10.9.8! + 8!
8!
=
8!(10.9 + 1)
8!
= 81
Exemplos
◼ Resolver a equação n!
(n – 2)! 
= 30
O fatorial só é definido para n – 2 ≥ 0 ⇒ n ≥ 2
n!
(n – 2)! 
= 30 ⇒
n(n – 1)(n – 2)!
(n – 2)! 
= 30
⇒ n(n – 1) = 30 ⇒ n = 6
Permutação simples
Permutação simples
◼ Definição: Dado um conjunto de 𝒏 elementos
distintos, chama-se permutação simples dos 𝒏
elementos qualquer agrupamento ordenado
(sequência) desses 𝒏 elementos. O número de
permutações simples de n elementos é indicado por
𝑷𝒏.
◼ Permutar é trocar a ordem dos elementos, a
permutação entre letras chamamos de anagrama.
◼ Calculamos permutação simples por,
𝑷𝒏 = 𝒏(𝒏 – 𝟏)(𝒏 – 𝟐).… . 𝟏 = 𝒏!
Prof. Jorge
Exemplos
◼ O número de permutações simples de 6 elementos é
𝑷𝟔 = 𝟔! = 𝟔. 𝟓. 𝟒. 𝟑. 𝟐. 𝟏 = 𝟕𝟐𝟎
◼ O número de permutações simples de 5 elementos é
𝑷𝟓 = 𝟓. 𝟒. 𝟑. 𝟐. 𝟏 = 𝟏𝟐𝟎
Observação: Todas as questões de permutação podem ser
resolvidas usando o principio multiplicativo.
Exemplos
◼ Chama-se anagrama de uma palavra, toda “palavra”
(com ou sem significado) obtida, trocando-se suas
letras de posição. Consideremos todos os anagramas
da palavra UNIVERSO.
a) Qual é o total de anagramas?
b) Quantos começam por consoante e terminam por
vogal?
c) Quantos têm as letras R, S, O juntas, nesta
ordem?
d) Quantos têm as letras R, S, O juntas, em
qualquer ordem?
Exemplos - Respostas
a) Qual é o total de anagramas?
P8 = 8.7.6.5.4.3.2.1 = 40 320 anagramas
Vogal Cons. 
b) Quantos começam por consoante e terminam por
vogal?
A palavra tem 4 vogais e 4 consoantes.
P6
4 . 4 . P6 = 11 520 
4 opç. 4 opç.
= 4 . 4 . 6.5.4.3.2.1 
U RSO N I V E
Exemplos - Respostas
c) Quantos têm as letras R, S, O juntas, nesta
ordem?
P6
P6 = 6.5.4.3.2.1 = 720 
U RSO N I V E
P3
d) Quantos têm as letras R, S, O juntas, em qualquer
ordem?
P6
P3 . P6 = 720 = 6 . 6.5.4.3.2.1 
Permutações com 
elementos repetidos
Permutações com repetição
◼ De maneira geral, o total de permutações de n
elementos, se um deles aparece a vezes, outro b
vezes, outro c vezes, ... é
n!
a!b!c!...
Pn
a, b, c,... =
Permutações com repetição
◼ Vamos analisar o que ocorre com o número de
anagramas de uma palavra, quando ela tem letras
repetidas.
Quantos anagramas tem a palavra ARARA?
5!
2!3!
=
120
2.6
= 10
AAARR AARAR AARRA ARAAR ARARA
ARRAA RAAAR RAARA RARAA RRAAA
P5
2,3 =
Prof. Jorge
Exemplos
◼ Considere todos os anagramas da palavra PARALELA.
a) Qual é o total de anagramas?
b) Quantos começam por vogal ?
◼ Considere todos os anagramas da palavra PARALELA.
a) Qual é o total de anagramas?
8!
3!.2!
P8
3, 2, 1, 1, 1 = =
8.7.6.5.4.3!
2.3!
= 3 360
Exemplos - Respostas
Exemplos - Respostas
b) Quantos começam por vogal?
• Começando por E
E 
7!
3!.2!
P7
3, 2, 1, 1 = =
7.6.5.4.3!
2.3!
= 420
• Começando por A
A 
7!
2!.2!
P7
2, 2, 1, 1 = =
7.6.5.4.3.2
4
= 1 260
Total = 420 + 1 260 = 1 680 anagramas
Exemplos
◼ A figura mostra uma superfície azulejada. Uma
formiga sai do ponto A e quer chegar ao ponto B,
onde há um grão de açúcar. Ela só anda sobre os
sulcos entre os azulejos, mas pretende percorrer o
menor caminho possível. Quantos trajetos diferente a
formiga pode utilizar?
A
B DCDCDCDCDCDD
12!
7!.5!
P12
7, 5 =
P12
7, 5 = 792
Permutação circular
Prof. Jorge
◼ As permutações circulares são agrupamentos, em
círculos, de 𝑛 elementos distintos em que os grupos
formados diferenciam apenas a ordem de seus
elementos. Neste tipo de permutação, o que define o
local de uma pessoa ou objeto são as duas pessoas
(ou objetos) que estão ao seu lado.
De modo geral, o total de permutações circulares de 𝒏
elementos é
Permutação circular
𝑷𝒏 = 𝒏 − 𝟏 !
Prof. Jorge
Exemplos
◼ Uma família é composta por seis pessoas: o pai, a mãe e quatro
filhos. Num restaurante, essa família vai ocupar uma mesa
redonda. Em quantas disposições diferentes essas pessoas
podem se sentar em torno da mesa?
RESPOSTA:
𝑷𝒏 = 𝒏 − 𝟏 ! → 𝑷𝟔 = 𝟔 − 𝟏 ! = 𝟓! = 𝟓. 𝟒. 𝟑. 𝟐. 𝟏 = 𝟏𝟐𝟎.
Essas pessoas podem sentar de 120 maneiras diferentes envolta
da mesa.
Prof. Jorge
Exemplos
◼ Uma família é composta por seis pessoas: o pai, a mãe e quatro
filhos. Num restaurante, essa família vai ocupar uma mesa
redonda. Em quantas disposições diferentes essas pessoas
podem se sentar em torno da mesa de modo que o pai e a mãe
fiquem juntos?
RESPOSTA:
Como queremos o pai e a mãe juntos iremos contar os dois como sendo
uma única pessoa, assim teremos apenas 5 pessoas da família para
permutar em volta da mesa.
𝑷𝒏 = 𝒏 − 𝟏 ! → 𝑷𝟓 = 𝟓 − 𝟏 ! = 𝟒! = 𝟒. 𝟑. 𝟐. 𝟏 = 𝟐𝟒.
Essas pessoas podem sentar de 24 maneiras diferentes envolta da mesa.
Arranjo simples
Arranjo simples
◼ Arranjo simples dos n elementos de um conjunto A,
tomados 𝒑 a 𝒑 (𝒑 ≤ 𝒏), é cada agrupamento ordenado
que contém, sem repetição, 𝒑 elementos distintos
escolhidos entre os 𝒏 possíveis.
O número de arranjos simples de n
elementos, tomados p a p, é indicado por An,p.
Observação:
◼ A ordem importa e não há repetição.
◼ Diferente da permutação o arranjo simples na usa todos os
elementos.
Número de Arranjo simples
◼ Vamos ver agora como calcular o número de
arranjos no caso geral de n elementos tomados
p a p, com 𝟎 ≤ 𝒑 < 𝒏, indicado por,
𝑨
𝒏,𝒑 =
𝒏!
𝒏−𝒑 !
Observação:
◼ Note que a permutação é um caso particular de arranjo,
que ocorre quando 𝒑 = 𝒏.Nesse caso, temos:
𝑨
𝒏,𝒑 =
𝒏!
𝒏−𝒑 !
=
𝒏!
𝟎
=𝒏!= 𝑷𝒏
Exemplos
◼ Utilizando-se, sem repetição, os algarismos 1, 3, 4, 5,
6, 7 e 9, quantos números distintos podemos formar
a) De 4 algarismos?
b) Ímpares, de 3 algarismos?
Exemplos
◼ Utilizando-se, sem repetição, os algarismos 1, 3, 4, 5,
6, 7 e 9, quantos números distintos podemos formar
a) De 4 algarismos?
A7,4 = 7.6.5.4 = 840
ímpar
b) Ímpares, de 3 algarismos?
A6,2
5 opções
5 . A6,2 = 150 = 5 . 6.5
Exemplos
◼ Um torneio de futebol é disputado por 8 equipes: A,
B, C, D, E, F, G e H.
a) Quantas são as alternativas de definição dos 4
primeiros colocados?
b) Se a equipe E já foi declarada campeã
antecipadamente, quantas são as alternativas de
definição do 2.º ao 4.º colocado?
Exemplos
◼ Um torneio de futebol é disputado por 8 equipes: A,
B, C, D, E, F, G e H.
a) Quantas são as alternativas de definição dos 4
primeiros colocados?
A8,4 = 1 680 = 8.7.6.5
b) Se a equipe E já foi declarada campeã
antecipadamente, quantas são as alternativas de
definição do 2.º ao 4.º colocado?
A7,3 = 210 = 7.6.5
Combinação simples
Combinação simples
◼ Tenho 5 amigos (A, B, C, D, E) e quero convidar 3
deles para a festa de meu aniversário. Quantas
alternativas tenho?
O meu problema é escolher apenas 3 dos 5 amigos.
✓ Dizemos que cada um desses agrupamentos é uma
combinação simples de 5 elementos, tomados 3 a 3.
{A, B, C} {A, B, D} {A, B, E} {A, C, D} {A, C, E}
{A, D, E} {B, C, D} {B, C, E} {B, D, E} {C, D, E}
No total são 10 maneiras diferentes. ⇒ C5,3 = 10
Combinação simples
◼ Combinação simples dos n elementos de um
conjunto A, tomados p a p (p ≤ n), é cada
agrupamento não-ordenado que contém, sem
repetição, p elementos de A.
Onúmero de combinações simples de n
elementos, tomados p a p, é indicado por Cn,p.
Cálculo no total de Combinações simples
◼ O cálculo do número de combinações simples está
relacionado ao cálculo do número de arranjos
simples e de permutações simples.
A formação de arranjos simples envolve duas etapas:
1ª etapa
Formação das 
combinações 
simples
2ª etapa
Formação das 
permutações 
simples
Resultado
Formação dos 
arranjos 
simples
Cn,p . Pp = An,p ⇒ Cn,p =
An,p
Pp
P2
10.9.8.7
4.3.2.1
A10,4
P4
12.11.10
3.2.1
A12,3
P3
(n – 1).(n – 2)
2
An – 1,2
Exemplos
◼ C10,4 = = = 210
◼ C12,3 = = = 220
◼ Cn – 1,2 = =
Exemplos
◼ Duas pessoas de um grupo de amigos serão
escolhidas para cuidarem dos preparativos de uma
festa. A escolha pode ser feita de 21 modos
diferentes. Quantas pessoas há no grupo?
P2
n.(n – 1)
2
Cn,2 = 21
An,2
= 21⇒
= 21⇒
n.(n – 1) = 42⇒ n = 7⇒
Exemplos
◼ Um grupo é formado por 7 alunos e 4 professores. De
quantos modos pode-se formar uma comissão de:
a) 5 pessoas?
b) 7 pessoas, com exatamente 3 professores?
c) 4 pessoas, com pelo menos 3 professores?
d) 3 pessoas, com pelo menos 1 professor?
11.10.9.8.7
5.4.3.2.1
A11,5
P5
Exemplos
◼ Um grupo é formado por 7 alunos e 4 professores. De
quantos modos pode-se formar uma comissão de:
a) 5 pessoas?
C11,5 = = = 462
7.6.5.4
4.3.2.1
4.3.2
3.2.1
Exemplos
◼ Um grupo é formado por 7 alunos e 4 professores. De
quantos modos pode-se formar uma comissão de:
b) 7 pessoas, com exatamente 3 professores?
C7,4 . C4,3 = .
1ª etapa
Escolher 4 
alunos
2ª etapa
Escolher 3 
professores
= 35 . 4 = 140
C7,4 C4,3
Exemplos
◼ Um grupo é formado por 7 alunos e 4 professores. De
quantos modos pode-se formar uma comissão de:
c) 4 pessoas, com pelo menos 3 professores?
7C7,1 . C4,3 = .
1ª etapa
Escolher 1 
aluno
2ª etapa
Escolher 3 
professores
4.3.2
3.2.1
= 7 . 4 = 28
Temos 2 hipóteses:
1ª hipótese:
C7,1 C4,3
Exemplos
◼ Um grupo é formado por 7 alunos e 4 professores. De
quantos modos pode-se formar uma comissão de:
c) 4 pessoas, com pelo menos 3 professores?
C4,4 =
Escolher 4 professores
4.3.2.1
4.3.2.1
= 1
Pelo princípio aditivo, 28 + 1 = 29 maneiras
Temos 2 hipóteses:
2ª hipótese:
Exemplos
◼ Um grupo é formado por 7 alunos e 4 professores. De
quantos modos pode-se formar uma comissão de:
d) 3 pessoas, com pelo menos 1 professor?
C11,3 =
11.10.9
3.2.1
= 165
Total de 
comissões de 
3 pessoas
Total de comissões 
de 3 pessoas, só 
com alunos
menos
C7,3 =
7.6.5
3.2.1
= 35
165 – 35 = 130 maneiras.
Exemplos
◼ Duas retas r e s são paralelas. Tomam-se 5 pontos
em r e 6 pontos em s. Com vértices nesses pontos,
quantos triângulos e quantos quadriláteros convexos
podemos construir?
Veja a ilustração da situação.
r
s
Exemplos
◼ Duas retas r e s são paralelas. Tomam-se 5 pontos
em r e 6 pontos em s. Com vértices nesses pontos,
quantos triângulos e quantos quadriláteros convexos
podemos construir?
Total de triângulos.
(2 pontos de r e 1 de s) ou (1 ponto de r e 2 de s)
C5,2 . C6,1
5.4
2.1
. 6
C5,1 . C6,2+
6.5
2.1
5 .
C5,2 . C6,1 + C5,1 . C6,2 = 60 + 75 = 135
Exemplos
◼ Duas retas r e s são paralelas. Tomam-se 5 pontos
em r e 6 pontos em s. Com vértices nesses pontos,
quantos triângulos e quantos quadriláteros convexos
podemos construir?
Total de quadriláteros é obtido escolhendo-se 4 pontos, 
sendo 2 de r e 2 de s.
C5,2 . C6,2 =
5.4
2.1
6.5
2.1
. = 10. 15 = 150
Distinguindo permutações, 
arranjos e combinações 
simples
Arranjos, combinações ou permutações?
ArranjoOrdenado
Escolher e ordenar 
os escolhidos
CombinaçãoNão-ordenado
Só escolher os 
elementos
PermutaçãoOrdenado
Só ordenar os 
elementos (todos)
Nome do 
agrupamento
Tipo de 
agrupamento
Critério de 
formação