Contar parece simples — até que a quantidade de casos explode. Quantas senhas de 8 caracteres existem? Quantos gabaritos possíveis tem uma prova de 20 questões de múltipla escolha? Enumerar um por um é impraticável. Precisamos de princípios.
Dois deles sustentam toda a combinatória: o Princípio Aditivo (PA) e o Princípio Multiplicativo (PM).
Por que PA e PM? #
Contar não é uma curiosidade matemática abstrata — é uma operação central em computação e engenharia:
- Segurança e criptografia: o tamanho do espaço de senhas ou chaves determina a resistência a ataques de força bruta. Quantificar esse espaço é sempre uma aplicação do PM.
- Testes de software: técnicas como pairwise testing usam PA e PM para escolher o menor conjunto de casos que cobre todas as combinações de pares de parâmetros.
- Estruturas de dados: o número de índices de um array multidimensional \(A[n_1][n_2]\cdots[n_k]\) é \(n_1 \cdot n_2 \cdots n_k\) — produto cartesiano direto.
- Protocolos de rede: os espaços de endereços IPv4 (\(2^{32}\)) e IPv6 (\(2^{128}\)) vêm do PM aplicado a sequências de bits.
- Análise de algoritmos: a estimativa de complexidade de algoritmos exaustivos, a probabilidade de colisões em tabelas hash e o dimensionamento de espaços de busca em IA (Inteligência Artificial) — tudo passa por contar com PA e PM.
Este artigo desenvolve os dois princípios formalmente, aplica-os em exemplos graduais e mostra como reconhecer qual usar em cada situação.
A Intuição: “ou” é soma, “e” é produto #
Considere uma loja com 4 livros de matemática e 3 de português.
- Quantas formas de escolher um livro (de matemática ou de português)? \(4 + 3 = 7\)
- Quantas formas de escolher um de cada (um de matemática e um de português)? \(4 \times 3 = 12\)
Essa intuição é o núcleo dos dois princípios. O diagrama abaixo transforma essa intuição em um guia de decisão que pode ser aplicado a qualquer problema de contagem:
flowchart TD
A["Como contar?"] --> B{"Alternativas
excludentes?"}
B -->|"Sim — 'ou'"| C["Princípio Aditivo
|A₁| + |A₂| + …"]
B -->|"Não — 'e'"| D{"Etapas
independentes?"}
D -->|Sim| E["Princípio Multiplicativo
|A₁| × |A₂| × …"]
D -->|Não| F["Complemento
ou PIE"]
C --> G["⚠️ Conjuntos não
disjuntos? → PIE"]
Princípio Aditivo #
Se \(A \cap B = \emptyset\), então \(|A \cup B| = |A| + |B|\).
Extensão: para conjuntos \(A_1, A_2, \ldots, A_n\) dois a dois disjuntos:
$$|A_1 \cup \cdots \cup A_n| = |A_1| + \cdots + |A_n|$$Aplicação: quando as escolhas são mutuamente exclusivas — não podem ocorrer simultaneamente.
O PA exige conjuntos dois a dois disjuntos. Se houver elementos em comum, somá-los ingenuamente conta esses elementos mais de uma vez. A correção é o Princípio da Inclusão-Exclusão (PIE):
$$|A \cup B| = |A| + |B| - |A \cap B|$$Exemplo: numa turma, 18 alunos praticam futebol e 12 praticam vôlei; 5 praticam os dois esportes. O total de praticantes é \(18 + 12 - 5 = 25\), não \(18 + 12 = 30\). O PIE é tratado em detalhe no artigo sobre cardinalidade.
Produto Cartesiano e Princípio Multiplicativo #
Se uma tarefa é realizada em etapas independentes, com \(|A_1|\) formas para a 1ª etapa, \(|A_2|\) para a 2ª, …, \(|A_k|\) para a \(k\)-ésima, então o total de maneiras de realizar a tarefa é:
$$|A_1 \times A_2 \times \cdots \times A_k| = |A_1| \cdot |A_2| \cdots |A_k|$$Aplicação: quando as escolhas são sequenciais e independentes — cada etapa não interfere nas demais.
Exemplos Resolvidos #
Os exemplos a seguir aumentam progressivamente em complexidade. Em cada um, identificamos o princípio aplicável antes de calcular — esse hábito evita erros e torna o raciocínio verificável.
Senhas com e sem repetição #
Enunciado: uma fechadura tem 8 símbolos disponíveis. Quantas senhas de 2 símbolos existem: (a) com repetição de símbolo permitida; (b) com os dois símbolos necessariamente distintos?
Princípio: PM em ambos os casos — a senha é formada em duas etapas sequenciais (escolher o 1º símbolo, depois o 2º), e em cada etapa o número de opções é constante independente do símbolo escolhido antes.
(a) Com repetição: cada posição tem 8 opções; não há restrição entre elas:
$$8 \times 8 = 64 \text{ senhas}$$(b) Sem repetição: a 1ª posição ainda tem 8 opções, mas a 2ª tem apenas 7 — qualquer símbolo exceto o já escolhido:
$$8 \times 7 = 56 \text{ senhas}$$Verificação por complemento: das 64 senhas com repetição, removemos as 8 onde ambas as posições têm o mesmo símbolo (AA, BB, …): \(64 - 8 = 56\). ✓
Python: itertools.product e itertools.permutations
itertools.product e itertools.permutations
O módulo itertools da biblioteca padrão implementa o produto cartesiano
diretamente, tornando o PM observável em código. O exemplo abaixo usa o caso
das senhas de 2 símbolos num alfabeto de 8 caracteres:
import itertools
simbolos = "ABCDEFGH" # 8 símbolos
# PM com repetição: produto cartesiano 8 × 8 = 64 pares
com_rep = list(itertools.product(simbolos, repeat=2))
print(len(com_rep)) # 64
# PM sem repetição: cada posição exclui o símbolo já usado → 8 × 7 = 56
sem_rep = list(itertools.permutations(simbolos, 2))
print(len(sem_rep)) # 56itertools.product(A, B, C, ...) gera \(|A| \times |B| \times |C| \times \cdots\)
tuplas — exatamente o PM. itertools.permutations(S, k) gera arranjos de
\(k\) elementos distintos de \(S\), correspondendo ao PM aplicado a
etapas sem repetição. O nome da função antecipa um conceito formal: uma
permutação é uma seleção ordenada de elementos distintos. O
próximo artigo trata esse
tema em detalhe.
Aplicação: força bruta e espaço de senhas
Um atacante que testa todas as senhas de 8 caracteres de um alfabeto de 95 símbolos imprimíveis enfrenta \(95^8 \approx 6{,}6 \times 10^{15}\) combinações — mais de 6 quadrilhões de tentativas. Proibir repetições reduziria esse espaço para \(95 \times 94 \times \cdots \times 88\), mas a prática mostra que usuários humanos escolhem senhas longe de aleatórias, reduzindo drasticamente o espaço efetivo. O PM é a ferramenta que formaliza esse raciocínio em políticas de senhas e em estimativas de custo de ataque.
Bandeira de 3 faixas com cores diferentes #
Enunciado: uma bandeira tem 3 faixas horizontais; há 5 cores disponíveis e cada faixa deve ter uma cor diferente das demais. Quantas bandeiras distintas podem ser criadas?
Princípio: PM — a montagem é feita em 3 etapas sequenciais (faixa superior, média, inferior), e em cada etapa o número de cores disponíveis diminui de forma previsível.
| Etapa | Faixa | Opções disponíveis |
|---|---|---|
| 1ª | Superior | 5 (qualquer das 5 cores) |
| 2ª | Média | 4 (qualquer exceto a usada na faixa superior) |
| 3ª | Inferior | 3 (qualquer exceto as duas já usadas) |
A contagem de opções na 2ª etapa é sempre 4, independente de qual cor foi escolhida na 1ª — essa constância é exatamente o que valida o uso do PM.
Prova de múltipla escolha #
Enunciado: uma prova tem 20 questões. Quantos gabaritos distintos são possíveis se cada questão é de verdadeiro ou falso? E se cada questão tem 5 alternativas?
Princípio: PM — cada questão é uma etapa independente das demais. A resposta dada a qualquer questão não altera as opções das outras.
Verdadeiro ou falso: cada uma das 20 questões tem 2 opções (V ou F):
$$\underbrace{2 \times 2 \times \cdots \times 2}_{20\text{ vezes}} = 2^{20} = 1.048.576 \text{ gabaritos}$$5 alternativas por questão: a estrutura é idêntica, apenas cada etapa passa a ter 5 opções:
$$5^{20} \approx 9{,}5 \times 10^{13} \text{ gabaritos}$$Mais de 95 trilhões de gabaritos possíveis — mesmo tentando um por segundo, seria necessário mais tempo do que a idade do universo para esgotá-los.
Aplicação: geração de casos de teste
Imagine um sistema com \(k\) parâmetros de configuração, cada um podendo assumir \(n\) valores. Testar todas as combinações possíveis — a estratégia chamada de cobertura exaustiva ou full factorial — exige \(n^k\) casos de teste, exatamente pelo PM. Para \(k = 10\) parâmetros com \(n = 5\) valores cada, isso já são \(5^{10} \approx 10\) milhões de testes.
Na prática, pesquisas empíricas mostram que a maioria dos defeitos é causada pela interação de no máximo dois parâmetros simultaneamente. O pairwise testing (ou cobertura de pares) aproveita isso: em vez de cobrir todas as \(n^k\) combinações, escolhe-se um subconjunto menor de testes tal que, para cada par de parâmetros, todas as \(n^2\) combinações de valores desse par apareçam ao menos uma vez. Algoritmos de geração de arrays ortogonais conseguem isso com apenas \(O(n^2 \log k)\) casos — uma redução brutal em relação ao full factorial.
Números de 3 algarismos distintos de \(\{1,2,3,4,5,6\}\) #
Enunciado: quantos números de 3 algarismos distintos podem ser formados usando apenas dígitos de \(\{1,2,3,4,5,6\}\)?
Princípio: PM — preenchemos as 3 posições sequencialmente; em cada posição o número de opções diminui em 1 porque o algarismo escolhido não se repete.
| Posição | Opções | Justificativa |
|---|---|---|
| Centenas | 6 | qualquer dos 6 dígitos |
| Dezenas | 5 | qualquer exceto o das centenas |
| Unidades | 4 | qualquer exceto os dois já usados |
Como 0 não pertence ao conjunto, todos os números formados já são automaticamente válidos como números de 3 algarismos — não há risco de zero à esquerda.
Números de 3 algarismos distintos de \(\{0,1,\ldots,9\}\) #
Enunciado: quantos números de 3 algarismos (entre 100 e 999) têm todos os algarismos distintos, usando dígitos de \(\{0,1,\ldots,9\}\)?
Princípio: PM — mesma estrutura do exemplo anterior, mas agora 0 está disponível e não pode ocupar a posição das centenas (caso contrário, o número teria menos de 3 algarismos).
| Posição | Opções | Justificativa |
|---|---|---|
| Centenas | 9 | dígitos 1–9 (zero excluído) |
| Dezenas | 9 | dígitos 0–9 exceto o das centenas (zero volta a ser opção) |
| Unidades | 8 | dígitos 0–9 exceto os dois já usados |
Verificação por complemento: contamos todos os arranjos de 3 dígitos distintos (inclusive os que começam com zero) e subtraímos os inválidos:
$$\underbrace{10 \times 9 \times 8}_{\text{todos os arranjos com dígitos distintos}} - \underbrace{1 \times 9 \times 8}_{\text{começam com 0}} = 720 - 72 = 648 \checkmark$$O método do complemento segue sempre a mesma estrutura — útil quando contar os casos inválidos é mais simples do que contar os válidos diretamente:
flowchart LR
A["**Total**
sem restrição"] -->|"− Casos inválidos
(mais fáceis de contar)"| B["**Resultado**
apenas os casos válidos"]
Seleção em uma sala #
Enunciado: numa sala há 5 homens, 6 mulheres e 4 crianças. De quantas formas podemos escolher: (a) uma única pessoa; (b) uma pessoa de cada tipo?
Este exemplo é instrutivo porque os dois sub-problemas, com enunciados parecidos, exigem princípios distintos.
(a) Uma única pessoa — Princípio Aditivo:
Escolher “ou um homem, ou uma mulher, ou uma criança” — as três categorias são mutuamente exclusivas (ninguém pertence a dois grupos simultaneamente). Pelo PA:
$$5 + 6 + 4 = 15 \text{ formas}$$(b) Uma de cada tipo — Princípio Multiplicativo:
Agora queremos “um homem e uma mulher e uma criança” — três escolhas independentes em grupos distintos. Quem escolhemos no grupo dos homens não interfere em quem podemos escolher entre as mulheres. Pelo PM:
$$5 \times 6 \times 4 = 120 \text{ formas}$$
SQL: UNION ALL (PA) vs CROSS JOIN (PM)
UNION ALL (PA) vs CROSS JOIN (PM)
A distinção “ou é soma, e é produto” tem um reflexo direto em SQL. Usamos tabelas mínimas para tornar o resultado visível:
CREATE TABLE homens (nome TEXT);
CREATE TABLE mulheres (nome TEXT);
CREATE TABLE criancas (nome TEXT);
INSERT INTO homens VALUES ('Bruno'), ('Carlos');
INSERT INTO mulheres VALUES ('Ana'), ('Diana');
INSERT INTO criancas VALUES ('Edu'), ('Fabi');PA — uma única pessoa (UNION ALL):
SELECT nome FROM homens
UNION ALL
SELECT nome FROM mulheres
UNION ALL
SELECT nome FROM criancas;nome
------
Bruno
Carlos
Ana
Diana
Edu
Fabi
(6 linhas: 2 + 2 + 2)PM — um de cada tipo (CROSS JOIN):
SELECT h.nome AS homem,
m.nome AS mulher,
c.nome AS crianca
FROM homens h
CROSS JOIN mulheres m
CROSS JOIN criancas c;homem | mulher | crianca
-------|--------|--------
Bruno | Ana | Edu
Bruno | Ana | Fabi
Bruno | Diana | Edu
Bruno | Diana | Fabi
Carlos | Ana | Edu
Carlos | Ana | Fabi
Carlos | Diana | Edu
Carlos | Diana | Fabi
(8 linhas: 2 × 2 × 2)UNION ALL empilha as linhas de tabelas disjuntas, somando as cardinalidades.
CROSS JOIN gera todas as combinações possíveis (pares, triplas, e assim por
diante), multiplicando as cardinalidades. Essa
correspondência aparece sempre que um esquema relacional precisa enumerar
combinações entre entidades independentes.
Divisores de \(N = 2^3 \times 3^2 \times 5^4\) #
Enunciado: quantos divisores positivos tem \(N = 2^3 \times 3^2 \times 5^4\)?
Observação chave: pelo Teorema Fundamental da Aritmética, todo divisor de \(N\) tem necessariamente a forma \(2^\alpha \cdot 3^\beta \cdot 5^\gamma\), onde os expoentes obedecem:
$$\alpha \in \{0,1,2,3\}, \quad \beta \in \{0,1,2\}, \quad \gamma \in \{0,1,2,3,4\}$$Princípio: PM — escolher \(\alpha\), \(\beta\) e \(\gamma\) são três etapas independentes entre si. Qualquer combinação dentro das faixas acima produz um divisor válido e distinto de todos os outros.
| Etapa | Escolha | Opções |
|---|---|---|
| 1ª | \(\alpha\) (expoente do 2) | 4 valores: 0, 1, 2, 3 |
| 2ª | \(\beta\) (expoente do 3) | 3 valores: 0, 1, 2 |
| 3ª | \(\gamma\) (expoente do 5) | 5 valores: 0, 1, 2, 3, 4 |
Generalização: se \(N = p_1^{a_1} \cdots p_k^{a_k}\) é a fatoração de \(N\) em primos, o número de divisores positivos é:
$$(a_1+1)(a_2+1)\cdots(a_k+1)$$O fator \((a_i + 1)\) conta os valores possíveis para o expoente de \(p_i\): de \(0\) até \(a_i\), são \(a_i + 1\) inteiros. O zero é incluído porque um divisor pode não conter aquele primo — por exemplo, 9 é divisor de \(N\) e corresponde a \(\alpha = 0, \beta = 2, \gamma = 0\).
Python: verificando a fórmula contra força bruta
Para \(N\) pequeno é possível confirmar o resultado enumerando todos os divisores diretamente e comparando com a fórmula:
from math import prod
N = 2**3 * 3**2 * 5**4 # 45 000
# Força bruta: lista todos os d que dividem N
divisores = [d for d in range(1, N + 1) if N % d == 0]
print(len(divisores)) # 60
# Fórmula do PM: produto dos (expoente + 1)
expoentes = [3, 2, 4] # expoentes de 2, 3 e 5
print(prod(e + 1 for e in expoentes)) # 60Para \(N\) grande (como em criptografia, onde os primos têm centenas de dígitos) a força bruta é inviável, mas a fórmula continua em tempo O(1) (tempo constante: uma única multiplicação de \(k\) termos) — desde que a fatoração seja conhecida. Encontrar essa fatoração para \(N\) grande é, por si só, um problema computacionalmente difícil, e é justamente nessa dificuldade que repousa a segurança do RSA (Rivest–Shamir–Adleman) — o algoritmo de criptografia assimétrica mais usado na internet, que protege conexões HTTPS, assinaturas digitais e troca de chaves.
Tabela-Resumo #
| Princípio | Situação típica | Palavra-chave | Operação |
|---|---|---|---|
| Aditivo | Escolhas excludentes | “ou” | Soma |
| Multiplicativo | Etapas sequenciais | “e” | Produto |
Exercícios #
Exercício 1 — Viagem de ida e volta
Para uma viagem Rio–Belo Horizonte–Rio posso usar trem, ônibus ou avião. De quantas maneiras posso escolher os transportes se não desejo usar o mesmo meio na volta que na ida?
Resposta: Na ida: 3 opções. Na volta: 2 opções (excluindo o da ida). Pelo PM: \(3 \times 2 = \mathbf{6}\) maneiras.
Exercício 2 — Palavras de 4 letras
Quantas palavras de 4 letras diferentes podem ser formadas com um alfabeto de 26 letras?
Resposta: Pelo PM, 4 etapas sequenciais sem repetição de letra: 1ª letra: 26 opções; 2ª: 25 (qualquer exceto a 1ª); 3ª: 24; 4ª: 23. \(26 \times 25 \times 24 \times 23 = \mathbf{358{,}800}\) palavras.
Exercício 3 — Inteiros com algarismos distintos
Quantos inteiros entre 100 e 999 têm algarismos distintos?
Resposta: 1º algarismo: 9 opções (1–9); 2º: 9 opções (0–9, exceto o 1º); 3º: 8 opções. \(9 \times 9 \times 8 = \mathbf{648}\)
Exercício 4 — Pelo menos dois dígitos iguais
Quantos números naturais de 4 dígitos possuem pelo menos dois dígitos iguais?
Resposta (por complemento):
- Total de números de 4 dígitos: \(9 \times 10^3 = 9000\)
- Com todos distintos: \(9 \times 9 \times 8 \times 7 = 4536\)
- Com pelo menos dois iguais: \(9000 - 4536 = \mathbf{4464}\)
Exercício 5 — Números com restrições de dígitos
Quantos números de 3 algarismos distintos, maiores que 390, podem ser formados com \(\{0,1,2,3,4,5,6,7,8,9\}\)?
Resposta: Separando em casos:
- Começa com 4–9 (6 dígitos): \(6 \times 9 \times 8 = 432\)
- Começa com 3: a 2ª posição deve ser ≥ 9, ou seja, = 9 (1 opção); 3ª posição: 7 opções — os dígitos \(\{1,2,4,5,6,7,8\}\) (excluídos 0, pois formaria 390 que não satisfaz a restrição, e 3 e 9, já usados). → \(1 \times 1 \times 7 = 7\)
Total: \(432 + 7 = \mathbf{439}\)
Exercício 6 — Divisores de \(M = a^m \cdot b^n \cdot c^p\)
Quantos divisores tem \(M = a^m \cdot b^n \cdot c^p\) (com \(a, b, c\) primos distintos)?
Resposta: Cada divisor tem forma \(a^\alpha b^\beta c^\gamma\) com \(0 \leq \alpha \leq m\), \(0 \leq \beta \leq n\), \(0 \leq \gamma \leq p\):
$$(m+1)(n+1)(p+1) \text{ divisores}$$Próximos passos #
Os princípios aditivo e multiplicativo são a fundação, mas têm uma limitação: exigem que o número de opções em cada etapa seja independente das escolhas anteriores (ou, quando há dependência, que a contagem de opções restantes permaneça constante). Quando essa condição deixa de ser satisfeita, é necessário refinar a análise.
O próximo passo natural é contar sequências sem repetição onde todos os elementos de um conjunto são usados — o domínio das permutações. Em seguida, veremos como contar agrupamentos onde a ordem não importa (combinações) e como lidar com restrições adicionais que misturam PA e PM de forma mais elaborada.
