Um grupo de 10 amigos vai ao cinema e precisa escolher 3 pessoas para comprar as pipocas. Não há distinção entre quem vai — apenas quem vai, não em que ordem. Isso é uma combinação simples.
Por que combinações simples? #
Selecionar subconjuntos sem considerar a ordem é uma das operações mais frequentes em computação e ciência de dados:
- Análise de dados: o número de pares de variáveis em um conjunto de \(n\) colunas é \(C(n, 2)\) — base de matrizes de correlação e testes de associação em SQL (Structured Query Language) e pandas.
- Testes de software: a técnica de all-pairs testing (teste de todos os pares de parâmetros) usa \(C(\text{parâmetros}, 2)\) combinações para cobrir todas as interações de dois fatores com o menor conjunto de casos de teste.
- Teoria dos grafos: o número máximo de arestas em um grafo simples de \(n\) vértices é \(C(n, 2)\) — cada aresta é uma combinação de dois vértices distintos, sem direção.
- Criptografia: esquemas de threshold (limiar) permitem que qualquer subgrupo de \(r\) entre \(n\) participantes reconstrua uma chave secreta — o número de subgrupos válidos é \(C(n, r)\).
- Estatística e aprendizado de máquina: o coeficiente binomial \(C(n, r)\) aparece na distribuição binomial, no cálculo de intervalos de confiança por bootstrap (reamostragem) e em métricas de diversidade de modelos ensemble.
Do arranjo à combinação #
No artigo sobre arranjos simples, vimos que a escolha de \(r\) elementos distintos entre \(n\) se divide em dois casos conforme a ordem importa ou não. O diagrama abaixo completa aquela árvore de decisão, acrescentando o ramo da combinação:
flowchart TD
A["n elementos distintos"] --> B{"Usar todos?"}
B -->|"Sim"| C["Permutação Simples
P_n = n!"]
B -->|"Não — escolher r ≤ n"| D{"Ordem importa?"}
D -->|"Sim"| E["Arranjo Simples
A(n,r) = n!/(n-r)!"]
D -->|"Não"| F["Combinação Simples
C(n,r) = n!/(r!(n-r)!)"]
Combinação Simples #
O diagrama acima já antecipa a definição formal:
Uma combinação simples de \(n\) elementos distintos tomados \(r\) a \(r\) é uma seleção de \(r\) elementos sem considerar a ordem:
$$C(n, r) = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}$$A fórmula vem diretamente do arranjo: cada combinação gera \(r!\) arranjos, um para cada reordenação dos \(r\) elementos escolhidos. Dividindo o arranjo pela quantidade de reordenações internas obtemos a combinação:
$$A(n,r) = C(n,r) \cdot r! \implies C(n,r) = \frac{A(n,r)}{r!} = \frac{n!}{r!\,(n-r)!}$$Propriedades #
Três identidades fundamentais simplificam muitos cálculos práticos:
Escolher quem entra no grupo é equivalente a escolher quem fica fora — os dois subconjuntos se determinam mutuamente.
$$C(n, 1) = C(n, n-1) = n$$
Quando \(r > n/2\), use a simetria \(C(n, r) = C(n, n-r)\): calcular com \(n - r < r\) reduz o número de fatores no numerador e simplifica o cálculo à mão.
Arranjo vs. Combinação: Como Decidir #
A pergunta-chave sempre é: “A ordem muda o resultado?” A tabela abaixo resume os casos mais comuns:
| Situação | Ordem importa? | Técnica |
|---|---|---|
| Pódio de corrida (1º, 2º, 3º) | Sim | Arranjo |
| Comissão de 3 membros entre 10 | Não | Combinação |
| Senha de 4 dígitos distintos | Sim | Arranjo |
| Mão de 5 cartas no baralho | Não | Combinação |
Exemplos Resolvidos #
Comissão de 3 entre 10 pessoas #
Enunciado: Uma associação precisa escolher 3 membros entre 10 voluntários para formar uma comissão. Quantas comissões distintas podem ser formadas?
Solução: A ordem não importa — uma comissão \(\{A, B, C\}\) é a mesma que \(\{B, A, C\}\). Aplicamos a combinação simples:
$$C(10, 3) = \frac{10!}{3!\,7!} = \frac{10 \times 9 \times 8}{6} = \mathbf{120}$$Voltando ao exemplo da abertura: o grupo de 10 amigos pode escolher as 3 pessoas para as pipocas de 120 maneiras distintas.
SQL: JOIN com filtro de ordem para gerar combinações
JOIN com filtro de ordem para gerar combinações
Em SQL, a diferença entre um arranjo e uma combinação é apenas a
condição de junção. No
artigo sobre arranjos
usamos <> para evitar repetição mas gerar os dois sentidos; aqui usamos
> para impor uma ordem canônica e contar cada subconjunto uma única vez:
CREATE TABLE pessoas (id INT, nome TEXT);
INSERT INTO pessoas VALUES
(1,'Ana'),(2,'Bruno'),(3,'Carlos'),(4,'Diana'),(5,'Eva'),
(6,'Felipe'),(7,'Gabi'),(8,'Hugo'),(9,'Iara'),(10,'João');
-- id_a < id_b < id_c garante que cada trio aparece exatamente uma vez,
-- independente da ordem dos nomes
SELECT a.nome, b.nome, c.nome
FROM pessoas a
JOIN pessoas b ON b.id > a.id
JOIN pessoas c ON c.id > b.id
ORDER BY a.nome, b.nome, c.nome;
SELECT COUNT(*)
FROM pessoas a
JOIN pessoas b ON b.id > a.id
JOIN pessoas c ON c.id > b.id;
-- 120 = C(10, 3)Substituindo > por <> nas condições de junção contaríamos os arranjos
\(A(10, 3) = 720\) — seis vezes mais, pois cada trio apareceria nas
\(3! = 6\) ordens possíveis.
Mão de 5 cartas em um baralho de 52 #
Enunciado: Quantas mãos de 5 cartas distintas podem ser distribuídas de um baralho padrão de 52 cartas?
Solução: A ordem das cartas na mão não importa — uma mão \(\{A\spadesuit, K\heartsuit, Q\diamondsuit, J\clubsuit, 10\spadesuit\}\) é a mesma em qualquer sequência em que as cartas cheguem:
$$C(52, 5) = \frac{52!}{5!\,47!} = 2{.}598{.}960$$
Python: itertools.combinations e math.comb
itertools.combinations e math.comb
Python oferece duas formas de trabalhar com combinações: math.comb(n, r)
para calcular a fórmula, e itertools.combinations(iterable, r) para
gerar cada subconjunto individualmente.
from itertools import combinations
import math
# math.comb calcula C(n, r) diretamente — rápido e sem gerar todos os casos
print(math.comb(52, 5)) # 2598960
# itertools.combinations gera cada mão — útil para filtrar por propriedade
# (ex.: quantas mãos têm pelo menos um ás?)
baralho = range(52) # 52 cartas representadas por 0–51
maos = combinations(baralho, 5)
print(sum(1 for _ in maos)) # 2598960
# Para n e r grandes, NUNCA materialize o iterador em lista —
# use math.comb para o total e combinations() só quando precisar inspecionaritertools.combinations garante que cada elemento aparece no máximo uma vez
por subconjunto e que subconjuntos com os mesmos elementos em ordens
diferentes são tratados como iguais — exatamente a definição de combinação.
Time de futebol: 11 jogadores entre 15 #
Enunciado: Um técnico precisa escalar 11 titulares entre 15 jogadores disponíveis. Quantas escalações distintas (sem considerar posições) existem?
Solução: Como \(r = 11 > 15/2\), a propriedade de simetria simplifica o cálculo — escolher 11 que entram é equivalente a escolher 4 que ficam de fora:
$$C(15, 11) = C(15, 4) = \frac{15 \times 14 \times 13 \times 12}{4!} = \frac{32{.}760}{24} = \mathbf{1{.}365}$$Grupo misto: 3 homens e 2 mulheres entre 6 homens e 5 mulheres #
Enunciado: Uma comissão de 5 pessoas deve ter exatamente 3 homens e 2 mulheres. Há 6 homens e 5 mulheres disponíveis. Quantas comissões distintas podem ser formadas?
Solução: As escolhas dos homens e das mulheres são independentes entre si; portanto, aplicamos o Princípio Multiplicativo entre os dois blocos:
$$C(6, 3) \times C(5, 2) = 20 \times 10 = \mathbf{200}$$Amostra de 3 peças: pelo menos 1 defeituosa #
Enunciado: Em um lote de 20 peças (5 defeituosas, 15 boas), uma amostra aleatória de 3 peças é retirada. Quantas amostras contêm pelo menos 1 peça defeituosa?
Solução: Contar diretamente os casos favoráveis exigiria somar três subcasos (1 defeituosa + 2 boas; 2 defeituosas + 1 boa; 3 defeituosas). A estratégia do complemento é mais eficiente:
$$\text{Pelo menos 1 defeituosa} = \text{Total} - \text{Nenhuma defeituosa}$$$$C(20, 3) - C(15, 3) = 1{.}140 - 455 = \mathbf{685}$$Divisão em grupos iguais #
Enunciado: De quantas maneiras 10 pessoas podem ser divididas em 2 grupos de 5? Considere dois casos: (a) grupos sem rótulo; (b) grupos com rótulo (Grupo A e Grupo B).
Solução:
(a) Grupos indistinguíveis (sem rótulo): escolhemos quem vai para o primeiro grupo — o segundo fica automaticamente determinado. Como os grupos são equivalentes entre si, cada divisão seria contada \(2! = 2\) vezes se não corrigíssemos. Dividimos pelo número de permutações dos \(2\) grupos:
$$\frac{C(10,5)}{2!} = \frac{252}{2} = \mathbf{126}$$(b) Grupos com rótulo (Grupo A e Grupo B): a divisão “5 no Grupo A e 5 no Grupo B” é diferente de “5 no Grupo B e 5 no Grupo A”. Basta escolher quem vai ao Grupo A — o Grupo B é o complemento:
$$C(10,5) = \mathbf{252}$$Tabela-Resumo #
As tabelas abaixo reúnem os três agrupamentos fundamentais e as propriedades específicas da combinação simples estabelecidas neste artigo.
Comparação dos agrupamentos:
| Conceito | Usa todos os \(n\)? | Ordem importa? | Fórmula |
|---|---|---|---|
| Permutação simples | Sim | Sim | \(P_n = n!\) |
| Arranjo simples | Não (\(r \leq n\)) | Sim | \(A(n,r) = \dfrac{n!}{(n-r)!}\) |
| Combinação simples | Não (\(r \leq n\)) | Não | \(C(n,r) = \dfrac{n!}{r!(n-r)!}\) |
Propriedades da combinação simples:
| Propriedade | Fórmula |
|---|---|
| Relação com arranjo | \(A(n, r) = C(n, r) \cdot r!\) |
| Simetria | \(C(n, r) = C(n, n-r)\) |
| Casos extremos | \(C(n, 0) = C(n, n) = 1\) |
| Casos unitários | \(C(n, 1) = C(n, n-1) = n\) |
Exercícios #
Os exercícios a seguir cobrem as principais técnicas do artigo: determinação de \(n\), simetria, complemento e Princípio Multiplicativo. Eles estão ordenados do mais simples ao mais complexo.
Exercício 1 — Determinando \(n\)
Se \(C(n, 2) = 10\), determine \(n\).
Resposta: Expandindo a fórmula:
$$\frac{n(n-1)}{2} = 10 \implies n^2 - n - 20 = 0 \implies (n-5)(n+4) = 0$$Como \(n > 0\), temos \(n = 5\).
Exercício 2 — Comitê com presidência
De 12 pessoas, devem ser escolhidas 3 para um comitê. De quantas maneiras o comitê pode ser formado se um dos membros deve ser o presidente (cargo distinto)?
Resposta: O cargo de presidente é uma posição distinta — importa quem ocupa esse papel. Escolhemos o presidente de forma ordenada (12 opções) e os demais 2 membros sem distinção entre os 11 restantes:
$$12 \times C(11, 2) = 12 \times 55 = \mathbf{660}$$
Exercício 3 — Caminhos em grade
Em uma grade de 4×4 pontos, de quantos modos podemos ir do canto inferior-esquerdo ao canto superior-direito movendo apenas para cima ou para a direita?
Resposta: Qualquer caminho usa exatamente 3 movimentos para cima e 3 para a direita, totalizando 6 movimentos. O caminho fica completamente determinado pela escolha de quais 3 posições (entre as 6) são o movimento “cima”:
$$C(6, 3) = \mathbf{20} \text{ caminhos}$$
Exercício 4 — Pontos gerando retas e triângulos
Com 10 pontos no plano em posição geral (sem 3 colineares), quantas retas e triângulos distintos podem ser formados?
Resposta:
- Retas: cada par de pontos determina exatamente uma reta: \(C(10,2) = \mathbf{45}\)
- Triângulos: cada trio de pontos determina exatamente um triângulo: \(C(10,3) = \mathbf{120}\)
Exercício 5 — Subconjuntos de tamanho variado
Quantos subconjuntos não vazios de tamanho ≤ 3 podem ser formados com 7 elementos?
Resposta: Somamos as combinações para cada tamanho (Princípio Aditivo):
$$C(7,1) + C(7,2) + C(7,3) = 7 + 21 + 35 = \mathbf{63}$$
Exercício 6 — Equipes com restrição
Em uma turma de 6 meninos e 4 meninas, quantas equipes de 4 têm pelo menos 1 menina?
Resposta: Por complemento:
$$C(10,4) - C(6,4) = 210 - 15 = \mathbf{195}$$Próximos passos #
A combinação simples \(C(n, r)\) fecha a tríade fundamental da combinatória clássica: junto com a permutação e o arranjo, ela cobre a grande maioria dos problemas de contagem com elementos distintos.
A limitação de todos esses três instrumentos é exatamente essa exigência de distinção: cada elemento pode aparecer no máximo uma vez. Mas e quando há repetições? Quantos anagramas tem a palavra MISSISSIPPI? Quantos números de 7 algarismos podem ser formados com os dígitos \(\{1, 1, 2, 2, 2, 3, 3\}\)?
Esses problemas nos levam às permutações com repetição, tema do próximo artigo da série.
