Spiegato: Permutazioni vs. Combinazioni

Sì, sto parlando di quei mistici pulsanti sulla tua calcolatrice (nCr e nPr) che graziosamente premi e sputa fuori la risposta corretta. Magico.

I due concetti sono abbastanza semplici, quindi non dovrebbe essere necessario spiegare troppo a lungo. Spiegherò le differenze; quando usarli; e cosa esattamente sta calcolando la vostra calcolatrice quando li inserite (l’equazione).

Il modo migliore per illustrare il loro caso d’uso è attraverso due esempi:

Esempio 1: Ci sono 10 atleti che competono in una gara dove il primo classificato riceverà una medaglia d’oro, il secondo classificato una medaglia d’argento, e il terzo classificato una medaglia di bronzo. Se vincono una medaglia, salgono sul podio a più livelli. Gli altri non ricevono nulla… nemmeno un trofeo di partecipazione… perché questa è l’America… e se non sei primo sei ultimo.

Domanda 1: quante possibilità ci sono per il podio?

Domanda 2: quante possibilità ci sono per chi vince una medaglia?

Quando si usa nPr e quando si usa nCr?

Quando usarle:

le due domande possono sembrare simili, ma c’è una differenza fondamentale che determina quale equazione usare.

La domanda 1 (podio) tiene conto della rilevanza dell’ordine:

Se Bob, Lacy e Sarah sono sul podio, Bob che arriva primo non è lo stesso che Bob che arriva secondo. Questo è un risultato diverso. L’ordine è rilevante, quindi si usa nPr.

nPr (permutazioni) si usa quando l’ordine conta.

La domanda 2 non tiene conto dell’ordine del podio, chiede semplicemente chi vince una medaglia. La domanda non sta delineando tra oro, argento o bronzo, sono tutte medaglie e questo è tutto ciò che conta. Quando l’ordine non conta, si usa nCr.

nCr (combinazioni) si usa quando l’ordine non conta.

Cosa fanno in realtà:

Ora che si spera che abbiate capito quando usare quale, passiamo a cosa fanno in realtà.

nPr
Come detto, nPr è trovare tutte le permutazioni che esistono in un dato insieme per un dato sottoinsieme. Nel nostro particolare esempio, guarderà quanti risultati diversi possono risultare dalla gara che risulterebbe in una permutazione del podio (ordine diverso).

Nella nostra gara:

Ok, quindi abbiamo scomposto un po’ di più il bottone magico, ma forse ora vi starete chiedendo… perché questa è l’equazione, e perché tutti i numeri mi stanno urlando contro!!!! – cosa significa il ! significa

! o altrimenti noto come fattoriale è semplicemente un modo conveniente per esprimere una serie di moltiplicazioni.

In particolare:

Illustriamo tornando al nostro esempio:

n = 15 (perché ci sono 15 atleti)

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

Questo è ciò che la vostra calcolatrice sta calcolando quando inserite il tasto !

15! = 1 307 674 368 000

questo numero rappresenta il numero massimo di ordini diversi che possono verificarsi da una lista. La nostra lista è di 15 corridori, e ci sono 1 307 674 368 000 modi diversi in cui il loro posizionamento può essere disposto. Il numero moltiplicato è decrescente perché quando un numero viene piazzato, quel posto viene occupato.

Se il corridore 1 si piazza al 15° posto, ci sono solo altri 14 posti da occupare per tutti i corridori rimanenti, se il corridore 2 si piazza al 14°, ci sono ora solo 13 posti rimasti per tutti i corridori. Come la maggior parte delle cose, è più facile da spiegare scalando i numeri:

Esempio più semplice (può saltare se già lo capisce):

Diciamo che ci sono quattro posti disponibili, e 4 amici che vogliono sedersi. Per il primo posto, ci sono quattro potenziali risultati (ognuno dei quattro amici può prenderlo), una volta che è stato preso, il secondo posto ha solo tre diversi risultati potenziali (uno qualsiasi dei 3 amici non seduti può prenderlo), il terzo posto ha solo due possibilità, e l’ultimo posto per default ha solo una opzione – il povero sfigato che non si è ancora seduto.

Come risultato, matematicamente, ci sono 4 x 3 x 2 x 1 risultati potenziali.

Se la gara chiedesse semplicemente in quanti modi diversi può cambiare l’ordine della gara, non useremmo nPr, ma il fattoriale(!)…ma non è così…si chiede quante volte può cambiare il podio, il che riguarda specificamente i primi tre corridori, non tutti. Di conseguenza, non usiamo factorial. Factorial è un ambito troppo ampio.

Perché è troppo ampio, dobbiamo ridurlo. Stiamo esaminando solo le prime tre posizioni, non le restanti 12. Detto diversamente, se l’ordine dei primi tre cambia, allora è considerata una nuova permutazione, ma se l’ordine dei primi tre rimane lo stesso, (anche se l’ordine dei restanti 12 cambia) allora non la consideriamo una nuova permutazione.

Perché 12 posizioni sono irrilevanti, dobbiamo ridurre la loro importanza nell’equazione.

Ecco perché otteniamo

Il modo più semplice per rimuovere la rilevanza delle restanti 12 posizioni è quello di dividere il numero completo di possibilità(!) per il numero possibile di posizioni irrilevanti. Come detto in precedenza, ci sono 12 posizioni che sono irrilevanti per il nostro podio.

quindi 15! diviso per (15 -3)!

Questo equivale a scrivere fuori:

che equivale a 15 x 14 x 13 perché tutto il resto dei numeri si annulla.

15 x 14 x 13 anche = 2730

Ora diamo un’occhiata a nCr:

Whew, c’è voluto molto tempo per passare attraverso le permutazioni, questo giro dovrebbe essere più veloce perché ho già parlato dei fattoriali ora.

Come detto, nCr, è trovare tutte le combinazioni che esistono in un dato insieme per un dato sottoinsieme quando l’ordine non ha importanza. Nel nostro esempio, cerca il numero di combinazioni diverse che possono verificarsi per vincere la medaglia (cioè finire nei primi tre)

Ora, subito noterete che ci sono meno combinazioni che permutazioni (455 < 2730). Questo ha senso perché le combinazioni marcano ABC e ACB come uguali, mentre la permutazione differenzia i due. Esaminiamo cosa fa la vostra calcolatrice quando premete il pulsante.

Ora la prima cosa che dovreste notare è che l’equazione è abbastanza simile a quella delle permutazioni, tranne che c’è un’aggiunta al denominatore (è k!(n-r), non solo (n-r)!

Secondo l’affermazione precedente, questo ha senso perché aggiungendo di più al denominatore si ottiene un risultato più piccolo (per esempio 10/2) < 10/5), e abbiamo stabilito che le combinazioni saranno più piccole delle permutazioni.

Se avete prestato attenzione/la mia scrittura ha senso, dovremmo già sapere perché si aggiunge (n-r)! all’equazione. Se non lo sai, ctrl/command +f “too wide a scope” e rileggi quel passaggio.

Aggiungiamo r! al denominatore perché ci sono r! modi in cui i vincitori di medaglie rimangono gli stessi, mentre l’ordine di essi cambia.

Per ogni serie di tre vincitori di medaglie, essi possono essere mescolati intorno 3! volte per creare una nuova permutazione (3! = 6 volte)… ma non ci interessa questa permutazione. Queste 6 diverse permutazioni sono in realtà solo una combinazione di atleti, quindi vogliamo estrarla dalla nostra risposta. Il modo più semplice per farlo è di aggiungerlo al denominatore in modo che venga estratto dal numeratore.

Non è un caso che 455 x 3! = 2730.

Ad ogni modo, questo è tutto quello che ho per oggi. Speriamo che abbia senso.

Ciao,