Permutações e combinações: por que a ordem muda a contagem

Cinco pessoas se oferecem para um projeto. Você precisa de um líder e de um vice. Escolha o líder de cinco maneiras e depois o vice de quatro. Existem vinte atribuições.

Agora mude uma frase: você precisa de uma comissão com duas pessoas, sem funções separadas. As mesmas cinco pessoas produzem dez comissões. Nada aconteceu com as pessoas. O que mudou foi a definição de um resultado.

Permutações e combinações são duas maneiras de contar resultados sem listar todas as possibilidades. As fórmulas fazem sentido depois que você decide quais informações o resultado preserva. Este artigo constrói primeiro essa decisão e depois deriva a notação.

Comece pelas posições, não por uma fórmula

Imagine duas caixas vazias rotuladas líder e vice. A primeira caixa tem cinco ocupantes possíveis. Depois de preenchê-la, restam quatro pessoas para a segunda. Cada primeira escolha tem quatro continuações, resultando em:

$$5 \times 4 = 20$$

Esse é o princípio multiplicativo. Se cada opção em uma etapa tem o mesmo número de continuações possíveis, multiplique as contagens das etapas. Você pode visualizar uma árvore com cinco ramos, cada um se dividindo em mais quatro.

Os rótulos importam. Alex como líder e Bea como vice é diferente de Bea como líder e Alex como vice. São as mesmas pessoas em posições diferentes. Isso é uma seleção ordenada, chamada permutação.

Uma comissão não tem posições rotuladas. Escrever Alex, Bea ou Bea, Alex descreve o mesmo grupo. Se você usar a contagem de vinte atribuições para as comissões, terá contado cada grupo duas vezes.

O teste da troca mostra se a ordem importa

Pergunte: se eu trocar dois itens selecionados, obtenho um resultado diferente?

Para o pódio de uma corrida, sim. Ouro e prata são resultados diferentes. Para um conjunto de coberturas de pizza, normalmente não. Cogumelos com azeitonas é a mesma seleção que azeitonas com cogumelos.

A pergunta é sobre o modelo, não sobre o substantivo. Um problema pode pedir que você escolha três livros para comprar, ignorando a ordem, ou que organize três livros em uma estante, registrando a ordem. A palavra “livros” não informa qual fórmula se aplica.

Escreva um exemplo de resultado antes de calcular. “Líder Alex, vice Bea” contém funções. “O grupo formado por Alex e Bea” não. Esse pequeno passo evita mais erros do que memorizar uma folha maior de fórmulas.

Situação	O que o resultado registra	Modelo
Conceder ouro, prata e bronze	Pessoa em cada colocação	Ordenado, sem repetição
Selecionar três membros de uma comissão	Apenas participação	Sem ordem, sem repetição
Criar um código de quatro dígitos	Dígito em cada posição	Ordenado, repetição pode ser permitida
Escolher várias bolas de sorvete	Quantidades de cada sabor	Sem ordem, repetição pode ser permitida

As duas últimas linhas também exigem a pergunta sobre repetição. Não decida apenas pela ordem.

Fatoriais contam arranjos completos

Coloque quatro livros distintos em fila. Existem quatro escolhas para a primeira posição, três para a segunda, duas para a terceira e uma para a última:

$$4! = 4 \times 3 \times 2 \times 1 = 24$$

O ponto de exclamação significa fatorial. Ele abrevia o produto decrescente. Para um inteiro não negativo $n$, o fatorial conta os arranjos de todos os $n$ itens distintos.

Por que $0! = 1$? Existe um arranjo vazio. Você não faz nada, e o arranjo vazio está completo. Esse também é o valor que mantém $1! = 1 \times 0!$ coerente.

Não interprete fatorial como soma repetida nem como potência. Quatro fatorial é vinte e quatro; quatro elevado à quarta potência é duzentos e cinquenta e seis. Em um fatorial, as opções diminuem porque um item não pode ser usado novamente. Em uma potência, as opções permanecem constantes.

Permutações interrompem o produto mais cedo

Suponha que existam sete corredores e você queira apenas os três primeiros, sem empates. Há sete escolhas para o primeiro lugar, seis para o segundo e cinco para o terceiro:

$$P(7,3) = 7 \times 6 \times 5 = 210$$

Não importa como os outros quatro corredores terminam. Continuar multiplicando até um responderia a outra pergunta.

Para $r$ posições ordenadas preenchidas a partir de $n$ itens distintos sem repetição:

$$P(n,r) = \frac{n!}{(n-r)!}$$

O denominador cancela a parte não usada do fatorial. No exemplo dos corredores, dividir sete fatorial por quatro fatorial deixa exatamente sete vezes seis vezes cinco.

Essa fórmula pressupõe $0 \le r \le n$ e itens disponíveis distintos. Se o problema mudar essas condições, volte às caixas em vez de forçar os números na expressão.

Combinações eliminam arranjos duplicados

Escolha três pessoas entre sete para uma comissão. A contagem ordenada é 210, mas trata arranjos diferentes do mesmo trio como respostas diferentes.

Considere um trio: Alex, Bea e Chen. Seus membros podem ser listados em seis ordens: ABC, ACB, BAC, BCA, CAB e CBA. Cada trio aparece exatamente seis vezes na contagem ordenada, porque $3! = 6$.

Divida pelo número de arranjos duplicados:

$$\binom{7}{3} = \frac{210}{6} = 35$$

Em geral:

$$\binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Leia como “n escolhe r”. A primeira divisão elimina os itens não usados da contagem de arranjos; a segunda elimina ordens que você deixou de distinguir.

Há uma simetria útil aqui: $\binom{7}{3} = \binom{7}{4}$. Escolher as três pessoas que entram também identifica as quatro que não entram. As duas descrições apontam para o mesmo conjunto de decisões.

A repetição muda a pergunta outra vez

Um código de quatro dígitos pode usar qualquer dígito de zero a nove em cada posição, inclusive no início. Dígitos repetidos são permitidos. Cada caixa tem dez escolhas:

$$10^4 = 10000$$

Se nenhum dígito puder se repetir, a contagem passa a ser:

$$10 \times 9 \times 8 \times 7 = 5040$$

Se o problema disser “número de quatro dígitos” em vez de “código”, um zero inicial normalmente é excluído. Com repetição permitida, isso dá:

$$9 \times 10 \times 10 \times 10 = 9000$$

Três frases muito parecidas, três contagens diferentes. A fórmula não se tornou pouco confiável. As restrições mudaram.

A seleção sem ordem e com repetição, como escolher bolas de sorvete com sabores repetidos, exige outro método de contagem. As combinações comuns pressupõem que cada item disponível pode ser escolhido no máximo uma vez. Reconhecer que uma fórmula conhecida não se aplica é um primeiro passo correto.

Percorra a decisão nesta ordem

Antes de calcular, escreva como é um resultado completo. Depois pergunte se a ordem ou as funções distinguem resultados, se um item pode se repetir e se existe alguma restrição especial para uma posição.

Tente estes três problemas sem olhar imediatamente para as respostas:

1. Entre seis pessoas, escolha um presidente e um secretário, sem que ninguém ocupe as duas funções.
2. Entre as mesmas seis pessoas, escolha dois representantes com o mesmo status.
3. Crie um código de três caracteres usando quatro símbolos, com repetição permitida.

O primeiro tem $6 \times 5 = 30$ atribuições. O segundo divide essa contagem por $2!$, dando quinze pares. O terceiro tem $4^3 = 64$ códigos porque os quatro símbolos continuam disponíveis em cada posição.

A explicação importa mais do que o número. Se você consegue dizer por que uma resposta divide por dois e outra não, entendeu a distinção.

A contagem é a base da probabilidade

Quando resultados igualmente prováveis são contados corretamente, você pode formar probabilidades comparando resultados favoráveis com todos os resultados possíveis. Nosso guia intuitivo de probabilidade dá esse próximo passo. O paradoxo do aniversário mostra como uma contagem escolhida com cuidado torna administrável um resultado surpreendente.

Por enquanto, mantenha a habilidade simples: defina um resultado, desenhe as posições, se houver, e explique cada fator. Use a prática de probabilidade do Math Zen para a próxima aplicação e volte a um exemplo pequeno sempre que a notação começar a esconder o raciocínio.

Uma permutação preserva o arranjo. Uma combinação preserva a participação. Dividir por um fatorial é simplesmente esquecer o arranjo sem contar o mesmo grupo de novo.