Permutação vs Combinação: Qual é a diferença entre a Fórmula de Permutação e a Fórmula Combinada?
Aqui está a versão curta.
Vamos tomar como exemplo os sinos tocando em uma igreja.
A permutação é uma encomenda dos sinos. Você está descobrindo a melhor ordem para tocá-los em.
Uma combinação é a escolha dos sinos. Você está escolhendo os sinos para tocar. Se você tiver muitos sinos, você primeiro os escolheria e depois pensaria em ordená-los.
Isso dá origem a uma identidade familiar: (n P r) = (n C r) * r!
A forma de encomendar r itens de n é primeiro escolher r itens de n, e depois encomendar os r itens (r! )
E, isto significa (n P r) = n! / (n-r)! e (n C r) = n! / ( (n-r)! * r! )
Mas quer saber como se lembrar disto para sempre?
Eu sou um grande fã dos primeiros princípios a pensar. Para entender um problema, chegar ao âmago dele, e raciocinar a partir daí.
Não fazer isso geralmente é fonte de confusão: se eu não entendo como as coisas funcionam, eu não sei onde pendurar os conceitos. Minha estrutura mental não está completa, então eu decido apenas lembrá-la.
Como você pode imaginar, isto não é o ideal. Então, de vez em quando, eu me entrego a um exercício de derivar coisas da fonte, e construir intuição para como as coisas funcionam.
Desta vez, estamos construindo intuição para permutações e combinações.
Por exemplo, você sabe porque a fórmula para uma combinação é (n C r)? De onde é que isto veio? E porque são usados factores aqui?
Vamos começar pela fonte. Fatoriais, Permutações e Combinações nasceram de matemáticos jogando juntos, muito parecido com como Steve Jobs e Steve Wozniak fundaram a Apple jogando juntos em sua garagem.
Apenas como a Apple se tornou uma empresa lucrativa de pleno direito, o simples fatorial, !, tornou-se o átomo de todo um campo da matemática: a combinatória.
Esqueça tudo, vamos começar a pensar de baixo para cima.
O primeiro caso de uso interessante conhecido veio das Igrejas no século XVII.
Você se perguntou como os sinos são tocados nas igrejas? Há uma máquina que os “toca” em ordem. Nós mudamos para máquinas porque os sinos são muito grandes. Além disso, há toneladas de sinos.
Como é que as pessoas descobriram a melhor sequência para os tocar? E se eles quisessem mudar as coisas para cima? Como poderiam encontrar o melhor som? Cada campanário tinha até 16 sinos!
Não se podia mudar a rapidez com que se podia tocar uma campainha – as máquinas só tocavam uma campainha a cada segundo. A única coisa que podias fazer era mudar a ordem dos sinos. Então, este desafio era sobre descobrir a melhor ordem.
Podemos nós, no caminho, também descobrir todas as ordens possíveis? Queremos saber todas as ordens possíveis para descobrir se vale a pena tentar todas.
Um sineiro, Fabian Stedman aceitou este desafio.
Ele começou com 2 sinos. Quais eram as diferentes encomendas em que ele podia tocar estes sinos?
1 e 2.
ou
2 e 1.
Isso fazia sentido. Não havia outra maneira.
Como com 3 sinos?
1, 2, e 3.
1, 3, e 2.
Então começando com o segundo sino,
2, 1, e 3.
2, 3, e 1.
Então começando com o terceiro sino,
3, 1, e 2.
3, 2, e 1.
Total, 6.
Então ele percebeu que isto era muito semelhante a dois sinos!
Se ele consertasse o primeiro sino, então o número de maneiras de ordenar os dois sinos restantes era sempre dois.
Quantas maneiras ele poderia consertar o primeiro sino? Qualquer um dos 3 sinos poderia ser o único!
Okay, ele continuou. Ele então alcançou 5 sinos.
Foi então que ele percebeu que fazer as coisas à mão é difícil. Você só tem tanto tempo no dia, você tem que tocar sinos, você não pode ficar preso desenhando todos os sinos possíveis. Houve uma maneira de perceber isto rapidamente?
Ele voltou à sua visão.
Se ele tivesse 5 sinos, e consertasse a primeira campainha, tudo o que ele tinha que fazer era descobrir como pedir 4 sinos.
Para 4 sinos? Bem, se ele tivesse 4 sinos, e ele consertasse o primeiro sino, tudo o que ele tinha que fazer era descobrir como pedir 3 sinos.
E ele sabia como fazer isso!
Então, pedir 5 sinos = 5 * pedido de 4 sinos.
Ordem de 4 sinos = 4 * pedido de 3 sinos.
Ordem de 3 sinos = 3 * pedido de 2 sinos.
… Você vê o padrão, não vê?
Facto: Esta é a chave para uma técnica de programação chamada recursividade.
Ele também o fez. Embora tenha demorado muito mais tempo, já que ninguém perto dele já tinha descoberto isto.
Então, ele descobriu que a ordenação de 5 sinos = 5 * 4 * 3 * 2 * 1.
Esta fórmula de ordenação, em 1808, passou a ser conhecida como factorial.
Pensamos na notação factorial como base, mas a ideia já existia muito antes de ter um nome. Foi somente quando o matemático francês Christian Kramp notou que ela era usada em alguns lugares que ele a chamou de fatorial.
Esta ordenação de sinos é chamada de permutação.
A Permutação é uma ordenação de itens.
Quando se aprende algo, penso que ajuda ver as coisas de todos os ângulos diferentes, para solidificar a compreensão.
E se tentássemos derivar a fórmula acima directamente, sem tentar reduzir o problema a um número menor de sinos?
Temos 5 espaços, certo?
Quantas formas podemos escolher o primeiro sino? 5, porque é esse o número de sinos que temos.
O terceiro sino? Bem, nós escolhemos os dois primeiros, então só nos restam 3 sinos para escolher.
O quarto sino? Só restam 2 sinos, portanto 2 opções.
>O quinto sino? Só falta 1, então 1 opção.
E aí está, o número total de pedidos é 5 * 4 * 3 * 2 * 1
Assim, temos a nossa primeira fórmula geral.
O número de formas de encomendar
NItens éN!
Agora, estamos diante de um problema diferente. O rei ordenou que fossem feitos novos sinos para cada igreja. Alguns são bons, outros são bons, alguns vão fazer-te ficar surdo. Mas cada um deles é único. Cada um faz o seu próprio som. Um sino ensurdecedor rodeado de belos sinos pode soar majestoso.
Mas, a nossa torre do sino ainda tem 5 sinos, por isso precisamos de descobrir a melhor encomenda de 8 sinos que os habilidosos sinalizadores fizeram.
Usando a lógica acima, podemos prosseguir.
Para o primeiro sino, podemos escolher qualquer um dos 8 sinos.
Para o segundo sino, podemos escolher qualquer um dos 7 sinos restantes… e assim por diante.
No final, obtemos 8 * 7 * 6 * 5 * 4 possíveis pedidos de 8 sinos em 5 espaços.
Se você está familiarizado com a versão da fórmula de (n P r), que é n! / (n-r)!, não se preocupe, vamos obter isso em breve, também!
Uma maneira ruim de derivá-la é multiplicar tanto o numerador como o denominador por 3! em nosso exemplo acima –
obtemos 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.
mas isto não nos ajuda a entender porque esta fórmula funciona. Antes de chegarmos lá, vamos dar uma olhada na escolha das coisas, ou na Combinação.
A Combinação
Agora sabemos como ordenar as coisas, podemos descobrir como escolher as coisas!
Vamos considerar o mesmo problema. Há uma campainha com 5 sinos, e você tem 8 sinos. No entanto, neste momento, você não quer descobrir a ordem dos sinos (lembre-se que é isso que é uma permutação).
Em vez disso, você quer escolher os 5 melhores sinos, e deixar alguém com melhor gosto musical descobrir a ordem. Na verdade, nós estamos dividindo o problema em partes: Primeiro, descobrimos quais os sinos a escolher. Depois, descobrimos como encomendar os sinos escolhidos.
Como escolher os sinos? Esta é a “combinação” de permutações e combinação.
A combinação é uma selecção. Você está a ser selectivo. Você está escolhendo 5 dos 8 sinos que os seus artesãos fizeram.
Desde que saibamos como pedir os sinos, vamos usar esta informação para descobrir como escolher os sinos. Parece impossível? Espere até ver a bela matemática envolvida.
Vamos imaginar que todos os sinos estão em uma linha.
Antes de encontrar todas as formas de escolher os sinos, vamos nos concentrar em uma forma de escolher os sinos.
Uma forma é escolher qualquer 5 ao acaso. Isto não nos ajuda muito a resolver o problema, então vamos tentar outra maneira.
Pomos os sinos em linha, e escolhemos os primeiros 5. Esta é uma maneira de escolher os sinos.
Notem que, mesmo que troquemos as posições dos primeiros 5 sinos, a escolha não muda. Eles ainda são a mesma maneira de escolher 5 sinos únicos.
Isto também é verdade para os últimos 3 sinos.
Agora, o belo truque matemático – para esta maneira de escolher os 5 sinos, quais são todos os pedidos de 8 sinos onde escolhemos exactamente estes 5 sinos? Da imagem acima, são todas as encomendas dos 5 sinos (5!) e todas as encomendas dos restantes 3 sinos (3!).
Assim, para cada forma de escolher 5 sinos, temos (5! * 3!) encomendas de 8 sinos.
Qual é o total possível de encomendas de 8 sinos? 8!.
Lembrar, para cada escolha dos 5 primeiros sinos, temos (5! * 3!) pedidos de 8 sinos que dão a mesma escolha.
Então, se multiplicarmos o número de formas de escolher os 5 primeiros sinos com todos os pedidos possíveis de uma escolha, devemos obter o número total de pedidos.
Ways to choose 5 bells * orderings of one choice = Total orderingsEntão,
Ways to choose 5 bells = the total possible orderings / total orderings of one choice.Em matemática, que se torna:
(8 C 5) = 8! / ( 5! * 3!)Agora, encontramos uma explicação intuitiva de como escolher 5 coisas de 8.
Agora, podemos generalizar isto. Se temos N coisas, e queremos escolher R delas, significa que traçamos uma linha em R.
O que significa que os itens restantes serão N-R. Então, para uma escolha de R itens, temos R! * (N-R)! pedidos que dão o mesmo R itens.
Para todas as formas de escolher R itens, temos N! / (R! * (N-R)!) possibilidades.
O número de maneiras de escolher
ritens dené(n C r) = n! / (r! * (n-r)!)
Em termos coloquiais, (n C r) também é pronunciado n choose r, o que ajuda a solidificar a ideia de que as combinações são para escolher itens.
A Permutação – revisitada
Com a combinação feita e polvilhada, voltemos à Parte 2 do nosso trabalho. Nosso querido amigo escolheu os melhores 5 sinos descobrindo todas as combinações possíveis de 5 sinos.
É nosso trabalho agora encontrar a melodia perfeita descobrindo o número de pedidos.
Mas, esta é a parte fácil. Nós já sabemos como encomendar 5 itens. É 5!, e estamos prontos.
Então, para permutar (ordenar) 5 itens de 8, primeiro escolhemos 5 itens, depois ordenamos os 5 itens.
Em outras palavras,
(8 P 5) = (8 C 5) * 5! E se expandirmos a fórmula, (8 P 5) = (8! / ( 5! * 3!)) * 5!
(8 P 5) = 8! / 3!.
E, chegamos ao círculo completo da nossa fórmula original, derivada corretamente.
O número de formas de ordenar
ritens dené(n P r) = n! / (n-r)!
Diferença entre permutação e combinação
E espero que isto faça a diferença entre permutações e combinações cristalinas.
Permutações são ordenações, enquanto combinações são escolhas.
Para ordenar N elementos, encontramos duas formas intuitivas de descobrir a resposta. Ambas levam à resposta, N!.
A fim de permutar 5 dos 8 elementos, você precisa primeiro escolher os 5 elementos, depois ordená-los. Você escolhe usando (8 C 5), depois ordene os 5 usando 5!.
E a intuição para escolher R de N é descobrir todas as ordenações (N!) e dividir por ordenações onde os primeiros R e últimos N-R permanecem os mesmos (R! e (N-R)!).
E, é tudo o que há para permutações e combinações.
Muitas permutações e combinações avançadas usam isto como base. Combinação com permutação? A mesma ideia. Permutação com itens idênticos? Mesma idéia, apenas o número de pedidos muda, já que alguns itens são idênticos.
Se você estiver interessado, podemos ir para os casos complexos em outro exemplo. Me informe no Twitter.
Cheque mais posts no meu blog, e entre na lista semanal de discussão.
End notes
- Foi assim que eu imagino que ele descobriu as coisas. Não tome isso como uma lição de história.
- Os índios tinham, no século XII, 400 anos antes dele.