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:
Permutação com repetição
Permutação com repetição
Tipo de permutação que considera elementos repetidos. O número de maneiras de se permutar n
objetos, contando com repetições, é
P a1,a2,...,ak
n =
n!
a1!a2!...ak!
em que a1 é o número de vezes em que um elemento se repete, a2 é o número de vezes em que
outro elemento se repete, etc.
Vamos entender a fórmula através do exemplo:
Exemplo 1: Quantos são os anagramas da palavra:
(a) A1PA2GA3 (modificamos as letras para forçá-las a serem distintas)
(b) APAGA
Resposta (a): Já vimos na aula de permutação que a resposta do item (a) é P5 = 5!, já que cada
permutação de A1PA2GA3 é um novo anagrama.
OBS: a fórmula de permutação com repetição funcionou também nesse caso sem repetição, pois
P 1,1,1,1,1
5 = P5 = 5!
Resposta (b): Note que o item (a) conta todas as combinações abaixo:
A1PA2GA3
A1PA3GA2
A2PA1GA3
A2PA3GA1
A3PA1GA2
A3PA2GA1
No item (b), todas as combinações acima são iguais, pois não há diferença entre os A’s. Para cada
6 = 3! combinações no item (a), gostaŕıamos de contar apenas 1, portanto a resposta é 5!
3! =
5!
3!1!1! =
P 3,1,1
5 = 20.
OBS: note que a fórmula da permutação com repetição também equivale ao seguinte procedimento:
- Escolha, de uma das
(
5
3
)
maneiras, 3 lugares dentre os 5 posśıveis para encaixar as letras A
- Sobraram 2 lugares. Escolha, de uma das
(
2
1
)
maneiras, um lugar para a letra P
- Há apenas uma maneira de colocar a letra G (no espaço restante)
Multiplicando o número de possibilidades em cada passo, obtemos:
(
5
3
)(
2
1
)
= 5!
3! = P 3,1,1
5
Exemplo 2: Quantos são os anagramas da palavra BATATA:
(a) sem restrições?
(b) que começam e terminam com T?
(c) que possuem as vogais juntas?
Resposta:
(a) Note que há uma letra B, 3 letras A e duas letras T, portanto a resposta é P 1,3,2
6 = 6!
1!3!2! = 60
(b) Começamos fixando um T como primeira letra e outro como última T. As 4 letras do meio (1
B e 3 A’s) podem ser permutadas de P 1,3
4 = 4!
3!1! = 4 maneiras.
1
(c) Podemos permutar 4 coisas: o bloco ”AAA” (que força as vogais a se juntarem), uma letra ”B”
e duas letras ”T”. Portanto, a resposta é P 1,2,1
4 = 4!
2! = 12
Exemplo 3: Observe o mapa abaixo:
Quantos são os caminhos de distância mı́nima (indo apenas baixo→cima e esquerda→direita):
(a) que vão de A para B?
(b) que vão de A para B passando por C?
Resposta:
(a) Todo caminho é necessariamente formado por 5 passos para cima e 6 para a direita.. Podemos
contar o número de caminhos A→ B pelo número de permutações com repetição de
↑↑↑↑↑→→→→→→
pois toda permutação representa um caminho válido e todo caminho válido é representado por uma
permutação.
Portanto, a resposta é P 5,6
11 = 11!
5!6! = 462.
(b) Podemos pegar o número de caminhos A → C e , pelo prinćıpio da multiplicação, multiplicar
pelo número de caminhos C → B.
O número de caminhos A→ C e o de C → B são o número de permutações de
↑↑↑↑→→→→ e de ↑→→ , respectivamente
Portanto, a resposta é P 4,4
8 P 2,1
3 = 8!
4!4!
3!
2!1! = 210
Exemplo 4: A cada instante de tempo, uma part́ıcula pode se mover oara a esquerda ou direita.
Quantos são os caminhos que a part́ıcula pode fazer em 10 instantes de tempo:
(a) ao total?
(b) retornando para o ponto onde iniciou?
Resposta:
(a) Como a cada um dos 10 instantes, a part́ıcula tem 2 opções (esquerda ou direita), a resposta é
210 = 1024
(b) Para retornar ao ponto inicial, a part́ıcula deve ir 5 vezes para a esquerda e 5 vezes para a
direita, em qualquer ordem. Portanto, queremos o número de permutações de
←←←←←→→→→→
Então, a resposta é P 5,5
10 = 10!
5!5! = 252
2