Uma permutação é uma ordenação de todos os itens de um grupo: a ordem dos corredores cruzando a linha de chegada, dos livros numa estante, das letras de uma palavra. Contar permutações é o princípio multiplicativo aplicado a uma situação especial, cada item usado exatamente uma vez, e isso leva a um dos números mais importantes da matemática, o fatorial. Este capítulo define o fatorial e ensina a manejá-lo à mão, conta permutações e depois acrescenta as três complicações que as provas adoram: condições sobre onde os itens podem ficar, itens que se repetem e itens sentados em círculo.
Ao final você vai conseguir
- Calcular fatoriais e simplificar quocientes de fatoriais sem multiplicá-los por inteiro.
- Contar as ordens de n itens diferentes e explicar por que são n!.
- Tratar condições: lugares fixos, itens juntos ou separados, um item antes de outro.
- Contar os anagramas de uma palavra com letras repetidas dividindo pelas repetições.
- Contar as disposições em volta de uma mesa redonda, e dizer por que a resposta é (n − 1)!.
De quantas ordens 5 livros diferentes podem ficar numa estante? Preencha a estante da esquerda para a direita. Qualquer um dos 5 livros pode ir primeiro. Seja qual for, sobram 4 para o segundo lugar, depois 3, depois 2, e o último livro vai para o último lugar: 5 · 4 · 3 · 2 · 1 = 120. Um produto de todos os números inteiros de n até 1 aparece com tanta frequência que ganhou nome e símbolo próprios: n fatorial, escrito n!.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| n! | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40 320 | 3 628 800 |
Por que 0! = 1
0! é definido como 1, e essa não é uma escolha arbitrária. Dois motivos independentes dão o mesmo valor. A regra n! = n · (n − 1)! lida de trás para a frente diz (n − 1)! = n!/n: descer na tabela é dividir pelo n que se deixa. Seguindo até o fim, 0! = 1!/1 = 1. E como contagem, existe exatamente um modo de ordenar nenhum item: não fazer nada. Com 0! = 1, toda fórmula desta seção funciona também nos casos extremos.
Simplificando quocientes de fatoriais
Fatoriais são enormes, mas quocientes de fatoriais costumam ser pequenos, porque a maior parte dos fatores se cancela. Nunca calcule os dois fatoriais para depois dividir: escreva o maior só até chegar ao menor e então cancele.
O fatorial cresce mais depressa que qualquer potência. 10! já passa de três milhões, 20! é cerca de 2,4 · 10¹⁸, e um baralho de 52 cartas pode ser embaralhado de 52! ≈ 8 · 10⁶⁷ ordens. Por isso um baralho bem embaralhado quase certamente está numa ordem em que nenhum baralho da história jamais esteve.
Uma ordenação de todos os n itens de um grupo, cada um usado exatamente uma vez, é uma permutação simples desses itens. O argumento da estante vale para qualquer n: n opções para o primeiro lugar, n − 1 para o segundo, até 1 para o último. Então há n! permutações. O símbolo P com o número de itens embaixo é o usual nos livros brasileiros: P₅ = 5! = 120.
Um uso clássico: anagramas. Um anagrama de uma palavra é qualquer ordenação das suas letras, faça sentido ou não. A palavra AMOR tem 4 letras diferentes, então tem P₄ = 4! = 24 anagramas: AMOR, AMRO, AOMR e assim por diante, incluindo ROMA. A palavra LIVRO tem 5 letras diferentes: 5! = 120 anagramas.
Questões de prova raramente pedem todas as ordens; elas acrescentam uma condição. Cada tipo de condição tem uma entrada padrão, e todas são o princípio multiplicativo com a parte restrita tratada primeiro.
Itens em lugares fixos
Quantos anagramas de LIVRO começam por vogal? Preencha primeiro o lugar restrito: a primeira letra é I ou O, 2 opções. As outras 4 letras ocupam os 4 lugares restantes em qualquer ordem: 4! = 24. Total 2 · 24 = 48. Começar por vogal e terminar em consoante: primeiro lugar 2 opções, último lugar 3 (L, V, R), meio 3! = 6: 2 · 3 · 6 = 36.
Itens que precisam ficar juntos: o bloco
Seis amigos fazem uma fila para uma foto, e dois deles, um casal, querem ficar lado a lado. Cole o casal num único bloco. Agora há 5 coisas para ordenar, o bloco e os outros 4: 5! = 120. Dentro do bloco, o casal pode ficar em 2! = 2 ordens. Total 120 · 2 = 240. Em geral, um bloco de m itens que precisam ficar juntos, entre n itens, dá (n − m + 1)! · m!.
Itens que precisam ficar separados: total menos juntos
Se o casal não pode ficar lado a lado, conte o contrário. Todas as ordens: 6! = 720. Ordens com o casal junto: 240. Toda ordem é uma coisa ou outra, então 720 − 240 = 480 ordens têm os dois separados. Contar o que você não quer e subtrair do total se chama contar pelo complementar, e muitas vezes é o caminho mais curto.
Um item antes de outro: simetria
Em quantas ordens dos 6 amigos a Ana fica em algum lugar à esquerda da Bia, não necessariamente ao lado dela? Troque as duas de lugar em qualquer ordem e você obtém uma ordem em que a Bia está à esquerda da Ana. Essa troca forma pares perfeitos entre as ordens, então exatamente metade delas tem a Ana primeiro: 720/2 = 360. Com três pessoas que precisam aparecer numa ordem dada entre si, divida por 3! = 6.
Filas alternadas
3 meninos e 3 meninas formam uma fila, alternando menino e menina. O padrão é M F M F M F ou F M F M F M: 2 casos. Em cada um, os meninos ocupam os seus 3 lugares de 3! = 6 modos e as meninas os delas de 3! = 6 modos. Total 2 · 6 · 6 = 72.
Quantos anagramas tem BANANA? A palavra tem 6 letras, então seriam 6! = 720 se fossem todas diferentes. Mas não são: há três A e dois N. Trocar dois A de lugar devolve a mesma palavra, então 720 conta cada palavra real várias vezes. A saída é fingir que as letras repetidas são diferentes, numerando-as, contar, e depois dividir pela numeração.
Cada ficha é uma palavra diferente feita com as mesmas letras. Numere as letras repetidas (A₁, A₂, A₃) como se fossem diferentes: aí há n! ordens, mas cada palavra real aparece uma vez para cada jeito de numerar suas repetições. O painel de baixo mostra essas cópias para a palavra selecionada; o número delas é o mesmo para toda palavra, então n! dividido por ele dá o número de fichas. Clique numa palavra para ver suas cópias numeradas.Toque numa palavra para ver suas cópias numeradas.
A mesma fórmula conta caminhos mínimos num quadriculado. Para andar de uma esquina de um quadriculado de ruas até a esquina 4 quarteirões a leste e 3 ao norte, indo sempre para leste (L) ou norte (N), todo trajeto é uma palavra de 7 movimentos com quatro L e três N, como LLNLNNL. Então o número de trajetos mínimos é 7!/(4! · 3!) = 35. Um trajeto que precisa passar por uma esquina dada são duas caminhadas dessas, uma depois da outra: multiplique-as.
Em volta de uma mesa redonda, o que importa é quem senta ao lado de quem, não qual cadeira é a "primeira". Se todo mundo se levanta e anda uma cadeira para a esquerda, a disposição na verdade não mudou. Então cada disposição real foi contada n vezes entre as n! ordens de uma fila, uma para cada giro. Dito de outra forma: fixe a cadeira de uma pessoa para eliminar o giro e ordene as outras n − 1 nas cadeiras restantes, como numa fila.
1. Oito atletas numa final: o número de ordens possíveis de chegada, sem empates, é 8! = 40 320.
2. Anagramas de ESCOLA que começam por S: o S fica fixo no primeiro lugar e as outras 5 letras são livres: 5! = 120.
3. Anagramas de ARARA: 5 letras, três A e dois R: 5!/(3! · 2!) = 120/12 = 10.
4. Sete livros numa estante, os 3 de matemática juntos em qualquer ordem: bloco de 3 mais 4 outros livros, 5 coisas: 5! · 3! = 120 · 6 = 720.
5. Cinco crianças brincam de roda de mãos dadas: (5 − 1)! = 24 rodas diferentes.
| Errado | Certo | Por quê |
|---|---|---|
| 0! = 0 | 0! = 1 | há um modo de ordenar nada, e isso mantém n! = n · (n − 1)! verdadeiro para n = 1 |
| 10!/5! = 2! | 10 · 9 · 8 · 7 · 6 = 30 240 | fatoriais não se dividem como os números de dentro; cancele a cauda comum |
| BANANA: 6! = 720 anagramas | 6!/(3! · 2!) = 60 | trocar letras iguais dá a mesma palavra; divida pelas repetições |
| casal junto: 5! = 120 | 5! · 2! = 240 | os dois dentro do bloco também podem trocar de lugar |
| 6 pessoas numa mesa redonda: 6! = 720 | 5! = 120 | girar todo mundo junto é a mesma disposição |
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
- n! = n · (n − 1) · … · 1, e n! = n · (n − 1)!; 0! = 1.
- Quocientes de fatoriais se cancelam: escreva o maior só até o menor.
- n itens diferentes têm Pₙ = n! ordens.
- Lugares fixos primeiro; um bloco que fica junto conta como um item, vezes suas ordens internas; "separados" é total menos juntos.
- Itens repetidos: divida n! pelo fatorial de cada número de repetições.
- Em volta de uma mesa redonda com cadeiras iguais: (n − 1)!.