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:
Prinćıpio da adição e multiplicação
Análise Combinatória
A análise combinatória nos dá técnicas para contar sem que precisemos enumerar todos os elementos
de uma coleção.
Prinćıpio da multiplicação [Morgado et al. 2020]. :
Se uma decisão d1 pode ser tomada de x maneiras e se, uma vez tomada a decisão d1, a decisão
d2 puder ser tomada de y maneiras então o número de maneiras de se tomarem as decisões d1 e d2 é
xy.
OBS: Suponha que:
• uma decisão d1 pode ser tomada de n1 maneiras.
• para todo i ∈ {2, ..., n} vale que, tomadas as decisões d1, d2, d3,...,di−1, uma decisão di pode ser
tomada de ni maneiras
Então há
∏n
i=1 ni maneiras de tomar as decisões d1, d2,...,dn. Isso pode ser provado por indução a
partir do prinćıpio acima.
Exemplo 1: Quantas placas de carro no padrão Mercosul (LLLNLNN, onde L é uma das 26 letras
do alfabeto brasileiro e N é um número entre 0 e 9) poderiam ser formadas?
• A primeira letra pode ser escolhida de 26 maneiras diferentes.
• Dada a primeira escolha, a segunda letra pode ser escolhida de 26 maneiras diferentes.
• ...
• Dadas as 5 primeiros escolhas, o último d́ıgito pode ser escolhido de 10 maneiras diferentes.
A− Z × A− Z × A− Z × 0− 9 × A− Z × 0− 9 × 0− 9
26 26 26 10 26 10 10
Pelo prinćıpio da multiplicação, o número de combinações posśıveis é
26 ∗ 10 ∗ 10 ∗ 26 ∗ 10 ∗ 26 ∗ 26 ≈ 467 milhões
Exemplo 2: Há 5 estradas diferentes que conectam a cidade A e cidade B. Todas as 5 estradas
podem ser utilizadas tanto como ida A→ B quanto como volta B→A.
(a) Quantas formas diferentes alguém poderia fazer o caminho de ida A→B e volta B→A?
(b) Quantas formas diferentes alguém poderia fazer o caminho de ida A→B e volta B→A sem
utilizar na volta a mesma estrada que pegou na ida?
Solução (a): Há 5 possibilidades para ida. Dado qualquer escolha de caminho de ida, há 5 possi-
bilidades para volta. Portanto, a resposta é 5.5 = 25.
1
(b) Há 5 possibilidades para ida. Dada a escolha de um caminho para ida, há 4 possibilidades de
caminho para volta (excluindo a que utilizou na ida) Portanto, a resposta é 5.4 = 20.
Exemplo 3: Quantos números naturais pares de 2 algarismos distintos podem ser formados usando
os d́ıgitos 1,2,3 ou 4?
Escolhendo inicialmente o primeiro d́ıgito:
1, 2, 3 ou 4 × ?
4 ?
O número de possibilidades para o segundo d́ıgito depende se foi escolhido um número par ou ı́mpar
como primeiro d́ıgito.
O prinćıpio da multiplicação não pode ser utilizado diretamente dessa maneira.
Outra solução: Escolhendo inicialmente o segundo d́ıgito:
1, 2, 3 ou 4, exceto o segundo d́ıgito × 2 ou 4
3 2
A resposta é 2.3=6
Frase de [Morgado et al. 2020]: ”Pequenas dificuldade adiadas costumam transformar-se em
grandes dificuldades. Se alguma decisão é mais complicada que as demais, ela deve ser tomada em
primeiro lugar.”
Prinćıpio da adição
Prinćıpio baseado no seguinte resultado:
• Se A1, A2,...,An é uma famı́lia de conjuntos dois a dois disjuntos (Ai ∩ Aj = ∅ para qualquer
i, j ∈ {1, 2, ..., n} com i ̸= j), então | ∪n
i=1 Ai| =
∑n
i=1 |Ai|
Exemplo: Quantos números pares se escrevem com dois algarismos distintos?
Começando pelo segundo d́ıgito:
? × 0, 2, 4, 6 ou 8
? 5
O número de possibilidades para o primeiro d́ıgito depende se o 0 foi escolhido como segundo d́ıgito
(o primeiro d́ıgito não pode ser 0, pois, nesse caso, o número seria de apenas 1 d́ıgito).
Alternativa: sejam
• A o conjunto dos números de dois algarismos distintos cujo segundo d́ıgito é 2,4,6 ou 8.
• B o conjunto dos números de dois algarismos distintos cujo segundo d́ıgito é 0.
Calculando |A|:
1− 9, exceto segundo d́ıgito × 2, 4, 6 ou 8
8 4
Calculando |B|:
1− 9 × 0
9 1
Note que A e B são disjuntos (não há numero cujo último algorismo seja 0 e seja 2,4,6 ou 8 ao
mesmo tempo)! Note também que A∪B representa o conjunto de todos os números que nos interessam
para resolver o exerćıcio. Portanto, a resposta é |A ∪B| = |A|+ |B| = 8 ∗ 4 + 9 ∗ 1 = 41
2
Exemplo: De quantas maneiras podemos, possuindo um total de 5 cores, colorir as partes 1,2,3 e
4 da figura a seguir, sem que partes adjacentes possuam a mesma cor?
Primeira tentativa:
parte 1 parte 2 parte 3 parte 4
uma das 5 cores × cor diferente da parte 1 × cor diferente da parte 1 × ?
5 4 4 ?
O número de formas de colorir a parte 4 depende se as cores 2 e 3 são iguais ou diferentes.
Alternativa: sejam
• A o conjunto das colorações que satisfazem as restrições e que as cores em 2 e 3 são iguais.
• B o conjunto das colorações que satisfazem as restrições e que as cores em 2 e 3 são diferentes.
Calculando |A|:
parte 1 parte 2 parte 3 parte 4
uma das 5 cores × cor diferente da parte 1 × mesma cor que a parte 2 × cor diferente de 2 e de 3
5 4 1 4
já que, por mais que a parte 4 tenha que possuir uma cor diferente de 2 e de 3, ainda temos 4
possibilidades pois as cores 2 e 3 são iguais.
Calculando |B|:
parte 1 parte 2 parte 3 parte 4
uma das 5 cores × cor diferente da parte 1 × cor diferente das partes 1 e 2 × cor diferente de 2 e de 3
5 4 3 3
já que, como sabemos que as partes 2 e 3 tem cores diferentes, sobram apenas 3 possibilidades para a
parte 4.
Note que A e B são disjuntos (não existe coloração tal que as cores em 2 e 3 são iguais e são diferentes
ao mesmo tempo)! Note também que A ∪ B representa o conjunto de todas as colorações que nos
interessam para resolver o exerćıcio. Portanto, a resposta é |A∪B| = |A|+|B| = 5∗4∗1∗4+5∗4∗3∗3 =
260
3