Princípios de contagem

Contar direito é o que permite dizer “força bruta não roda” antes de escrever o código. Quatro ferramentas cobrem quase tudo:

Regra do produto:   escolhas independentes ⇒ multiplique
Permutações:        n! = n·(n−1)·…·1
Arranjos:           P(n,k) = n! / (n−k)!
Combinações:        C(n,k) = n! / (k!·(n−k)!)

Use permutação quando a ordem importa (senhas, rotas) e combinação quando não importa (subconjuntos, times).

from math import comb, perm, factorial
from itertools import combinations

comb(5, 2)        # 10
perm(5, 2)        # 20
list(combinations("ABCD", 2))  # [('A','B'), ('A','C'), ...]

# Espaço de busca do caixeiro viajante com 20 cidades
factorial(19) // 2   # ≈ 6·10¹⁶ rotas. Força bruta: fora de questão.

Inclusão-exclusão

|A ∪ B| = |A| + |B| − |A ∩ B|

Somar os dois conjuntos conta a interseção duas vezes; por isso a subtraímos. Com três conjuntos, soma-se de volta a interseção tripla.

Estrelas e barras

O número de formas de distribuir n itens idênticos em k caixas é C(n + k − 1, k − 1). Serve, por exemplo, para contar quantos multiconjuntos (combinações com repetição) existem.