v1 · padrão canônico

Lição 36 — Princípio Fundamental da Contagem

PFC: se uma tarefa tem k etapas independentes com n₁, n₂, …, nₖ opções cada, o total de sequências possíveis é o produto. Princípio aditivo, fatorial e aplicações.

Used in: 1.º ano do EM (15 anos) · Equiv. Math A japonês · Equiv. Klasse 10 alemã

N = n_1 \times n_2 \times \cdots \times n_k

O Princípio Fundamental da Contagem: se uma tarefa se divide em $k$ etapas independentes, com $n_i$ escolhas na $i$ -ésima etapa, o número total de sequências possíveis é o produto $n_1 \times n_2 \times \cdots \times n_k$ . O conector "E" entre etapas gera multiplicação; o conector "OU" entre alternativas mutuamente exclusivas gera adição.

Choose your door

Rigorous notation, full derivation, hypotheses

Enunciado rigoroso e princípio aditivo

Princípio Multiplicativo (PFC)

"Se você tiver $m$ maneiras de fazer uma coisa e $n$ maneiras de fazer outra, então há $m \cdot n$ maneiras de fazer as duas coisas." — OpenStax College Algebra 2e, §11.5

A justificativa formal: o conjunto de todas as sequências é o produto cartesiano $E_1 \times E_2 \times \cdots \times E_k$ , e $|A \times B| = |A| \cdot |B|$ (provado por indução). O PFC é exatamente esse teorema.

Princípio Aditivo

Conector entre etapas	Operação
"E" — etapas sequenciais independentes	multiplicação
"OU" — alternativas mutuamente exclusivas	adição

"O Princípio da Adição afirma que se há $m$ resultados no evento $A$ e $n$ resultados no evento $B$ , e $A$ e $B$ são mutuamente exclusivos, então há $m + n$ resultados no evento $A$ ou $B$ ." — OpenStax College Algebra 2e, §11.5

Fatorial

Árvore de possibilidades

Uma árvore de decisão com $k$ níveis representa graficamente o PFC: cada nó no nível $i$ gera $n_i$ filhos. O total de folhas é $n_1 \times n_2 \times \cdots \times n_k$ .

Árvore com 3 etapas no 1.º nível e 2 no 2.º nível: 6 folhas = 3 × 2. O PFC em ação.

Funções e subconjuntos via PFC

Total de funções $f: A \to B$ com $|A| = m,\, |B| = n$ : $n^m$ (cada elemento de $A$ tem $n$ imagens independentes).
Total de subconjuntos de $S$ com $|S| = n$ : $2^n$ (cada elemento é incluído ou excluído).
Funções injetoras $f: A \to B$ ( $m \leq n$ ): $n \cdot (n-1) \cdots (n-m+1) = \frac{n!}{(n-m)!}$ — base do arranjo (Lição 37).

Exemplos resolvidos

Example— 2· PFC com três etapas — placa de veículo

Problema: Uma placa de veículo no padrão antigo (antes do Mercosul) era formada por 3 letras seguidas de 4 dígitos numéricos. Admitindo 26 letras e dígitos 0-9 com repetição permitida, quantas placas distintas eram possíveis?

Estratégia: 7 etapas independentes — 3 de escolha de letra e 4 de escolha de dígito. Aplique o PFC.

Resolução:

Letras: cada uma das 3 posições tem 26 opções. Subtotal: $26^3 = 17\,576$ .
Dígitos: cada uma das 4 posições tem 10 opções. Subtotal: $10^4 = 10\,000$ .
PFC: $26^3 \times 10^4 = 17\,576 \times 10\,000 = 175\,760\,000$ .

Verificação: Ordem de grandeza: $\approx 1{,}8 \times 10^8$ . O Brasil tinha em 2019 cerca de 100 milhões de veículos — o espaço de $1{,}8 \times 10^8$ placas era suficiente. Consistente com o fato histórico de que o sistema funcionou por décadas.

Fonte. OpenStax College Algebra 2e, §11.5 — licença CC-BY 4.0.

Example— 3· Princípio aditivo — alternativas mutuamente exclusivas

Problema: Um estudante quer ir da escola para casa usando transporte público. Ele pode pegar um dos 3 ônibus disponíveis OU uma das 2 linhas de metrô que fazem o trajeto. De quantas formas ele pode fazer o trajeto?

Estratégia: Ônibus e metrô são meios alternativos (exclusivos entre si — ele pega um OU outro, não os dois). Aplique o princípio aditivo.

Resolução:

As duas alternativas são mutuamente exclusivas (o estudante usa exatamente um meio de transporte):

$N = 3 + 2 = 5 \text{ formas}$

Atenção: se o problema fosse "pegar um ônibus E depois um metrô" (duas etapas em sequência), o total seria $3 \times 2 = 6$ . O conector "OU" (alternativa) gera soma; o conector "E" (sequência) gera produto.

Fonte. Book of Proof, 3rd ed., §3.1 — Richard Hammack, licença CC-BY-ND.

Example— 5· Senha com restrições mistas — sem e com restrição na 1.ª posição

Problema: Um sistema exige senhas de 6 caracteres formadas por letras minúsculas (a-z, 26 opções) e dígitos (0-9, 10 opções), com repetição permitida. Quantas senhas são possíveis se: (a) não há restrição adicional; (b) a senha deve começar com uma letra?

Estratégia: Aplique o PFC diretamente em (a). Para (b), fixe a restrição no primeiro caractere antes de multiplicar.

Resolução:

(a) Sem restrição: cada uma das 6 posições aceita qualquer dos $26 + 10 = 36$ caracteres alfanuméricos.

$N_a = 36^6 = 2\,176\,782\,336 \approx 2{,}2 \times 10^9$

(b) Primeira posição deve ser letra: a 1.ª posição tem 26 opções (apenas letras); as outras 5 posições mantêm 36 opções cada.

$N_b = 26 \times 36^5 = 26 \times 60\,466\,176 = 1\,572\,120\,576 \approx 1{,}6 \times 10^9$

Verificação: $N_b / N_a = 26/36 \approx 0{,}72$ — senhas com primeira letra representam 72% do total, consistente com $26/36$ das 36 opções serem letras.

Fonte. OpenStax College Algebra 2e, §11.5 — licença CC-BY 4.0.

Exercise list

40 exercises · 10 with worked solution (25%)

Application 27Understanding 6Modeling 6Challenge 1

Fontes desta aula

OpenStax College Algebra 2e — Jay Abramson et al. · OpenStax · 2022 · EN · CC-BY 4.0 · §11.5 (Counting Principles). Fonte primária.
Book of Proof, 3rd ed. — Richard Hammack · 2018, 3rd ed. · EN · CC-BY-ND · Cap. 3 (Counting), §3.1 (Multiplication Principle), §3.2 (Lists and Functions). Fonte primária.
Wikilivros — Matemática elementar / Combinatória — colaborativo · PT-BR · CC-BY-SA · PFC, fatorial, aplicações brasileiras.