Permutações e combinações explicadas

O princípio fundamental da contagem

Os problemas de contagem perguntam de quantas maneiras algo pode acontecer. A base é o princípio fundamental da contagem, ou princípio multiplicativo: se uma escolha pode ser feita de $m$ maneiras e uma segunda escolha, independente, de $n$ maneiras, as duas juntas podem ser feitas de $m \times n$ maneiras. A ideia vale para qualquer número de etapas.

Com 3 camisas, 4 calças e 2 pares de sapatos, você pode montar $3 \times 4 \times 2 = 24$ looks diferentes. Uma senha de quatro dígitos usando os algarismos de 0 a 9, com repetição permitida, tem $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ possibilidades. Todas as fórmulas deste artigo são atalhos dessa multiplicação: quando um problema parecer estranho, voltar a uma contagem etapa por etapa é sempre uma aposta segura.

Os fatoriais

Para enfileirar $n$ objetos distintos, há $n$ escolhas para o primeiro lugar, $n - 1$ para o segundo, e assim por diante até 1. Esse produto se chama fatorial de $n$:

Assim, $5! = 120$: cinco livros podem ser arrumados em uma prateleira de 120 maneiras diferentes. Por definição, $0! = 1$, o que mantém as fórmulas seguintes coerentes, já que existe exatamente uma maneira de arrumar “nada”. Os fatoriais crescem a uma velocidade impressionante: $10! = 3{,}628{,}800$, e um baralho embaralhado tem $52!$ ordens possíveis, um número de 68 algarismos.

Permutações e arranjos: a ordem importa

Um arranjo, também chamado de permutação parcial, é uma sequência ordenada de $r$ objetos escolhidos entre $n$ objetos distintos. Como a ordem importa, primeiro-segundo-terceiro é diferente de terceiro-segundo-primeiro. O número de arranjos é

Acomodar pessoas em volta de uma mesa redonda é um caso especial. Deslocar todo mundo uma cadeira dá a mesma disposição, então $n$ pessoas podem se sentar de $(n-1)!$ maneiras diferentes. Seis pessoas em volta de uma mesa redonda têm $5! = 120$ disposições, e não 720. Essa é a chamada permutação circular.

Combinações: a ordem não importa

Uma combinação é uma escolha em que só importa quais elementos foram escolhidos. Escolher Ana, Ben e Clara para uma comissão dá a mesma comissão, seja qual for a ordem. Cada grupo de $r$ objetos corresponde a $r!$ arranjos, então dividimos por esse número:

As combinações são simétricas: $\binom{n}{r} = \binom{n}{n-r}$, porque escolher as 3 pessoas que entram equivale a escolher as 5 que ficam de fora. Elas também são os números do triângulo de Pascal e os coeficientes do desenvolvimento do binômio $(a + b)^n$.

Como saber qual usar

Faça uma única pergunta: se eu trocar dois dos elementos escolhidos de lugar, obtenho um resultado diferente? Se sim, a ordem importa e você precisa de arranjos. Se não, use combinações.

• Colocações, classificações, senhas, disposições de lugares e horários: arranjos.
• Times, comissões, mãos de cartas, apostas de loteria e coberturas de pizza: combinações.
• Cargos dentro de um grupo, como presidente e tesoureiro, fazem a ordem importar mesmo que as pessoas venham do mesmo grupo.

Uma verificação rápida: o número de arranjos é sempre $r!$ vezes o número de combinações. Se os seus dois resultados não respeitarem essa relação, um deles está errado.

Contagem com repetição e letras repetidas

Quando os elementos podem se repetir, as fórmulas mudam. As escolhas ordenadas com repetição são $n^r$, como no exemplo da senha. As escolhas não ordenadas com repetição, como pegar 3 bolas de sorvete entre 5 sabores podendo repetir sabor, são

Arrumar letras com repetições exige mais um ajuste: dividir pelo fatorial de cada quantidade de repetições, porque trocar letras iguais de lugar não muda nada. A palavra MISSISSIPPI tem 11 letras, sendo 4 letras I, 4 letras S e 2 letras P: ela tem, portanto, $\frac{11!}{4!\,4!\,2!} = 34{,}650$ anagramas distintos.

Contagem para calcular probabilidades

Quando os resultados são igualmente prováveis, uma probabilidade é o número de casos favoráveis dividido pelo número de casos possíveis: arranjos e combinações fazem, portanto, a maior parte do trabalho. A base dessa razão é explicada em noções básicas de probabilidade.

Os jogos de cartas oferecem outros exercícios. Há $\binom{52}{5} = 2{,}598{,}960$ mãos possíveis de cinco cartas. Uma mão com os quatro ases só precisa de mais uma carta, escolhida entre as outras 48, então a probabilidade é $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$.

Erros comuns

• Usar arranjos para um time ou uma comissão, o que conta a mais por um fator $r!$.
• Esquecer que $0! = 1$, o que estraga fórmulas como $\binom{n}{n}$.
• Não levar em conta elementos iguais, como nos anagramas com letras repetidas.
• Multiplicar etapas que não são independentes sem ajustar as contagens seguintes.

A calculadora de permutações e combinações calcula ${}_nP_r$ e ${}_nC_r$ detalhando as etapas com os fatoriais, e a calculadora de probabilidade transforma essas contagens em probabilidades.

O triângulo de Pascal e os subconjuntos

Cada número do triângulo de Pascal é a soma dos dois números logo acima, e a linha $n$ contém os valores $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. A linha 4 é 1, 4, 6, 4, 1, exatamente os coeficientes de $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. A regra que constrói o triângulo, a relação de Stifel, é ela própria um resultado de contagem:

Para entender por quê, fixe um elemento específico. Toda escolha de $r$ elementos ou o contém, e restam $r - 1$ elementos a escolher entre os outros $n - 1$, ou o exclui, e restam os $r$ elementos a escolher entre os outros $n - 1$. A soma de uma linha inteira é $2^n$, o número total de subconjuntos de um conjunto com $n$ elementos, já que cada elemento está dentro ou fora. Uma pizzaria que oferece 8 coberturas pode, portanto, preparar $2^8 = 256$ pizzas diferentes, contando a que não tem nenhuma cobertura.

Exercícios

1. De quantas maneiras se podem arrumar em uma prateleira 4 livros escolhidos entre 7 livros diferentes? Solução: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. De quantas maneiras se podem escolher 4 coberturas entre 10? Solução: $\binom{10}{4} = 210$.
3. Quantos anagramas distintos tem a palavra BANANA? Solução: $\frac{6!}{3!\,2!} = 60$.
4. Quantos códigos de cinco letras podem ser formados com 26 letras se a repetição for permitida? Solução: $26^5 = 11{,}881{,}376$.

Perguntas frequentes