A pergunta central: a ordem importa?
Permutações e combinações contam o número de maneiras de escolher r itens de um grupo de n itens distintos, mas respondem a duas perguntas diferentes. Uma permutação conta o número de maneiras de escolher e arranjar r itens, de modo que duas seleções contendo os mesmos itens em ordem diferente são contadas como dois resultados separados. Uma combinação conta apenas o número de maneiras de escolher r itens, de modo que duas seleções contendo os mesmos itens são contadas como um único resultado, independentemente da ordem em que foram escolhidos.
Uma forma simples de decidir qual delas se aplica: imagine duas seleções que usam exatamente os mesmos itens, mas os listam ou arranjam de forma diferente. Se essas duas seleções representam resultados do mundo real genuinamente distintos -- classificações diferentes, senhas diferentes, ordens de chegada diferentes em uma corrida -- a ordem importa e uma permutação é a contagem correta. Se essas duas seleções representam o mesmo resultado do mundo real -- a mesma comissão, a mesma mão de cartas, o mesmo conjunto de números da loteria -- a ordem não importa e uma combinação é a contagem correta.
As fórmulas: nPr e nCr, com um exemplo verificado
O número de permutações de r itens escolhidos de n itens distintos é nPr = n! / (n − r)!, e o número de combinações é nCr = n! / [r! (n − r)!] -- a fórmula da combinação é a fórmula da permutação dividida por r!, porque dividir por r! remove os r! arranjos diferentes de cada grupo de mesmos itens que a contagem de permutações trata como separados.
Exemplo resolvido: escolher 3 itens de um grupo de 7. Permutações: 7P3 = 7! / (7−3)! = 7 × 6 × 5 = 210. Combinações: 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35. A contagem de combinações é exatamente a contagem de permutações dividida por 3! = 6, confirmando a relação nCr = nPr / r!.
| Quantidade | Fórmula | Valor para n=7, r=3 |
|---|---|---|
| Permutações (a ordem importa) | nPr = n! / (n − r)! | 7P3 = 7 × 6 × 5 = 210 |
| Combinações (a ordem não importa) | nCr = n! / [r!(n − r)!] | 7C3 = 210 / 3! = 35 |
Com repetição vs. sem repetição
As duas fórmulas acima pressupõem que cada um dos n itens pode ser selecionado no máximo uma vez -- amostragem sem repetição. Quando os itens podem ser reutilizados (amostragem com repetição, também chamada de amostragem com reposição), as fórmulas de contagem mudam. Permutações com repetição permitida simplesmente elevam n à potência r, já que cada uma das r posições tem, de forma independente, todas as n opções disponíveis, seja qual for a escolha anterior: n^r.
Combinações com repetição permitida usam uma fórmula diferente, C(n + r − 1, r), que conta o número de maneiras de escolher r itens de n tipos quando repetições são permitidas e a ordem ainda não importa -- esse é um caso menos frequente, mas que surge, por exemplo, ao escolher bolas de sorvete entre n sabores em que o mesmo sabor pode ser escolhido mais de uma vez.
| Caso | Fórmula | Exemplo típico |
|---|---|---|
| Permutações, sem repetição | n! / (n − r)! | Classificar 3 vencedores entre 7 finalistas |
| Permutações, com repetição | n^r | Um PIN de 4 dígitos em que os dígitos podem se repetir |
| Combinações, sem repetição | n! / [r!(n − r)!] | Escolher 6 números para um bilhete de loteria |
| Combinações, com repetição | (n + r − 1)! / [r!(n − 1)!] | Escolher 3 bolas entre 5 sabores de sorvete, com repetição permitida |
Exemplos resolvidos: um código PIN e um bilhete de loteria
Um PIN de 4 dígitos, em que cada uma das 4 posições pode ser qualquer dígito de 0 a 9 e os dígitos podem se repetir (a regra típica de PINs bancários), é um exemplo de permutações com repetição: a ordem importa (1234 e 4321 são PINs diferentes) e a repetição é permitida, dando 10^4 = 10.000 PINs possíveis. Se, em vez disso, dígitos repetidos não fossem permitidos, a contagem cairia para o valor de permutação sem repetição, 10P4 = 10 × 9 × 8 × 7 = 5.040 -- menos possibilidades, porque cada dígito usado remove uma opção para as posições restantes.
Um formato clássico de loteria que sorteia 6 números de um conjunto de 49, sem repetir nenhum número e com a ordem do sorteio irrelevante para saber se um bilhete é premiado, é um exemplo de combinações sem repetição: C(49, 6) = 49! / (6! × 43!) = 13.983.816. Esse número tão grande é exatamente o motivo pelo qual esses formatos de loteria são descritos como jogos de longas probabilidades -- uma contagem de combinações cresce muito rápido à medida que n aumenta em relação a r, já que ela conta grupos não ordenados de um conjunto grande, e não um pequeno número fixo de arranjos.
Uma forma rápida de lembrar qual fórmula usar
«Permutação» e «posição» começam com o mesmo som de P, e um recurso de memória útil é lembrar que as permutações se preocupam com a posição -- onde, na sequência, cada item se encaixa. «Combinação» descreve um grupo combinado, como o conteúdo de uma sacola ou uma comissão, em que só importa a composição, e não a sequência em que os membros foram adicionados.
Senhas, PINs, classificações de corrida e qualquer arranjo de assentos ou de agendamento são problemas de permutação, porque trocar a ordem muda o resultado. Mãos de cartas, conjuntos de números da loteria, composições de comissões e qualquer seleção de grupo não ordenado são problemas de combinação, porque os membros são a única coisa que importa, e não a sequência em que foram escolhidos.
Perguntas frequentes
Qual é a diferença entre uma permutação e uma combinação?
Uma permutação conta arranjos em que a ordem importa, então escolher os mesmos itens em ordem diferente conta como um resultado distinto. Uma combinação conta seleções em que a ordem não importa, então os mesmos itens em qualquer ordem contam como um único resultado. Ambas partem do mesmo grupo de n itens e envolvem escolher r deles, mas uma contagem de permutações é sempre maior ou igual à contagem de combinações correspondente para os mesmos n e r.
O que é 7P3 e como se calcula?
7P3 é igual a 210, o número de maneiras de escolher e arranjar 3 itens de um grupo de 7 itens distintos em que a ordem importa. É calculado como 7P3 = 7! / (7 − 3)! = 7 × 6 × 5 = 210, multiplicando os três maiores fatores de 7! entre si, já que os fatores menores se cancelam com (7−3)! no denominador.
O que é 7C3 e como se calcula?
7C3 é igual a 35, o número de maneiras de escolher 3 itens de um grupo de 7 itens distintos em que a ordem não importa. É calculado como 7C3 = 7! / (3! × 4!) = (7 × 6 × 5) / (3 × 2 × 1) = 210 / 6 = 35 -- exatamente a contagem de permutações, 7P3 = 210, dividida por 3! (o número de maneiras de reordenar cada grupo de 3), já que as combinações agrupam todos os arranjos do mesmo grupo em um único resultado.
Por que os PINs usam permutações e as loterias usam combinações?
Um PIN trata 1234 e 4321 como códigos diferentes, então a ordem dos dígitos muda o resultado, o que é um cenário de permutação -- com repetição permitida para um PIN típico de 4 dígitos, dando 10^4 = 10.000 possibilidades. Um bilhete de loteria é premiado apenas com base em quais números foram sorteados, não na ordem em que saíram, então dois sorteios com os mesmos números em ordem diferente são o mesmo resultado premiado, o que é um cenário de combinação -- para um formato de 6 entre 49, C(49,6) = 13.983.816 conjuntos de números possíveis.
O que significa «com repetição» em uma fórmula de permutação ou combinação?
Significa que um item pode ser selecionado mais de uma vez dentro do mesmo resultado. Permutações com repetição permitida usam n^r (cada uma das r posições tem, de forma independente, todas as n opções), enquanto combinações com repetição permitida usam (n + r − 1)! / [r!(n − 1)!]. Sem repetição, cada item pode ser usado no máximo uma vez, que é o que as fórmulas padrão nPr e nCr pressupõem.
Referências
- NIST Digital Library of Mathematical Functions (DLMF), §26 Combinatorial Analysis. dlmf.nist.gov.
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018 (permutations, combinations, and counting with repetition).
- Ross SM. A First Course in Probability. Pearson (combinatorial counting methods).
- Weisstein EW. "Permutation" and "Combination." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.