Princípio fundamental da contagem (PFC)
A Análise Combinatória é o ramo da matemática que se dedica ao estudo das técnicas de contagem dos elementos de um conjunto, obedecendo a certas regras. Assim como a Cinemática descreve o movimento sem a necessidade de explicar as suas causas. A Análise Combinatória estuda o número de possibilidades de ocorrência de um determinado evento sem, necessariamente, descrever todas as possibilidades.
O princípio fundamental da contagem é um conceito fundamental na análise combinatória, que é um ramo da matemática que lida com a contagem e organização de elementos em conjuntos. O princípio fundamental da contagem estabelece que se você tem um evento que pode ser dividido em duas ou mais etapas independentes e você deseja contar o número total de maneiras de realizar o evento completo, então você pode calcular o número total de maneiras de realizar cada etapa e multiplicá-los para obter o resultado final.
Em outras palavras, se você tem n maneiras de realizar a primeira etapa de um evento e m maneiras de realizar a segunda etapa do mesmo evento, então o número total de maneiras de realizar o evento completo é n vezes m.
Por exemplo, se você está escolhendo uma camisa e uma calça para vestir, e você tem 3 camisas diferentes e 4 calças diferentes para escolher, o princípio fundamental da contagem diz que você pode multiplicar o número de maneiras de escolher uma camisa (3 maneiras) pelo número de maneiras de escolher uma calça (4 maneiras) para encontrar o número total de maneiras de escolher um conjunto de roupas. Nesse caso, seriam 3 x 4 = 12 maneiras diferentes de escolher um conjunto de camisa e calça.
Exemplo 1
Temos três cidades X, Y e Z. Existem quatro rodovias que ligam X com Y e cinco que ligam Y com Z. Partindo de X e passando por Y, de quantas formas podemos chegar até Z?
Veja o esquema que representa as rodovias ligando as cidades, X, Y e Z.
Dissemos, na introdução, que a Análise Combinatória se dedica ao estudo das técnicas de contagem dos elementos de um conjunto, certo? Então, podemos extrair dois conjuntos desse problema.
A = {a1,a2,a3,a4}
Representa as rodovias que ligam X e Y.
B = {b1,b2,b3,b4,b5}
Representa as rodovias que ligam Y e Z.
É feito, então, o produto cartesiano entre os conjuntos A e B. Fixamos o primeiro elemento do conjunto A, enquanto variamos os demais.
A x B = {(a1,b1),(a1,b2) … (a4,b5)}
Cada maneira de se deslocar de X até Z pode ser considerado como um par de rodovias (ai,bj), onde ai ∈ A e bj ∈ B;
Logo, teremos 4 x 5 = 20 modos diferentes de sair de X e chegar até Z.
Exemplo 2
Quatro carros disputam uma corrida. Quantas são as possibilidades de chegada para os três primeiros lugares?
| 1º lugar | 2º lugar | 3º lugar | Ordem de chegada |
|---|---|---|---|
| carro 1 | carro 2 | carro 3 | c1,c2,c3 |
| carro 4 | c1,c2,c4 | ||
| carro 3 | carro 2 | c1,c3,c2 | |
| carro 4 | c1,c3,c4 | ||
| carro 4 | carro 2 | c1,c4,c2 | |
| carro 3 | c1,c4,c3 | ||
| carro 2 | carro 1 | carro 3 | c2,c1,c3 |
| carro 4 | c2,c1,c4 | ||
| carro 3 | carro 1 | c2,c3,c1 | |
| carro 4 | c2,c3,c4 | ||
| carro 4 | carro 1 | c2,c4,c1 | |
| carro 3 | c2,c4,c3 | ||
| carro 3 | carro 1 | carro 2 | c3,c1,c2 |
| carro 4 | c3,c1,c4 | ||
| carro 2 | carro 1 | c3,c2,c1 | |
| carro 4 | c3,c2,c4 | ||
| carro 4 | carro 1 | c3,c4,c1 | |
| carro 2 | c3,c4,c2 | ||
| carro 4 | carro 1 | carro 2 | c4,c1,c2 |
| carro 3 | c4,c1,c3 | ||
| carro 2 | carro 1 | c4,c2,c1 | |
| carro 3 | c4,c2,c3 | ||
| carro 3 | carro 1 | c4,c3,c1 | |
| carro 2 | c4,c3,c2 |
Decidimos, aqui, listar todas as possibilidades através de uma tabela. Veja que, para o primeiro lugar, temos 4 possibilidades (qualquer carro pode chegar no primeiro lugar); para o segundo lugar, temos 3 possibilidades, já que um dos carros já ocupou o primeiro lugar; para o terceiro lugar, temos 2 possibilidades, visto que as outras duas já foram preenchidas. Portanto, temos um total de 4 x 3 x 2 = 24 possibilidades.
Se um acontecimento pode ocorrer por várias etapas sucessivas e independentes, de tal modo que:
p1 é o número de possibilidades da 1ª etapa
p2 é o número de possibilidades da 2ª etapa
.
.
.
pk é o número de possibilidades da k-ésima etapa;
então, p1 . p2 … pk é o número total de possibilidades de o acontecimento ocorrer.
Vejamos mais dois exemplos.
Exemplo 3
Um homem encontra-se na origem de um sistema cartesiano ortogonal de eixos Ox e Oy. Ele pode dar um passo de cada vez, para norte (N) ou para leste (L). Quantas trajetórias ele pode percorrer se der exatamente 4 passos?
Pelo gráfico, podemos notar que cada trajetória é composta pela quádrupla-ordenada {a1,a2,a3,a4} onde a1 ∈ {N,L}, a2 ∈ {N,L}, a3 ∈ {N,L}, a4 ∈ {N,L}.
Visto que a trajetória é composta de 4 passos, cada passo se torna uma etapa. Logo, temos 2 • 2 • 2 • 2 = 16 possibilidades, já que para cada passo temos duas possibilidades.
Exemplo 4
Durante um exercício da marinha de guerra, empregam-se sinais luminosos para transmitir palavras por meio de código Morse. Esse código só emprega dois sinais: ponto e traço. As palavras transmitidas tinham de um a seis sinais. Qual o número de palavras que podiam ser transmitidas?
| Qtde | Letras/palavra | ||||||
|---|---|---|---|---|---|---|---|
| 2 |
|
||||||
| 2² |
|
||||||
| 2³ |
|
||||||
| 24 |
|
||||||
| 25 |
|
||||||
| 26 |
|
De acordo com o problema, as palavras podem ter de um a seis sinais. Exemplos de palavras: •, – •, • • – -.
A formação de uma palavra com apenas um sinal possui 1 etapa.
A formação de uma palavra com dois sinais possui 2 etapas.
.
.
.
A formação de uma palavra com seis sinais possui 6 etapas.
Para sabermos o total de palavras que podemos formar somamos, 2 + 22 + 23 + 24 + 25 + 26 = 2 + 4 + 8 + 16 + 32 + 64 = 126. Portanto, o número de palavras que podem ser transmitidas é de 126.