Permutações, arranjos e combinações cobrem a maioria dos problemas de contagem, mas algumas situações pedem mais uma ideia. Itens que podem ser escolhidos mais de uma vez num grupo sem ordem. Objetos repartidos entre pessoas ou caixas. Grupos que se sobrepõem, de modo que somar seus tamanhos conta alguns resultados duas vezes. Cartas que precisam errar todas o próprio envelope. E perguntas que não pedem "quantos", e sim "é certo que…". Este capítulo dá o método padrão de cada uma: estrelas e barras, divisão em grupos, inclusão–exclusão, permutações caóticas e o princípio da casa dos pombos.
Ao final você vai conseguir
- Contar escolhas com repetição e sem ordem com estrelas e barras, e as soluções inteiras de x + y + z = s.
- Repartir objetos diferentes entre grupos identificados, com ou sem condição, e tratar grupos sem identificação.
- Contar a união de conjuntos que se sobrepõem com a inclusão–exclusão.
- Contar permutações caóticas, ordens em que nenhum item fica no próprio lugar.
- Usar o princípio da casa dos pombos para provar que alguma coincidência precisa acontecer.
Uma sorveteria tem 5 sabores e você quer um copo com 3 bolas. Os sabores podem se repetir e a ordem das bolas não importa: duas bolas de chocolate e uma de limão é um copo só. Isso não é nem arranjo nem combinação comum. O truque é desenhar cada copo num código. Enfileire os 5 sabores como caixas separadas por 4 paredes (barras) e desenhe cada bola como uma estrela na sua caixa. ★★|★||| quer dizer duas bolas do sabor 1 e uma do sabor 2. Todo copo dá exatamente uma fila de 3 estrelas e 4 barras, e toda fila dessas dá um copo.
Em cima: os k itens iguais repartidos entre as n caixas; uma caixa pode ficar vazia. Embaixo: a mesma coisa escrita como uma fila, uma estrela por item e uma barra por parede entre duas caixas. Toda repartição dá uma fila e toda fila dá uma repartição, então basta contar as filas. Uma fila tem n + k − 1 lugares e fica determinada ao escolher quais k deles têm estrelas.
Uma fila tem 3 + 4 = 7 lugares e fica totalmente determinada quando você diz quais 3 dos 7 lugares têm estrelas. Então há C(7, 3) = 35 copos. Em geral, escolher k itens entre n tipos com repetição e sem ordem é ter k estrelas e n − 1 barras.
Soluções inteiras de uma equação
Quantas soluções x + y + z = 10 tem em números inteiros x, y, z ≥ 0? Leia como 10 estrelas iguais repartidas entre 3 caixas x, y e z: 10 estrelas e 2 barras, C(12, 2) = 66 soluções. Se cada variável precisa ser pelo menos 1, dê primeiro o 1 de cada uma. Isso usa 3 dos 10, e os 7 restantes são repartidos livremente.
| sem repetição | com repetição | |
|---|---|---|
| a ordem importa | A(n, k) = n!/(n − k)! | nᵏ |
| a ordem não importa | C(n, k) = n!/(k!(n − k)!) | C(n + k − 1, k) |
Grupos identificados: escolha por etapas
Sete presentes diferentes vão para três crianças: a mais velha ganha 3, a do meio 2 e a mais nova 2. As crianças são pessoas diferentes, então os grupos são identificados. Escolha os presentes da mais velha, C(7, 3) = 35, depois os da do meio entre os 4 que sobram, C(4, 2) = 6, e a mais nova fica com os 2 últimos, C(2, 2) = 1: 35 · 6 · 1 = 210. O mesmo número é 7!/(3! · 2! · 2!): pôr todos os presentes numa fila e cortar a fila em pedaços de 3, 2 e 2, onde a ordem dentro de cada pedaço não importa.
Uma condição sobre um dos grupos
Entre os sete presentes há um tablet e uma bola, e a criança mais velha precisa ganhar exatamente um deles, não os dois. Trate a condição primeiro. Qual dos dois vai para a mais velha: 2 opções. Os outros 2 presentes da mais velha saem dos 5 presentes comuns (o outro especial não pode): C(5, 2) = 10. Sobram 4 presentes, incluindo o outro especial, para a do meio: C(4, 2) = 6. A mais nova fica com o resto.
Grupos sem identificação
Seis jogadores são divididos em 3 duplas para um torneio. Contando por etapas, C(6, 2) · C(4, 2) · C(2, 2) = 15 · 6 · 1 = 90, mas essa é a contagem para duplas identificadas (dupla 1, dupla 2, dupla 3). As duplas não têm nome: as mesmas três duplas listadas em outra ordem são a mesma divisão. Três grupos do mesmo tamanho podem ser listados em 3! = 6 ordens, então há 90/6 = 15 divisões. Divida pelo fatorial do número de grupos só para grupos que têm o mesmo tamanho e nenhuma identificação.
Quantos números inteiros de 1 a 100 são divisíveis por 2 ou por 3? Há 50 múltiplos de 2 e 33 múltiplos de 3 (100/3 = 33,3…, arredondado para baixo). Mas 50 + 33 = 83 é demais: os múltiplos de 6 (6, 12, …, 96, que são 16 números) estão nas duas listas e foram contados duas vezes. Subtraia-os uma vez: 50 + 33 − 16 = 67. É o princípio aditivo consertado para grupos que se sobrepõem. Com três conjuntos, some os três tamanhos, subtraia as três interseções duas a duas e some de volta a interseção tripla, que as subtrações tiraram uma vez a mais.
Uma secretária põe n cartas em n envelopes endereçados completamente ao acaso. De quantos modos nenhuma carta chega ao próprio envelope? Uma ordem assim é uma permutação caótica (ou desarranjo), e a contagem se escreve Dₙ. Com 3 cartas, das 3! = 6 ordens só 2 mudam todas as cartas de lugar (BCA e CAB), então D₃ = 2. A inclusão–exclusão dá a contagem geral: comece com todas as n! ordens, tire as que fixam a carta 1, a carta 2 e assim por diante, some de volta as que fixam duas cartas, e continue.
| n | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Dₙ | 0 | 1 | 2 | 9 | 44 | 265 |
| Dₙ / n! | 0 | 0.5 | 0.333 | 0.375 | 0.367 | 0.368 |
O parêntese é o começo da série de 1/e, em que e ≈ 2,718 é a base dos logaritmos naturais. Então, para qualquer número de cartas acima de um punhado, a chance de nenhuma chegar ao seu envelope é quase exatamente 1/e ≈ 36,8%, sejam 6 cartas ou um milhão.
Se mais de n pombos entram em n casas, pelo menos uma casa fica com dois pombos. Parece óbvio demais para ser útil, mas prova coisas sem contá-las. Entre quaisquer 13 pessoas, duas fazem aniversário no mesmo mês: 13 pessoas, 12 meses. Uma gaveta tem meias de 3 cores, misturadas no escuro: tirar 4 meias garante um par da mesma cor, e 3 não garantem. A forma mais forte: se mais de n · k objetos vão para n caixas, alguma caixa fica com pelo menos k + 1 deles. Entre 367 pessoas, duas fazem aniversário no mesmo dia; entre 1000 pessoas, alguma data é compartilhada por pelo menos 3, porque 1000 > 366 · 2.
1. 6 balas iguais são repartidas entre 4 crianças, e uma criança pode ficar sem nenhuma: 6 estrelas e 3 barras, C(9, 3) = 84 modos. Se cada criança precisa ganhar pelo menos uma: dê uma para cada primeiro, sobram 2 balas: C(2 + 3, 3) = C(5, 3) = 10.
2. Uma padaria vende 4 tipos de pão, e um saco leva 6 pães: C(4 + 6 − 1, 6) = C(9, 6) = 84 sacos diferentes.
3. 12 alunos são divididos em 3 grupos de trabalho de 4, sem nome: C(12, 4) · C(8, 4) · C(4, 4)/3! = 495 · 70 · 1/6 = 5775. Se os grupos recebem temas diferentes, não divida: 34 650.
4. De 40 alunos, 25 estudam inglês, 18 estudam espanhol e 10 estudam os dois. Os que estudam pelo menos um: 25 + 18 − 10 = 33; os que não estudam nenhum: 40 − 33 = 7.
5. Quatro amigos trazem cada um um presente e sorteiam um ao acaso, como num amigo secreto. A chance de ninguém tirar o próprio: D₄/4! = 9/24 = 37,5%.
| Errado | Certo | Por quê |
|---|---|---|
| 3 bolas entre 5 sabores, com repetição: C(5, 3) = 10 | C(7, 3) = 35 | C(5, 3) proíbe sabores repetidos; use estrelas e barras |
| x + y + z = 10 com x, y, z ≥ 1: C(12, 2) | C(9, 2) = 36 | entregue os 1 obrigatórios antes de repartir |
| 6 jogadores em 3 duplas: 15 · 6 · 1 = 90 | 90/3! = 15 | as duplas não têm nome; listá-las em outra ordem é a mesma divisão |
| inglês ou espanhol: 25 + 18 = 43 | 25 + 18 − 10 = 33 | os 10 que estudam os dois foram contados duas vezes |
| meias de 3 cores: 6 meias garantem um par | 4 | 3 meias podem ser todas diferentes; a 4ª precisa repetir uma cor |
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
- k itens entre n tipos, com repetição e sem ordem: k estrelas e n − 1 barras, C(n + k − 1, k).
- Soluções inteiras de x₁ + … + xₙ = s: C(s + n − 1, n − 1); com cada xᵢ ≥ 1, entregue os 1 primeiro.
- Grupos identificados: escolha-os por etapas e multiplique; grupos sem identificação de mesmo tamanho: divida pelo número de ordens deles.
- Inclusão–exclusão: some os conjuntos, subtraia as interseções duas a duas, some de volta a interseção tripla.
- Permutações caóticas: Dₙ = n!(1 − 1/1! + 1/2! − … ± 1/n!), e Dₙ/n! é quase 1/e.
- Casa dos pombos: mais objetos que caixas obriga dois objetos na mesma caixa.