Análise Combinatória e Probabilidades

Prévia do material em texto

Análise Combinatória, Probabilidades e Aplicações
Curso de Verão 2024 - IME/USP
Análise Combinatória:
Combinação completa
Combinação completa
O número de formas de se escolher p objetos, distintos ou não, dentre um total de n tipos de objetos é
CRp
n =
(
n+ p− 1
p
)
(1)
OBS: Não confundir com Cp
n, que é o número de formas de se escolher p objetos distintos dentre
um total de n.
Equivalentemente, CRp
n é o número de soluções inteiras não negativas de
x1 + x2 + ...+ xn = p
Vamos entender o motivo da fórmula (1) através do exemplo:
Exemplo 1: Quantas são as soluções inteiras não negativas de
x1 + x2 + x3 + x4 = 7
Note que toda solução da equação acima se associa (de 1:1) a uma permutação de
|||||||+++
Alguns exemplos dessa associação:
2 + 4 + 0 + 1 = 7 equivale a ||+ ||||++|
0 + 2 + 0 + 5 = 7 equivale a + ||++|||||
Logo, queremos saber o número de permutações de 7 śımbolos | e 3 (ou seja, n-1) śımbolos +.
Por permutação com repetição, a resposta é P 7,3
10 = 10!
7!3! =
(
10
7
)
= CR7
4
Exemplo 2: Há 3 sabores de sucos. Quantas são as formas de escolher até 5 sucos?
Resposta: Queremos o número de soluções inteiras não negativas de
x1 + x2 + x3 ≤ 5
Primeira alternativa: Podemos considerar as soluções de todas as 6 opções abaixo:
x1 + x2 + x3 = 5
x1 + x2 + x3 = 4
x1 + x2 + x3 = 3
x1 + x2 + x3 = 2
x1 + x2 + x3 = 1
x1 + x2 + x3 = 0
A resposta seria CR5
3 + CR4
3 + CR3
3 + CR2
3 + CR1
3 + CR0
3 = 56.
1
Segunda alternativa:
Podemos considerar uma variável ”folga” y = 5 − (x1 + x2 + x3). Há uma relação 1:1 entre as
soluções inteiras não negativas de x1 +x2 +x3 ≤ 5 e as de x1 +x2 +x3 + y = 5. Por essa equivalência,
a resposta é CR5
4 =
(
4+5−1
5
)
= 56.
Exemplo 3: Numa venda há 3 sabores de sucos: limão, laranja e tamarindo. De quantas formas
podemos escolher 20 sucos, sendo no mı́nimo 2 de limão, 4 de laranja e 2 de tamarindo.
Queremos o número de soluções não negativas de
x1 + x2 + x3 = 20, com x1 ≥ 2, x2 ≥ 4, x3 ≥ 2
Fazendo y1 = x1−2, y2 = x2−4, y3 = x3−2, podemos calcular o número de soluções não negativas
de
y1 + 2 + y2 + 4 + y3 + 2 = 20 ou, equivalentemente y1 + y2 + y3 = 12, com y1 ≥ 0, y2 ≥ 0, y3 ≥ 0
Portanto, a resposta é CR12
3 =
(
14
12
)
= 91.
Exemplo 4: Numa sala há 9 cadeiras alinhadas. De quantas formas 3 pessoas (A, B e C) podem
se sentar de modo que entre quaisquer duas pessoas existam pelo menos duas cadeiras vazias?
Resposta:
Primeiramente, podemos escolher a ordem com que A, B e C se sentarão (quem fica à esquerda,
quem fica ao centro e quem fica à direita) de P3 = 3! maneiras.
A B C
1 2 3 4
Para cada ordenação escolhida (no exemplo acima: A,B,C da esquerda para direita), resta deter-
minar o número de cadeiras vazias nas posições 1,2,3 e 4, que no total somam 6 = 9− 3.
Queremos saber o número de soluções inteiras não negativas de x1 + x2 + x3 + x4 = 6, com
x2 ≥ 2 e x3 ≥ 2. Equivalentemente, calculamos o número de soluções inteiras não negativas de
y1 + y2 + y3 + y4 = 2, que é CR2
4 =
(
5
2
)
= 10
Portanto, a resposta é P3 ∗ CR2
4 = 60
Exemplo 5: Quantos anagramas de PIRACICABA não possuem nenhum par de A’s juntos?
Dividimos a palavra em 4 espaços:
A A A
1 2 3 4
e cada espaço pode ser ocupado por um determinado número de letras, somando 7 (número de
letras que não são A). Mas temos a restrição que x2 ≥ 1 e x2 ≥ 1 já que os espaços do meio não podem
estar vazios.
O número de soluções inteiras não negativas de x1 + x2 + x3 + x4 = 7 com x2 ≥ 1 e x3 ≥ 1 é igual
ao de soluções inteiras não negativas de y1 + y2 + y3 + y4 = 5, ou seja, CR5
4 =
(
8
5
)
= 56.
Há 56 formas de determinar a quantidade de letras entre cada A. Um deles é o exemplo abaixo,
em que (x1, x2, x3, x4) = (1, 3, 1, 2)
A A A
Resta determinar quais as letras que ficarão em cada lugar. Isso pode ser feito de P 2,2,1,1,1
7 = 1260
maneiras.
Portanto, a resposta é 56 ∗ 1260 = 70.560
2