Quantos subconjuntos tem um conjunto com 10 elementos? A resposta, \(1{.}024\), não precisa de contagem direta: ela emerge da soma da linha \(n = 10\) do Triângulo de Pascal. O coeficiente binomial \(\binom{n}{r}\) 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}\). Boa parte da análise de testes A/B, de intervalos de confiança e de 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\), ou seja, o número de bits 1 na palavra) é \(\binom{n}{k}\). O Teorema das Linhas, \(\sum_k \binom{n}{k} = 2^n\), 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}\), ligado diretamente à 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 os \(r\) elementos que entram equivale a escolher os \(n-r\) que ficam de fora, porque cada subconjunto de \(r\) elementos corresponde a exatamente um subconjunto de \(n-r\) elementos, o seu complemento. Portanto, \(\binom{n}{r} = \binom{n}{n-r}\), que é o que queríamos demonstrar. \(\blacksquare\)
Fronteira e Secundária #
Relação de Pascal (Stifel) #
No Brasil, a relação costuma levar também o nome de Michael Stifel, que publicou parte do triângulo em 1544, na Arithmetica integra.
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}$$Portanto, \(\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}\), que é o que queríamos demonstrar. \(\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}\)). Os dois casos não se sobrepõem e cobrem todas as escolhas, então se somam. Portanto, \(\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}\), que é o que queríamos demonstrar. \(\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 #
O triângulo é muito mais antigo que Pascal e foi descoberto várias vezes, de forma independente:
- Índia: o Chandaḥśāstra de Pingala (séc. III ou II a.C.) já contava as combinações de sílabas longas e curtas dos versos; por volta do ano 975, Halayudha, comentando Pingala, descreveu o triângulo explicitamente, com o nome de Meru-prastāra.
- Pérsia: al-Karaji (953-1029) descreveu o triângulo num livro hoje perdido, e Omar Khayyam (1048-1131) o usou para extrair raízes. No Irã, ele é o triângulo de Khayyam.
- China: Jia Xian (1010-1070) já o conhecia, e Yang Hui (1238-1298) o apresentou no século XIII. Lá, ele é o triângulo de Yang Hui.
- Europa: Petrus Apianus publicou o triângulo completo em 1527, Stifel parte dele em 1544 e Tartaglia seis linhas em 1556. Na Itália, ele é o triângulo de Tartaglia.
Blaise Pascal reuniu as propriedades conhecidas e as usou em problemas de probabilidade no Traité du triangle arithmétique, publicado depois de sua morte, em 1665, o mesmo tratado que costuma ser apontado como a primeira formulação explícita da indução matemática. O nome “triângulo de Pascal” veio depois, com Montmort (1708) e de Moivre (1730). Mais em Pascal’s triangle.
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)\). A figura abaixo mostra o triângulo escrito nessa notação:
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\). Portanto, \(\sum_{k=0}^n \binom{n}{k} = 2^n\), que é o que queríamos demonstrar. \(\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}\)
Os três casos não se sobrepõem e cobrem todos os subconjuntos de tamanho \(p+2\). Portanto, \(\binom{n+2}{p+2} = \binom{n}{p} + 2\binom{n}{p+1} + \binom{n}{p+2}\), que é o que queríamos demonstrar. \(\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\).
Solução
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|\)?
Solução
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?
Solução
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}\).
Demonstração
Escreva \(k = \binom{k}{1}\):
$$\sum_{k=1}^n \binom{k}{1} = \binom{n+1}{2} = \frac{(n+1)n}{2}$$Portanto, \(\displaystyle\sum_{k=1}^n k = \dfrac{n(n+1)}{2}\), que é o que queríamos demonstrar. \(\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.
