Uma comissão, um bilhete de loteria, uma mão de cartas, um conjunto de coberturas de pizza: em todos esses casos se escolhe um grupo, e a ordem em que os membros foram escolhidos não importa. Uma escolha assim é uma combinação. As combinações são a ferramenta mais usada da análise combinatória e da probabilidade, e saem direto dos arranjos: conte as escolhas ordenadas e depois divida pelo número de ordens em que cada grupo foi contado. Este capítulo deduz a fórmula, mostra como calculá-la depressa à mão e percorre as situações que as provas constroem em cima dela: dois grupos ao mesmo tempo, "pelo menos um", geometria, loterias e problemas que misturam ordem e grupo.
Ao final você vai conseguir
- Explicar por que uma combinação é um arranjo dividido por k!, e calcular C(n, k) à mão.
- Usar a simetria C(n, k) = C(n, n − k) para economizar contas.
- Contar grupos escolhidos por etapas em dois ou mais conjuntos, e grupos com "pelo menos" ou "no máximo".
- Contar segmentos, diagonais e triângulos a partir de pontos, e jogos de um campeonato.
- Separar, num problema misto, a parte que é combinação da parte que é arranjo.
De 8 pessoas, escolha uma comissão de 3 com funções iguais. Se as funções fossem diferentes (presidente, secretário, tesoureiro), a resposta seria o arranjo A(8, 3) = 8 · 7 · 6 = 336. Só que uma comissão não tem funções: {Ana, Bruno, Carla} é a mesma comissão em qualquer ordem em que seus membros tenham sido escolhidos. Entre as 336 escolhas ordenadas, essa comissão aparece uma vez para cada ordem dos seus 3 membros, ou seja, 3! = 6 vezes, e o mesmo vale para toda comissão. Então o número de comissões é 336/6 = 56.
Cada ficha é uma seleção possível de k letras entre as n primeiras. Desligue “a ordem importa” e AB e BA viram a mesma ficha: a lista encolhe por um fator k!, porque todo conjunto de k letras diferentes pode ser posto em ordem de k! jeitos. Ligue a repetição e as letras podem se repetir (AA, BB): com ordem isso dá nᵏ sequências, sem ordem dá as combinações com repetição contadas por estrelas e barras.
Não calcule os três fatoriais. Escreva em cima k fatores descendo a partir de n e embaixo k fatores descendo a partir de k, e cancele antes de multiplicar. C(10, 4) = (10 · 9 · 8 · 7)/(4 · 3 · 2 · 1): o 8 cancela com 4 · 2, o 9 com o 3, e sobra 10 · 3 · 7 = 210. O resultado é sempre um número inteiro, porque conta alguma coisa; se sobrou uma fração, algum fator se perdeu.
Simetria e casos extremos
Escolher as 3 pessoas que vão viajar é o mesmo que escolher as 5 que ficam, então C(8, 3) = C(8, 5) = 56. Em geral C(n, k) = C(n, n − k): trocar k por n − k só troca os dois fatoriais de baixo. Use isso para deixar k pequeno: C(100, 98) = C(100, 2) = 100 · 99/2 = 4950. Os casos extremos saem da fórmula e do bom senso: C(n, 0) = C(n, n) = 1 (um modo de não escolher nada, um modo de escolher tudo) e C(n, 1) = n. Os números C(n, k) formam o triângulo de Pascal, estudado no capítulo do binômio de Newton.
Uma comissão de 5 precisa ter exatamente 3 mulheres e 2 homens, escolhidos entre 6 mulheres e 4 homens. Monte-a em duas etapas: escolha as mulheres, C(6, 3) = 20 modos, e depois os homens, C(4, 2) = 6 modos. Cada escolha de mulheres combina com cada escolha de homens, então multiplique: 20 · 6 = 120. Dentro de cada etapa a ordem não importa; entre as etapas, vale o princípio multiplicativo de sempre.
"Pelo menos um homem" numa comissão de 5 entre 6 mulheres e 4 homens abrange os casos com 1, 2, 3 ou 4 homens. Daria para somar os quatro casos, mas o contrário de "pelo menos um homem" é um caso só, "nenhum homem", muito mais curto. Todas as comissões: C(10, 5) = 252. Comissões sem homem, só de mulheres: C(6, 5) = 6. Então 252 − 6 = 246 têm pelo menos um homem. "No máximo dois homens" são os casos com 0, 1 e 2 homens: C(6, 5) + C(4, 1) · C(6, 4) + C(4, 2) · C(6, 3) = 6 + 60 + 120 = 186.
Um conjunto de pontos determina figuras, e a figura não depende da ordem em que seus pontos são nomeados: o segmento AB é o segmento BA. Então isso são combinações. Com 10 pontos numa circunferência (nunca três numa mesma reta): segmentos C(10, 2) = 45, triângulos C(10, 3) = 120, quadriláteros C(10, 4) = 210.
| O que se conta | Como | Exemplo |
|---|---|---|
| diagonais de um polígono convexo de n lados | todos os segmentos entre vértices, menos os n lados | C(8, 2) − 8 = 20; n(n − 3)/2 |
| triângulos com n pontos, m deles numa mesma reta | todos os trios, menos os trios da reta (eles não formam triângulo) | C(10, 3) − C(4, 3) = 116 |
| apertos de mão quando n pessoas se cumprimentam todas | um aperto por dupla | C(10, 2) = 45 |
| jogos de um campeonato, cada time contra cada outro uma vez | um jogo por dupla de times; turno e returno (ida e volta) é arranjo | C(20, 2) = 190; A(20, 2) = 380 |
A Mega-Sena sorteia 6 números entre 60, e a ordem do sorteio não importa: C(60, 6) = (60 · 59 · 58 · 57 · 56 · 55)/720 = 50 063 860 resultados possíveis. Uma aposta simples de 6 números cobre um deles. Uma aposta de 7 números cobre todo conjunto de 6 dentro dos 7, que são C(7, 6) = 7 conjuntos: custa sete apostas simples e ganha exatamente sete vezes mais. Uma mão de 5 cartas de um baralho de 52: C(52, 5) = 2 598 960. Mãos com as 5 cartas do mesmo naipe: 4 naipes vezes C(13, 5) = 1287, então 5148.
Muitos problemas têm uma parte em que a ordem importa e outra em que não importa. Escolha uma comissão de 4 entre 10 pessoas e depois um coordenador entre os 4. Etapa 1, o grupo: C(10, 4) = 210. Etapa 2, um papel dentro do grupo: 4 opções. Total 840. A mesma contagem em outra ordem: primeiro o coordenador, 10 opções, depois os outros 3 membros com funções iguais, C(9, 3) = 84: 10 · 84 = 840. Dois métodos corretos precisam dar o mesmo número, e isso é uma boa conferência.
| Pergunta | Tipo | Contagem |
|---|---|---|
| 3 prêmios, ouro, prata e bronze, entre 10 alunos | arranjo | A(10, 3) = 720 |
| 3 prêmios iguais entre 10 alunos | combinação | C(10, 3) = 120 |
| 3 prêmios iguais, no máximo um por aluno, depois uma foto dos 3 vencedores em fila | combinação, depois permutação | 120 · 3! = 720 |
1. Uma aluna precisa responder 7 das 10 questões de uma prova: C(10, 7) = C(10, 3) = 120 modos de escolhê-las. Se as questões 1 e 2 são obrigatórias, ela escolhe as outras 5 entre as 8 restantes: C(8, 5) = 56.
2. De 5 bolas vermelhas e 4 azuis, tiram-se 3 de uma vez. Retiradas com 2 vermelhas e 1 azul: C(5, 2) · C(4, 1) = 10 · 4 = 40, entre C(9, 3) = 84 retiradas ao todo.
3. Uma pizzaria oferece 8 coberturas e uma pizza leva 3 diferentes: C(8, 3) = 56 pizzas. Com 2 ou 3 coberturas: C(8, 2) + C(8, 3) = 28 + 56 = 84.
4. Sequências de 8 bits com exatamente 3 uns: escolher quais 3 das 8 posições recebem os uns fixa a sequência: C(8, 3) = 56.
5. Retas por pares de 12 pontos, 5 dos quais estão numa mesma reta e nenhum outro trio é colinear: C(12, 2) − C(5, 2) + 1 = 66 − 10 + 1 = 57. Os 10 pares da reta especial dão todos a mesma reta, contada uma vez.
| Errado | Certo | Por quê |
|---|---|---|
| comissões de 3 entre 8: 8 · 7 · 6 = 336 | 336/3! = 56 | uma comissão não tem ordem; cada uma foi contada 3! vezes |
| 3 mulheres e 2 homens: C(6, 3) + C(4, 2) = 26 | C(6, 3) · C(4, 2) = 120 | as duas etapas são feitas uma depois da outra: multiplique |
| "pelo menos um homem": C(4, 1) · C(9, 4) = 504 | 252 − 6 = 246 | escolher "o" homem primeiro conta duas vezes uma comissão com dois homens |
| diagonais de um octógono: C(8, 2) = 28 | 28 − 8 = 20 | 8 desses segmentos são lados, não diagonais |
| C(10, 4) = 10!/4! | 10!/(4! · 6!) = 210 | as ordens dos escolhidos e dos não escolhidos são divididas |
Uma rodada de 10 perguntas
Acerte quantas conseguir. Os erros voltam no final, numa rodada de revisão.
Cada exercício é criado na hora, então uma rodada nova nunca é igual. O computador escolhe a resposta primeiro e monta a pergunta em volta dela, trabalhando com frações exatas, por isso o gabarito está sempre certo. As respostas são lidas de forma exata: 0,75, 3/4 e 6/8 contam como o mesmo número (quando a forma irredutível é pedida, 6/8 só recebe um lembrete). Uma resposta errada mostra a resolução linha por linha, na ordem em que a lição faz; o número novo de cada linha aparece colorido.
Ideias-chave
- Uma combinação é um grupo sem ordem: C(n, k) = A(n, k)/k! = n!/(k!(n − k)!).
- À mão: k fatores descendo a partir de n sobre k!, cancelando antes; o resultado é sempre inteiro.
- C(n, k) = C(n, n − k); C(n, 0) = C(n, n) = 1, C(n, 1) = n.
- Grupos escolhidos por etapas em conjuntos separados se multiplicam: C(6, 3) · C(4, 2).
- "Pelo menos um" costuma ser todos menos nenhum; escolher primeiro "o" membro especial conta em dobro.
- Pontos formam figuras sem ordem: segmentos C(n, 2), triângulos C(n, 3), diagonais C(n, 2) − n.
- Em problemas mistos, escolha o grupo (combinação) e depois distribua os papéis (arranjo).