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 é 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 um conjunto reduzido 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\), um 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, isto é, 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 #
Também chamado de regra do produto (em inglês, rule of product). 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, isto é, 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, e 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, pois 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, sem 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\) (distintos pela posição em \(S\), não pelo valor), 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 usuários humanos escolhem senhas longe de aleatórias, o que reduz o espaço efetivo: por isso o NIST SP 800-63B orienta comparar as senhas escolhidas com listas de valores comuns, esperados ou vazados. 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, pois 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, pois 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}$$São mais de 95 trilhões de gabaritos possíveis. Mesmo tentando um por segundo, seriam necessários cerca de 3 milhões de anos 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 do NIST indicam que a maioria dos defeitos é causada pela interação de um ou dois parâmetros, com uma fração menor exigindo três ou mais. O pairwise testing (ou cobertura de pares; em inglês, também all-pairs testing) 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. Os chamados arranjos de cobertura (covering arrays) 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, pois 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, com a 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 de 1 a 9 (zero excluído) |
| Dezenas | 9 | dígitos de 0 a 9 exceto o das centenas (zero volta a ser opção) |
| Unidades | 8 | dígitos de 0 a 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, pelo 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, pelo 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, pois 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 rápida: são só \(k\) multiplicações, uma por fator primo, ou seja, \(O(k)\), 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), um algoritmo de criptografia assimétrica clássico, usado em assinaturas digitais e na autenticação de certificados do HTTPS (a troca de chaves por RSA existia nas versões antigas do TLS, mas foi removida no TLS 1.3).
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 (de 1 a 9); 2º: 9 opções (de 0 a 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 = 9{.}000\)
- Com todos distintos: \(9 \times 9 \times 8 \times 7 = 4{.}536\)
- Com pelo menos dois iguais: \(9{.}000 - 4{.}536 = \mathbf{4{.}464}\)
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 a 9 (6 dígitos): \(6 \times 9 \times 8 = 432\)
- Começa com 3: para passar de 390, a 2ª posição tem de ser 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). Logo, \(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.
