Articles

Explicar: Permutações vs. Combinações

Sim, estou a falar daqueles botões místicos na sua calculadora (nCr e nPr) que você graciosamente acerta e exprime a resposta correcta. Magia.

Os dois conceitos são bastante simples, pelo que não deve demorar muito tempo a explicar. Vou explicar as diferenças; quando as usar; e o que exactamente a sua calculadora está a calcular quando as introduz (a equação).

p> Por isso a melhor maneira de ilustrar o seu caso de uso é através de dois exemplos:

Exemplo 1: Há 10 atletas a competir numa prova em que o primeiro classificado receberá uma medalha de ouro, o segundo classificado receberá uma medalha de prata, e o terceiro classificado receberá uma medalha de bronze. Se ganharem uma medalha, poderão estar no pódio de nível. Os restantes não receberão nada… nem sequer um troféu de participação… porque isto é a América… e se não for o primeiro, será o último.

p>questão 1: quantas possibilidades existem para o pódio?

Questão 2: quantas possibilidades existem para quem ganha uma medalha?

Quando se usa nPr e quando se usa nCr?

Quando se usam:

as duas perguntas podem parecer semelhantes, mas existe uma diferença fundamental que ditará qual a equação a usar.

Question 1 (podium) factors in the relevance of order:

Se Bob, Lacy, e Sarah estiverem no podium, Bob vir em primeiro lugar não é o mesmo que Bob vir em segundo. Este é um resultado diferente. A ordem é relevante, pelo que será usado nPr.

nPr (permutações) é usado quando a ordem é importante.

Questão 2 não tem em conta a ordem do pódio, é simplesmente perguntar quem ganha uma medalha. A questão não é delinear entre ouro, prata, ou bronze, são todas medalhas e isso é tudo o que importa. Quando a ordem não importa, usa-se nCr.

nCr (combinações) quando a ordem não importa.

O que eles realmente fazem:

Agora que esperamos que compreenda quando usar qual deles, passemos ao que eles realmente fazem.

nPr
Como mencionado, nPr está a encontrar todas as permutações que existem dentro de um determinado conjunto para um determinado subconjunto. No nosso exemplo em particular, ele analisará quantos resultados diferentes podem resultar da corrida, o que resultaria numa permutação de pódio (ordem diferente).

há 2730 resultados diferentes que podem ocorrer com o pódio

esta é a equação que está a calcular. n é o número de concorrentes na corrida, e r é o número que chega ao pódio

na nossa corrida:

15 -3 = 12

Okay, por isso quebrámos um pouco mais o botão mágico, mas pode estar a perguntar-se agora…porque é que esta é a equação, e porque é que todos os números gritam comigo!!!! – o que significa o !

! ou de outra forma conhecido como factorial é simplesmente uma forma conveniente de expressar uma série de multiplicação.

Em particular:

Isto é dizer que n! = n x (n-1) x (n-2) (n-2) (n-2)…e assim por diante até chegar ao fundo – mas não a zero porque quando se multiplica por zero a resposta torna-se zero

p>Vamos ilustrar voltando ao nosso exemplo:

n = 15 (porque há 15 atletas)

n! = 15! = 15 x 14 x 13 x 12 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 4 x 3 x 2 x 1

Isto é o que a sua calculadora está a calcular quando introduz o botão !button.

15! = 1 307 674 368 000

este número representa o número máximo de ordens diferentes que podem ocorrer a partir de uma lista. A nossa lista tem 15 corredores, e existem 1 307 674 368 000 formas diferentes de organizar a sua colocação. O número multiplicado está a diminuir porque, à medida que um número é colocado, esse lugar é agora ocupado.

Se o corredor 1 colocar no 15º lugar, há apenas 14 outros lugares para todos os restantes corredores, se o corredor 2 colocar no 14º lugar, restam agora apenas 13 lugares para todos os corredores. Como a maioria das coisas, é mais facilmente explicado escalonando os números:

Exemplo mais simples (pode saltar se já se agarrar):

p>>>p>Vamos dizer que há quatro lugares disponíveis, e 4 amigos que procuram sentar-se. Para o primeiro lugar, há quatro resultados potenciais (qualquer um dos quatro amigos pode agarrá-lo), uma vez ocupado, o segundo lugar só tem três resultados potenciais diferentes (qualquer um dos 3 amigos não sentados pode agarrá-lo), o terceiro lugar só tem duas possibilidades, e o último lugar, por defeito, só tem uma opção – o pobre otário que ainda não se sentou.

Como resultado, matematicamente, há 4 x 3 x 2 x 1 resultados potenciais.

Se a corrida estivesse simplesmente a perguntar de quantas formas diferentes a ordem da corrida pode mudar, não usaríamos nPr, usaríamos factorial(!)…mas não é…é perguntar quantas vezes o pódio pode mudar, o que é olhar especificamente para os três melhores corredores, não todos eles. Como resultado, não utilizamos factorial(!). Factorial é um âmbito demasiado amplo.

Porque é demasiado amplo, precisamos de o reduzir. Estamos apenas a examinar as três primeiras posições, não as 12 restantes. Apresentada de forma diferente, se a ordem das três primeiras mudar, então é considerada uma nova permutação, mas se a ordem das três primeiras permanecer a mesma, (mesmo que a ordem das 12 restantes se altere) então não a consideramos uma nova permutação.

Porque 12 posições são irrelevantes, precisamos de reduzir a sua importância na equação.

É por isso que obtemos

div>>

A maneira mais fácil de remover a relevância das restantes 12 posições é dividir o número total de possibilidade(!) pelo número possível para as posições irrelevantes. Como anteriormente referido, existem 12 posições que são irrelevantes para o nosso pódio.

so 15! divididas por (15 -3)!

12 porque é o número de corredores cuja ordem não nos interessa

p>Isto equivale a escrever:

que equivale a 15 x 14 x 13 porque todos os outros números se cancelam a si próprios.

15 x 14 x 13 também = 2730

Agora vejamos o nCr:

>Quando demorou muito tempo a passar pelas permutações, esta ronda deveria ser mais rápida porque já falei agora de factores.

Como mencionado, nCr, está a encontrar todas as combinações que existem dentro de um dado conjunto para um dado subconjunto quando a ordem não importa. No nosso exemplo, analisa-se o número de diferentes combinações que podem ocorrer para ganhar a medalha (ou seja terminando nos três primeiros)

15c3 é geralmente escrito na forma de colchete mas significa a mesma coisa

agora mesmo fora do taco, notará que há menos combinações do que permutações (455 < 2730). Isto faz sentido porque as combinações estão a marcar ABC e ACB como iguais, enquanto que a permutação diferencia entre as duas. Vamos examinar o que a sua calculadora está a fazer quando se carrega no botão.

equation para nCr

Agora a primeira coisa que deve notar é que a equação é bastante semelhante à equação das permutações, excepto que há mais a acrescentar ao denominador (é k!(n-r)!, não apenas (n-r)!

De acordo com a afirmação anterior, isto faz sentido, pois adicionar mais ao denominador resultará num resultado menor (por exemplo 10/2) < 10/5), e estabelecemos que as combinações serão menores do que as permutações.

Se prestou atenção/minha escrita faz algum sentido, já devemos saber porque é que adiciona (n-r)! à equação. Se não o fizer, ctrl/command +f “too wide a scope” e leia novamente essa passagem.

Adicionamos r! ao denominador porque há r! maneiras de os medalhados permanecerem os mesmos, enquanto a ordem deles muda.

Para cada conjunto de três medalhados, eles podem ser misturados cerca de 3! vezes para criar uma nova permutação (3! = 6 vezes)…mas não nos importamos com esta permutação. Essas 6 permutações diferentes são realmente apenas uma combinação de atletas, por isso queremos retirá-la da nossa resposta. A forma mais fácil de o fazer é adicioná-la ao denominador, de modo a ser retirada do numerador.

= 455

Não é coincidência que 455 x 3! = 2730.

Anyways, é tudo o que tenho por hoje. Esperemos que faça sentido.

Ciao,

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *