Combinações vs Permutações

Nós jogamos em torno do termo "combinação " de forma imprecisa, e geralmente de maneira errada. Dizemos coisas como: "Ei, qual é a sua combinação de armários?", Mas o que realmente devemos dizer é "Ei, qual é a permutação de seu armário ?"

Então qual a diferença? E o que exatamente é uma permutação?

Como saber a diferença

A diferença entre combinações e permutações é ordenada. Com as permutações, nos preocupamos com a ordem dos elementos, enquanto com as combinações não.

Por exemplo, digamos que seu armário “combo” é 5432. Se você digitar 4325 no seu armário, ele não será aberto porque é uma ordenação diferente (permutação aka).

As permutações de 2, 3, 4, 5 são:

  • 5432, 5423, 5324, 5342, 5234, 5243, 4532, 4523, 4325, 4352, 4253, 4235, 3542, 3524, 3425, 3452, 3254, 3245, 2543, 2534, 2435, 2453, 2354, 2345

Seu armário "combo" é uma permutação específica de 2, 3, 4 e 5. Se o seu armário funcionasse verdadeiramente por combinação, você poderia inserir qualquer uma das permutações acima e abriria!

Calculando Permutações com Facilidade

Suponha que você queira saber quantas permutações existem dos números 2, 3, 4, 5 sem listá-las como eu fiz acima. Como você conseguiria isso?

Vamos usar um diagrama de linhas para nos ajudar a visualizar o problema.

Queremos descobrir quantas permutações de 4 dígitos possíveis podem ser feitas a partir de quatro números distintos. Comece desenhando quatro linhas para representar os 4 dígitos.

O primeiro dígito pode ser qualquer um dos 4 números, então coloque um “4” no primeiro espaço em branco.

Agora restam 3 opções para o segundo espaço em branco, porque você já usou um dos números no primeiro espaço em branco. Coloque um “3” no próximo espaço.

Para a terceira posição, você tem dois números restantes.

E há um número restante para a última posição, então coloque um “1” lá.

O princípio da multiplicação

Usando o princípio de multiplicação de combinatória, sabemos que se houver x maneiras de fazer uma coisa e formas y de fazer outro, então o número total de maneiras de fazer as duas coisas é x • y. Isso significa que precisamos multiplicar para encontrar as permutações totais.

Esta é uma ótima oportunidade para usar a notação fatorial de taquigrafia (!) :

Existem 24 permutações, que correspondem à listagem que fizemos no início deste post.

Permutações com Repetição

E se eu quisesse encontrar o número total de permutações envolvendo os números 2, 3, 4 e 5, mas deseja incluir pedidos como 5555 ou 2234, onde nem todos os números são usados, e alguns são usados ??mais de uma vez?

Quantas dessas permutações existem?

Isso acaba sendo um cálculo simples. Novamente estamos compondo um número de 4 dígitos, então desenhe 4 linhas para representar os dígitos.

Na primeira posição temos 4 opções numéricas, assim como antes colocamos um “4” no primeiro espaço em branco. Como temos permissão para reutilizar números, agora temos 4 opções de números disponíveis para o segundo dígito, terceiro dígito e quarto dígito também.

Isso é o mesmo que:

Ao permitir que os números sejam repetidos, acabamos com 256 permutações!

Escolhendo um Subconjunto

Vamos subir a parada com um problema mais desafiador:

Quantas mãos diferentes de 5 cartas podem ser feitas de um baralho padrão de cartas?

Neste problema, a ordem é irrelevante, pois não importa qual ordem selecionamos.

Começaremos com cinco linhas para representar nossa mão de 5 cartas.

Supondo que ninguém mais esteja comprando cartas do baralho, existem 52 cartas disponíveis no primeiro sorteio, então coloque “52” no primeiro espaço em branco.

Depois de escolher um cartão, haverá um cartão a menos disponível no próximo sorteio. Então o segundo espaço em branco terá 51 opções. O próximo sorteio terá duas cartas a menos no baralho, então agora há 50 opções e assim por diante.

São 311.875.200 permutações .

Isso é permutações, não combinações. Para corrigir isso, precisamos dividir pelo número de mãos que são permutações diferentes, mas a mesma combinação.

Isto é o mesmo que dizer quantas maneiras diferentes posso arranjar 5 cartas?

Nota: Isto é matematicamente semelhante a encontrar as diferentes permutações do nosso combo de armário

Então o número de combinações de mãos de cinco cartas é:

Reescrevendo com Factorials

Com um pouco de criatividade, podemos reescrever o cálculo acima usando fatoriais.

Nós sabemos 52! = 52 • 51 • 50 •… • 3 • 2 • 1, mas só precisamos dos produtos dos inteiros de 52 a 48. Como podemos isolar apenas esses inteiros?

Nós gostaríamos de dividir todos os números inteiros, exceto aqueles de 48 a 52. Para fazer isso, divida por 47! já que é o produto dos inteiros de 47 para 1.

Certifique-se de dividir por 5! para se livrar das permutações extras:

Aqui vamos nós!

Ora aqui está a parte legal ? nós realmente derivamos a fórmula para combinações.

Fórmula de Combinações

Se tivermos n objetos e quisermos escolher k deles , podemos encontrar o número total de combinações usando a seguinte fórmula:

leia: “n escolha k”

Por exemplo, temos 52 cartas (n = 52) e queremos saber quantas mãos de 5 cartas (k = 5) podemos fazer.

Conectando os valores que obtemos:

nota: (52–5)! = 47!

Qual é exatamente o que encontramos acima!

Muitas vezes você verá essa fórmula escrita em notação parêntese, como acima, mas alguns livros escrevem com um C gigante:

Várias notações para a fórmula de combinações

Fórmula de Permutações

A fórmula para permutações é semelhante à fórmula de combinações, exceto que não precisamos dividir as permutações, para que possamos remover k! do denominador:

leia: n permute k elementos