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).
na nossa corrida:
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:
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
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)!
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)
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.
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.
Não é coincidência que 455 x 3! = 2730.
Anyways, é tudo o que tenho por hoje. Esperemos que faça sentido.
Ciao,