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
Combinação
O número de modos de se escolher p objetos de um total de n ≥ p é
Cp
n =
(
p
n
)
=
p!
n!(n− p)!
Vamos entender a fórmula pelo exemplo abaixo:
Exemplo 1: João possui um total de 10 frutas diferentes. De quantos modos ele pode escolher 3
frutas diferentes:
(a) para comer uma na sexta, uma no sábado outra no domingo?
(b) para fazer uma salada de frutas?
Resposta (a): 10.9.8=720, pois há 10 opções para sexta; 9 para sábado (desconsiderando o já
escolhido de sexta); 8 para domingo (desconsiderando os já escolhidos de sexta e sábado).
Resposta (b): Sejam a,b,c 3 frutas. O primeiro exerćıcio conta cada uma das combinações abaixo:
(a, b, c)
(a, c, b)
(b, a, c)
(b, c, a)
(c, a, b)
(c, b, a)
No exerćıcio 2, todas as 6 combinações acima são IGUAIS, pois não há ordenação (primeira, segunda
e terceira fruta). Para cada 6 = 3! (número de permutações de 3 determinadas frutas) combinações no
exemplo 1, gostaŕıamos de contar apenas 1, portanto a resposta é 10.9.8
3! = 10!
7!3! = C3
10
Exemplo 2: Para um time de futsal foram convocados 3 goleiros e 10 jogadores de linha. De
quantos modos é posśıvel montar a seleção titular com 1 goleiro e 4 jogadores de linha?
Resposta: Há C1
3 = 3!
2!1! = 3 formas de escolher o goleiro. Há também C4
10 = 10!
6!4! = 210 formas
de escolher 4 jogadores de linha. Portanto, há um total de C1
3 .C
4
10 = 630 formas de escolar o time.
Exemplo 3: Há um grupo de 10 pessoas, contando com Ana, Beatriz, Carla e Daniela. Quantas
comissões com cinco pessoas podemos formar:
a) ao todo?
b) nas quais Ana participa, mas Beatriz não?
c) nas quais pelo menos 3 dentre Ana, Beatriz, Carla e Daniela participam?
d) nas quais Ana ou Beatriz ou Carla ou Daniela participam, mas não as quatro juntas?
Resposta (a): Diretamente por combinação, a resposta é C5
10 =
(
10
5
)
= 252
Resposta (b): Considerando que Beatriz não será escolhida, sobram 9 pessoas no total; con-
siderando que Ana já foi escolhida, faltam escolher outras 4 pessoas dentre 8 no total. Portanto, a
resposta é: C4
8 =
(
8
4
)
= 70
1
Resposta (c): 3 ou 4 dentre Ana ou Beatriz ou Carla ou Daniela podem participar. Há C3
4C
2
6
maneiras em que 3 delas participam. Há C4
4C
1
6 maneiras em que 3 delas participam. Portanto, há um
total de C3
4C
2
6 + C4
4C
1
6 = 66 maneiras.
Resposta (d): Queremos todas as combinações, exceto aquelas nas quais nenhuma das 4 participa
e as quais todas as 4 participam. Portanto, a resposta é C5
10 − C5
6 − C1
6 = 240
Demonstrações combinatoriais
Demonstrações obtidas ao contar de duas maneiras diferentes.
Exemplo 1: Mostrar que
(
n
k
)
=
(
n
n−k
)
De um total de n integrantes de uma equipe esportiva, vamos escolher k para serem os titulares.
Do lado esquerdo, contamos o números de escolhas para os k titulares. Do lado direito, contamos o
números de escolhas para os n− k reservas.
Exemplo 2: Mostrar que n
(
n−1
k−1
)
= k
(
n
k
)
De um total de n pessoas, vamos escolher k para formar uma equipe. Dentre os k integrantes, 1
deles será o ĺıder da equipe. De quantas maneiras podemos montar esse grupo?
Solução 1 (lado esquerdo): Podemos escolher um ĺıder de
(
n
1
)
= n maneiras. Depois de escolhido o
ĺıder, podemos escolher os outros k − 1 integrantes da equipe de
(
n−1
k−1
)
maneiras.
Solução 2 (lado direito): Podemos determinar todos os k integrantes da equipe de
(
n
k
)
maneiras.
Depois, podemos selecionar um ĺıder dentre os k integrantes de
(
k
1
)
= k maneiras.
Exemplo 3: Mostrar que
(
m+n
r
)
=
r∑
k=0
(
m
r−k
)(
n
k
)
para m,n e r inteiros tais que r ≤ m e r ≤ n
Suponha que há m mulheres e n homens, dos quais formaremos um grupo com r pessoas.
Solução 1 (lado esquerdo): Escolhemos, dentre as m+ n pessoas no total, r para o grupo.
Solução 2 (lado direito): Podemos escolher:
• 0 homens e r mulheres
• 1 homem e r − 1 mulheres
• ...
• r homens e 0 mulheres
Somando todas as formas diferentes, obtemos
r∑
k=0
(
m
r−k
)(
n
k
)
Exemplo 4: Mostrar que
(
n
k
)
=
(
n−1
k
)
+
(
n−1
k−1
)
Suponha que vamos escolher k dentre os números 1,2,3,...,n.
Solução 1 (lado esquerdo): Solução direta.
Solução 2 (lado direito): Há
(
n−1
k
)
maneiras de fazer a escolha sem que o número 1 tenha sido
escolhido. Há também
(
n−1
k−1
)
maneiras de fazer a escolha de forma que o número 1 tenha sido escolhido.
2