Combinatória

Combinatória é a arte de contar sem enumerar. Em computação ela responde às perguntas que decidem viabilidade: quantas configurações existem, qual o tamanho do espaço de busca, qual a probabilidade de colisão numa tabela hash.

Os dois princípios

Princípio aditivo. Se uma escolha pode ser feita de $m$ formas ou de $n$ formas, e as opções são disjuntas, há $m + n$ possibilidades.

Princípio multiplicativo. Se uma tarefa se decompõe em etapas independentes com $m$ e $n$ opções, há $m \cdot n$ resultados.

Praticamente toda contagem se reduz a combinar esses dois. A dificuldade quase nunca está na aritmética; está em decidir se as escolhas são disjuntas (soma) ou sequenciais (produto), e em não contar a mesma coisa duas vezes.

Permutações, arranjos e combinações

Conceito	Fórmula	Pergunta que responde
Permutação de $n$	$n!$	De quantas formas ordenar $n$ objetos?
Arranjo $A(n,k)$	$\dfrac{n!}{(n-k)!}$	Escolher $k$ de $n$, com ordem
Combinação $\binom{n}{k}$	$\dfrac{n!}{k!(n-k)!}$	Escolher $k$ de $n$, sem ordem

A relação entre arranjo e combinação é a chave: cada combinação de $k$ elementos pode ser ordenada de $k!$ formas, logo $A(n,k) = \binom{n}{k} \cdot k!$.

A pergunta que resolve quase todo exercício é simples: a ordem importa? Uma senha de 4 dígitos distintos é arranjo; uma mão de 5 cartas é combinação.

Propriedades do coeficiente binomial

$$\binom{n}{k} = \binom{n}{n-k} \qquad \text{(escolher }k\text{ é o mesmo que descartar }n-k\text{)}$$

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \qquad \text{(relação de Pascal)}$$

$$\sum_{k=0}^{n} \binom{n}{k} = 2^n \qquad \text{(total de subconjuntos)}$$

A relação de Pascal tem interpretação direta: fixe um elemento; ou ele está no subconjunto (e faltam $k-1$ entre os $n-1$ restantes) ou não está (e faltam $k$ entre $n-1$). É também a recorrência que gera o triângulo de Pascal e a base da implementação por programação dinâmica.

def binomial(n, k):
    # calcula sem passar por n! — evita estouro e é mais rápido
    if k > n - k:
        k = n - k
    r = 1
    for i in range(k):
        r = r * (n - i) // (i + 1)
    return r

Calcular $\binom{n}{k}$ como $n!/(k!(n-k)!)$ é um erro prático: $n!$ estoura muito antes do resultado. A forma iterativa acima mantém os valores intermediários pequenos e a divisão sempre exata.

Binômio de Newton

$$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$$

O coeficiente de $x^{n-k}y^k$ conta de quantas formas escolher $k$ fatores que contribuem com $y$. Fazendo $x = y = 1$ recupera-se $\sum_k \binom{n}{k} = 2^n$.

Combinações com repetição

Para escolher $k$ elementos de $n$ tipos, com repetição permitida e sem ordem:

$$\left(!!\binom{n}{k}!!\right) = \binom{n + k - 1}{k}$$

A demonstração é o argumento de estrelas e barras: represente a escolha por $k$ estrelas separadas por $n-1$ barras; cada arranjo dos $n+k-1$ símbolos determina uma escolha.

É a fórmula que conta soluções inteiras não negativas de $x_1 + \cdots + x_n = k$ — que aparece em alocação de recursos e em análise de distribuição de carga.

Princípio de inclusão-exclusão

$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots$$

Corrige a contagem dupla alternando sinais. Aplicação clássica: contar desarranjos — permutações sem ponto fixo:

$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \approx \frac{n!}{e}$$

Ou seja, cerca de $37%$ das permutações não deixam nenhum elemento no lugar — um fato que surpreende e que independe de $n$.

Exemplo trabalhado: o paradoxo do aniversário

Qual a probabilidade de que, entre $k$ pessoas, duas façam aniversário no mesmo dia?

É mais fácil contar o complemento. O número de formas de $k$ pessoas terem datas todas distintas é $A(365, k)$, e o total de configurações é $365^k$:

$$P(\text{todas distintas}) = \frac{365 \cdot 364 \cdots (365-k+1)}{365^k}$$

Para $k = 23$ isso dá aproximadamente $0{,}493$ — logo a probabilidade de colisão passa de $50%$ com apenas 23 pessoas.

Este resultado é o ataque do aniversário em criptografia: para uma função de resumo de $n$ bits, espera-se encontrar colisão após cerca de $2^{n/2}$ tentativas, e não $2^n$. É por isso que resistência a colisão de 128 bits exige um resumo de 256 bits.

Aplicações em computação

Tabelas hash. A análise de colisões é combinatória de bolas em urnas. Com $n$ chaves em $m$ posições, o comprimento máximo esperado de uma lista é $\Theta(\log n / \log\log n)$.

Espaço de busca. Contar configurações decide se busca exaustiva é viável. Um problema com $2^{40}$ estados é tratável; com $2^{80}$, não.

Complexidade de senhas. Uma senha de comprimento $L$ sobre alfabeto de tamanho $A$ tem $A^L$ possibilidades — a base de todo cálculo de entropia.

Aprendizado de máquina. A contagem de hipóteses limita a capacidade de generalização; é o ingrediente combinatório por trás da dimensão VC.

Testes. Cobertura de pares (pairwise testing) usa desenhos combinatórios para cobrir todas as interações de dois parâmetros com poucas execuções.

Erros comuns

• Confundir arranjo com combinação. Pergunte sempre se a ordem importa.
• Contar duas vezes ao aplicar o princípio aditivo a casos não disjuntos — é para isso que existe a inclusão-exclusão.
• Calcular fatoriais grandes desnecessariamente.
• Esquecer que escolhas podem não ser independentes. O princípio multiplicativo exige que o número de opções de cada etapa não dependa das escolhas anteriores.

Leituras recomendadas

• Rosen, capítulos de contagem — muitos exercícios e aplicações diretas em computação.
• Graham, Knuth e Patashnik, capítulo 5 — coeficientes binomiais em profundidade; é a referência definitiva sobre identidades binomiais.
• Knuth, TAOCP volume 4A — geração combinatória: como enumerar permutações, combinações e partições eficientemente.

Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill. ISBN 9781259676512. Ronald L. Graham and Donald E. Knuth and Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. ISBN 9780134389967.

Referências

1. Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill.
2. Ronald L. Graham; Donald E. Knuth; Oren Patashnik (1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley.