Quantos subconjuntos tem um conjunto com 10 elementos? A resposta — \(1{.}024\) — não precisa de contagem direta: ela emerge da soma da décima linha do Triângulo de Pascal. O coeficiente binomial \(\binom{n}{r}\) não é apenas uma fórmula de contagem isolada; ele satisfaz identidades que se reforçam mutuamente e tornam cálculos complexos surpreendentemente diretos.
Por que coeficientes binomiais? #
As identidades dos coeficientes binomiais reaparecem em áreas centrais da computação e da matemática:
- Probabilidade e estatística: a distribuição binomial — modelo de \(n\) experimentos independentes com probabilidade \(p\) de sucesso — tem \(P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}\). Toda a análise de testes A/B, intervalos de confiança e modelos de classificação Bayesiana passa por essa fórmula.
- Teoria de códigos: o número de palavras binárias de comprimento \(n\) com exatamente \(k\) bits iguais a 1 (peso de Hamming \(k\) — número de bits 1 na palavra) é \(\binom{n}{k}\). O Teorema das Linhas — \(\sum_k \binom{n}{k} = 2^n\) — simplesmente diz que a soma de todas as classes de peso dá o total de palavras binárias.
- Análise de algoritmos: algoritmos de busca exaustiva que avaliam todos os subconjuntos de tamanho \(k\) têm complexidade \(\Theta!\left(\binom{n}{k}\right)\). A simetria \(\binom{n}{k} = \binom{n}{n-k}\) revela que avaliar subconjuntos de tamanho \(k\) custa o mesmo que avaliar seus complementos de tamanho \(n-k\).
- Expansão de polinômios: os coeficientes de \((1 + x)^n\) são exatamente \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\). Em aprendizado de máquina, o número de features polinomiais de grau \(\leq d\) geradas a partir de \(n\) variáveis de entrada (features) é \(\binom{n+d}{d}\) — diretamente ligado à combinação com repetição.
- Recorrências e programação dinâmica: a Relação de Pascal \(\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}\) é a base da memorização do triângulo — o mesmo padrão de subproblemas sobrepostos que torna a programação dinâmica (técnica de armazenar subresultados para reutilizá-los) eficiente.
O mapa das identidades #
O diagrama abaixo mostra como as identidades deste artigo se relacionam: a Relação de Pascal gera o Triângulo, e o Triângulo revela os três teoremas de soma.
flowchart TD
DEF["C(n,r) — definição"] --> SIM["Simetria
C(n,r) = C(n,n-r)"]
DEF --> FRONT["Fronteira
C(n,0) = C(n,n) = 1"]
DEF --> PASCAL["Relação de Pascal
C(n,r) + C(n,r+1) = C(n+1,r+1)"]
PASCAL --> TRI["Triângulo de Pascal"]
TRI --> LINHA["Teorema das Linhas
∑ C(n,k) = 2ⁿ"]
TRI --> COL["Teorema das Colunas
∑ C(k,r) = C(n+1,r+1)"]
TRI --> DIAG["Teorema das Diagonais
∑ C(n+k,k) = C(n+r+1,r)"]
Coeficiente Binomial #
Identidades Fundamentais #
Simetria #
Prova combinatória: escolher \(r\) elementos de \(n\) equivale a excluir os outros \(n-r\). \(\blacksquare\)
Fronteira e Secundária #
Relação de Pascal (Stifel) #
Prova algébrica: partindo da definição e usando o denominador comum \((r+1)!(n-r)!\):
$$\binom{n}{r} + \binom{n}{r+1} = \frac{n!}{r!(n-r)!} + \frac{n!}{(r+1)!(n-r-1)!}$$$$= \frac{n!\,(r+1)}{(r+1)!(n-r)!} + \frac{n!\,(n-r)}{(r+1)!(n-r)!} = \frac{n!\,[(r+1)+(n-r)]}{(r+1)!(n-r)!}$$$$= \frac{n!\,(n+1)}{(r+1)!(n-r)!} = \frac{(n+1)!}{(r+1)!(n-r)!} = \binom{n+1}{r+1} \quad \blacksquare$$Prova combinatória: de \(n+1\) objetos, quantas formas escolher \(r+1\)? Fixe o objeto \(x\): ou ele está incluído (escolhem-se \(r\) dos \(n\) restantes: \(\binom{n}{r}\)) ou não está (escolhem-se \(r+1\) dos \(n\) restantes: \(\binom{n}{r+1}\)). \(\blacksquare\)
A figura abaixo ilustra a relação com o exemplo concreto \(C(4,2) = C(3,1) + C(3,2) = 3 + 3 = 6\):
Triângulo de Pascal #
A Relação de Pascal permite construir o triângulo iterativamente: cada elemento é a soma dos dois acima dele na linha anterior, com 1 nas extremidades de cada linha. Cada posição do triângulo corresponde a um coeficiente binomial: a posição da linha \(n\) e coluna \(r\) contém exatamente \(C(n, r)\).
Substituindo cada \(C(n,r)\) pelo seu valor numérico, obtemos o triângulo que costuma aparecer nos livros:
Na linha \(n\), a coluna \(r\) contém \(\binom{n}{r}\).
Teorema das Linhas #
Prova: No Binômio de Newton \((a+b)^n\) (tema do próximo artigo), substitua \(a = b = 1\): \(2^n = \sum_{k=0}^n \binom{n}{k}\). \(\blacksquare\)
Interpretação: o número total de subconjuntos de um conjunto com \(n\) elementos é \(2^n\) — e a soma dos coeficientes de uma linha do triângulo comprova isso diretamente. Para \(n = 10\), isso dá \(2^{10} = 1{.}024\) — a resposta à pergunta da abertura.
A figura abaixo destaca a linha \(n = 5\) no triângulo, mostrando que \(1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5\):
Teorema das Colunas #
Somar a \(r\)-ésima coluna do triângulo até a linha \(n\) resulta em \(\binom{n+1}{r+1}\) — o elemento imediatamente abaixo e à direita do último somado. A figura abaixo mostra o triângulo em grade e destaca a coluna \(r = 2\): os valores \(1, 3, 6, 10, 15\) somam \(35 = C(7,3)\).
Teorema das Diagonais #
Somam-se elementos ao longo de uma diagonal ascendente do triângulo e o resultado está na diagonal seguinte. A figura abaixo mostra a diagonal \(n = 2\): os valores \(C(2,0), C(3,1), C(4,2), C(5,3)\) estão conectados em vermelho e sua soma aponta para \(C(6,3) = 20\) em âmbar.
Exemplos Resolvidos #
Simetria e complexidade de busca exaustiva #
Enunciado: Um algoritmo avalia todos os subconjuntos de tamanho \(k = 3\) e todos os de tamanho \(k = 17\) de um conjunto com \(n = 20\) elementos. Quantos subconjuntos são avaliados em cada caso? O que a simetria implica?
Solução:
$$\binom{20}{3} = \frac{20 \times 19 \times 18}{3!} = \frac{6{.}840}{6} = \mathbf{1{.}140}$$$$\binom{20}{17} = \binom{20}{20-17} = \binom{20}{3} = \mathbf{1{.}140}$$A simetria \(\binom{n}{r} = \binom{n}{n-r}\) tem consequência prática direta: avaliar subconjuntos de tamanho \(r\) custa exatamente o mesmo que avaliar seus complementos de tamanho \(n - r\). A contagem é máxima para \(r\) próximo de \(n/2\) e mínima para \(r\) próximo de \(0\) ou \(n\) — por isso algoritmos de busca por subconjuntos pequenos ou grandes são mais eficientes do que buscas por subconjuntos de tamanho médio.
Soma de produto de inteiros consecutivos #
Enunciado: Calcular \(S = 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + \cdots + 50 \cdot 51 \cdot 52\).
Solução: Observe que \(k(k+1)(k+2) = 6\binom{k+2}{3}\), pois \(\binom{k+2}{3} = \frac{(k+2)(k+1)k}{6}\). Logo:
$$S = 6\sum_{k=1}^{50}\binom{k+2}{3} = 6\left[\binom{3}{3} + \binom{4}{3} + \cdots + \binom{52}{3}\right]$$Pelo Teorema das Colunas com \(r = 3\), somando de \(k=3\) a \(52\):
$$\binom{3}{3} + \cdots + \binom{52}{3} = \binom{53}{4} = \frac{53 \times 52 \times 51 \times 50}{24} = 292{.}825$$$$S = 6 \times 292{.}825 = \mathbf{1{.}756{.}950}$$
Python: gerando o triângulo com programação dinâmica
Programação dinâmica é uma técnica que resolve um problema complexo dividindo-o em subproblemas menores e armazenando os resultados intermediários para reutilizá-los — em vez de recalculá-los do zero a cada passo. O triângulo de Pascal é um exemplo clássico: \(C(n,r)\) depende de \(C(n-1,r-1)\) e \(C(n-1,r)\), que já foram calculados na linha anterior. A Relação de Pascal \(\binom{i}{j} = \binom{i-1}{j-1} + \binom{i-1}{j}\) se traduz diretamente em código: cada célula é a soma das duas acima. Isso evita o cálculo de fatoriais e o risco de overflow para \(n\) grande.
def pascal(n):
tri = [[1] * (i + 1) for i in range(n + 1)]
for i in range(2, n + 1):
for j in range(1, i):
tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j]
return tri
for linha in pascal(7):
print(linha)[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]A inicialização [1] * (i + 1) preenche as bordas com 1; o laço interno sobrescreve
apenas os elementos interiores de cada linha. Complexidade: \(O(n^2)\) em tempo e
espaço — o mesmo custo de preencher a tabela manualmente.
SQL: calculando \(C(n,r)\) com WITH RECURSIVE
WITH RECURSIVE
Uma expressão de tabela comum (CTE, do inglês Common Table Expression) recursiva constrói a tabela de fatoriais até \(15!\); em seguida, três junções calculam \(C(n,r) = \frac{n!}{r!,(n-r)!}\) para todo \(0 \leq r \leq n \leq 8\).
WITH RECURSIVE fat(n, f) AS (
SELECT 0, 1
UNION ALL
SELECT n + 1, f * (n + 1) FROM fat WHERE n < 15
)
SELECT
a.n AS n,
b.n AS r,
a.f / (b.f * c.f) AS "C(n,r)"
FROM fat a -- a.n = linha, a.f = n!
JOIN fat b ON b.n <= a.n -- b.n = coluna r, b.f = r!
JOIN fat c ON c.n = a.n - b.n -- c.f = (n-r)!
WHERE a.n <= 8
ORDER BY a.n, b.n;O resultado é uma tabela com uma linha por par \((n, r)\), equivalente ao triângulo lido linha a linha. Compatível com SQLite, PostgreSQL e DuckDB.
Tabela-Resumo #
Os três teoremas de soma partilham a mesma estrutura: em cada um, um parâmetro permanece fixo enquanto o outro varia ao longo de uma linha, coluna ou diagonal do triângulo. O painel abaixo destaca esse padrão com o parâmetro fixo em vermelho:
| Identidade / Teorema | Fórmula |
|---|---|
| Simetria | \(\binom{n}{r} = \binom{n}{n-r}\) |
| Fronteira | \(\binom{n}{0} = \binom{n}{n} = 1\) |
| Secundária | \(\binom{n}{1} = \binom{n}{n-1} = n\) |
| Relação de Pascal (Stifel) | \(\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}\) |
| Teorema das Linhas | \(\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n\) |
| Teorema das Colunas | \(\displaystyle\sum_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1}\) |
| Teorema das Diagonais | \(\displaystyle\sum_{k=0}^{r} \binom{n+k}{k} = \binom{n+r+1}{r}\) |
Exercícios #
Os exercícios a seguir aplicam as identidades do artigo: provas combinatórias, leitura do triângulo e uso do Teorema das Linhas e das Colunas. Estão ordenados do mais simples ao mais complexo.
Exercício 1 — Identidade generalizada de Pascal
Prove, usando argumento combinatório, que:
$$\binom{n+2}{p+2} = \binom{n}{p} + 2\binom{n}{p+1} + \binom{n}{p+2}$$Prova: Considere o conjunto \(\{a_1,\ldots,a_n, x, y\}\) com \(n+2\) elementos. Contamos subconjuntos de tamanho \(p+2\) por casos:
- Nem \(x\) nem \(y\): \(\binom{n}{p+2}\)
- Exatamente \(x\) ou exatamente \(y\) (2 casos): \(2\binom{n}{p+1}\)
- Ambos \(x\) e \(y\): \(\binom{n}{p}\)
Somando: \(\binom{n+2}{p+2} = \binom{n}{p} + 2\binom{n}{p+1} + \binom{n}{p+2}\) \(\blacksquare\)
Exercício 2 — Oitava linha do triângulo
Construa a linha \(n=8\) do triângulo a partir da linha \(n=7\): \(1\ 7\ 21\ 35\ 35\ 21\ 7\ 1\).
Somando pares adjacentes e mantendo 1 nas extremidades:
$$1\quad 8\quad 28\quad 56\quad 70\quad 56\quad 28\quad 8\quad 1$$
Exercício 3 — Número de elementos a partir de subconjuntos
Se um conjunto \(A\) possui 512 subconjuntos, qual é \(|A|\)?
Pelo Teorema das Linhas, um conjunto com \(n\) elementos tem exatamente \(2^n\) subconjuntos. Basta resolver:
\(2^n = 512 = 2^9 \Rightarrow n = \mathbf{9}\)
Exercício 4 — Coquetéis de 2 ou mais ingredientes
Quantos coquetéis (misturas de ≥ 2 ingredientes) podem ser feitos com 7 ingredientes distintos?
Subconjuntos de tamanho ≥ 2: \(2^7 - \binom{7}{0} - \binom{7}{1} = 128 - 1 - 7 = \mathbf{120}\)
Exercício 5 — Prova pelo Teorema das Colunas
Prove que \(\displaystyle\sum_{k=1}^n k = \dfrac{n(n+1)}{2}\).
Escreva \(k = \binom{k}{1}\):
$$\sum_{k=1}^n \binom{k}{1} = \binom{n+1}{2} = \frac{(n+1)n}{2} = \frac{n(n+1)}{2} \quad \blacksquare$$Próximos passos #
As identidades deste artigo revelam a estrutura interna de \(\binom{n}{r}\), mas não explicam por que esse coeficiente aparece nos produtos de potências. Quando expandimos \((a+b)^n\), os coeficientes que surgem em cada termo \(a^k b^{n-k}\) são exatamente \(\binom{n}{k}\) — e o Teorema das Linhas nada mais é do que o caso \(a = b = 1\) dessa expansão. Esse é o Binômio de Newton, tema do próximo artigo da série.
