Uma permutação põe todos os itens em ordem. Muitas vezes só alguns deles são necessários: três medalhas para oito corredores, um presidente e um tesoureiro escolhidos num clube, uma senha de quatro dígitos feita com dez algarismos. Escolher k itens entre n e pô-los em ordem se chama arranjo. Este capítulo apresenta o método das casas (ou dos tracinhos), a ferramenta mais confiável para esse tipo de contagem, deduz a fórmula dos arranjos com e sem repetição e dá um teste simples para a pergunta que decide quase todo problema de contagem: a ordem importa?
Ao final você vai conseguir
- Usar o método das casas: uma casa por posição, o número de opções em cada uma, casas restritas primeiro.
- Contar arranjos de k entre n itens, com a fórmula n!/(n − k)! e sem ela.
- Contar sequências com repetição permitida, nᵏ.
- Decidir se a ordem importa com o teste da troca.
- Resolver problemas de algarismos com restrições, separando em casos quando necessário.
Desenhe uma casa (um tracinho) para cada posição do resultado. Escreva em cada casa o número de opções daquela posição no momento em que ela é preenchida. Multiplique as casas. É só isso: o princípio multiplicativo escrito de um jeito que se vê. O método tem uma regra que importa: preencha as casas numa ordem em que cada casa tenha um número fixo de opções. Na prática, isso quer dizer as casas restritas primeiro.
Uma casa por posição; o número numa casa é quantas opções aquela posição tem no momento em que é preenchida. Multiplique as casas. O numerozinho em cima de uma casa é a ordem em que ela é preenchida: a casa com restrição vai primeiro, para que a contagem de toda casa seguinte seja a mesma qualquer que tenha sido a escolha anterior. Quando a restrição não se resolve assim (o último algarismo é 0 ou não?), separe em casos, uma linha cada, e some as linhas.
Na figura, escolha "par, 3 algarismos distintos". Se o último algarismo é 0 ou não muda quantas opções o primeiro algarismo tem (o 0 é proibido ali, mas se o 0 já foi usado no fim, todos de 1 a 9 continuam disponíveis). Nenhuma ordem de preenchimento deixa todas as casas fixas, então o problema se divide em dois casos, cada um contado pelas casas, e os casos se somam: 72 + 256 = 328. Separar em casos é a resposta sempre que uma restrição afeta outra.
Oito corredores disputam uma prova e são entregues ouro, prata e bronze. Três casas: 8 opções para o ouro, 7 para a prata (qualquer um menos o vencedor), 6 para o bronze: 8 · 7 · 6 = 336 pódios. O produto começa em n e tem k fatores, um por casa, cada um uma unidade menor que o anterior. Essa contagem se chama arranjo simples de n itens tomados k a k, escrito A(n, k), Aₙ,ₖ ou P(n, k). Para escrevê-la com fatoriais, multiplique e divida pela cauda que falta, 5 · 4 · 3 · 2 · 1 = 5!.
Quando um item pode ser usado de novo, toda casa tem as n opções. Uma senha de 4 dígitos: 10 · 10 · 10 · 10 = 10⁴ = 10 000. Uma sequência de 8 bits, cada um 0 ou 1: 2⁸ = 256. Um código de 3 letras com repetição: 26³ = 17 576. Esses são arranjos com repetição, e a contagem deles é uma potência.
| Código | com repetição | sem repetição |
|---|---|---|
| 4 dígitos | 10⁴ = 10 000 | 10 · 9 · 8 · 7 = 5040 |
| 3 letras | 26³ = 17 576 | 26 · 25 · 24 = 15 600 |
| 6 letras minúsculas | 26⁶ = 308 915 776 | 26 · 25 · 24 · 23 · 22 · 21 = 165 765 600 |
O erro mais comum em contagem é usar arranjo onde cabe combinação, ou o contrário. Um teste resolve. Pegue um resultado e troque de lugar dois dos itens escolhidos. Se a troca dá um resultado diferente, a ordem importa, e você está fazendo um arranjo. Se dá o mesmo resultado, a ordem não importa, e você está escolhendo um grupo (uma combinação, o assunto do próximo capítulo).
| Situação | Trocar dois dos escolhidos | A ordem importa? |
|---|---|---|
| ouro e prata entre 8 corredores | o campeão e o vice mudam: outro pódio | sim: arranjo |
| 2 representantes de uma turma, com funções iguais | as mesmas duas pessoas: a mesma dupla | não: combinação |
| presidente e tesoureiro de um clube | os cargos trocam de mãos: outra diretoria | sim: arranjo |
| 6 números num bilhete de loteria | o mesmo conjunto de números: o mesmo bilhete | não: combinação |
| uma senha de 4 dígitos | 1234 e 2134 abrem cadeados diferentes | sim: arranjo |
| 3 coberturas de pizza entre 10 | a mesma pizza | não: combinação |
Questões sobre números formados com algarismos são os problemas de arranjo mais frequentes nas provas. Elas combinam três tipos de restrição: o primeiro algarismo não pode ser 0, os algarismos podem ter de ser distintos, e o número pode ter de ser par, ímpar, múltiplo de 5 ou estar dentro de uma faixa. O método das casas com as casas restritas primeiro resolve todas.
Números pares com algarismos distintos: dois casos
Números acima de um limite
Com os algarismos 1, 2, 3, 4, 5 e 6, sem repetição, quantos números de 3 algarismos são maiores que 400? A restrição está no primeiro algarismo: 4, 5 ou 6, 3 opções. Depois 5 e 4 opções para os outros dois: 3 · 5 · 4 = 60. Múltiplos de 5 com os mesmos algarismos: o último precisa ser 5, 1 opção; depois 5 · 4 para os dois primeiros: 20.
Restrições entre pessoas: no máximo um por casal
Dez casais formam um clube, e é escolhida uma diretoria com presidente, secretário e tesoureiro, com no máximo uma pessoa de cada casal. Os cargos são diferentes, então a ordem importa: três casas. Presidente: qualquer uma das 20 pessoas. Secretário: não o presidente, nem o cônjuge do presidente, 20 − 2 = 18. Tesoureiro: nem as duas pessoas já escolhidas nem seus dois cônjuges, 20 − 4 = 16. Total 20 · 18 · 16 = 5760. Cada escolha tira das opções um casal inteiro.
1. Uma turma de 30 elege um representante e um vice: A(30, 2) = 30 · 29 = 870 resultados possíveis.
2. Uma prova de 5 questões de múltipla escolha com alternativas de A a E: cada jeito de responder é uma sequência de 5 letras com repetição, 5⁵ = 3125.
3. Números de quatro algarismos distintos que são ímpares: último algarismo ímpar, 5 opções; primeiro, nem 0 nem o último, 8; depois 8 e 7 para o meio: 8 · 8 · 7 · 5 = 2240.
4. Uma corrida com 12 cavalos e uma aposta nos três primeiros em ordem: A(12, 3) = 12 · 11 · 10 = 1320 apostas possíveis.
5. Três bandeiras diferentes são hasteadas em 5 mastros enfileirados, no máximo uma por mastro, e a posição nos mastros importa: A(5, 3) = 60 sinais.
| Errado | Certo | Por quê |
|---|---|---|
| 2 representantes iguais entre 30: 30 · 29 | 30 · 29/2 = 435 | trocar os dois representantes dá a mesma dupla; o teste da troca diz combinação |
| senha de 4 dígitos: 10 · 9 · 8 · 7 | 10⁴ | os dígitos de uma senha podem se repetir |
| pares de 3 algarismos distintos: 9 · 8 · 5 | 72 + 256 = 328 | o último algarismo ser 0 ou não muda as opções do primeiro; separe em casos |
| A(8, 3) = 8!/3! | 8!/5! | divida pelo fatorial dos itens NÃO usados, (n − k)! |
| diretoria entre 10 casais: 20 · 19 · 18 | 20 · 18 · 16 | cada escolha também tira o cônjuge daquela pessoa |
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
- Método das casas: uma casa por posição, as opções em cada uma, multiplique; casas restritas primeiro.
- Quando uma restrição muda as opções de outra casa, separe em casos e some.
- Arranjos simples: A(n, k) = n(n − 1)…(n − k + 1) = n!/(n − k)!.
- Com repetição permitida, toda casa mantém as n opções: nᵏ.
- Teste da troca: se trocar dois itens escolhidos dá um resultado novo, a ordem importa.