Permutazione vs. Combinazione: Qual è la differenza tra la formula di permutazione e la formula di combinazione?

Permutazione vs. Combinazione: Qual è la differenza tra la formula di permutazione e la formula di combinazione?

Ecco la versione breve.

Prendiamo come esempio il suono delle campane in una chiesa.

Una permutazione è un ordine delle campane. Stai trovando l’ordine migliore per suonarle.

Una combinazione è la scelta delle campane. Stai scegliendo le campane da suonare. Se hai troppe campane, prima le scegli, e poi pensi ad ordinarle.

Questo dà origine all’identità familiare: (n P r) = (n C r) * r!

Il modo di ordinare r oggetti su n è di scegliere prima r oggetti su n, e poi ordinare i r oggetti (r! )

E, questo significa (n P r) = n! / (n-r)! e (n C r) = n! / ( (n-r)! * r! )

Ma vuoi sapere come ricordarlo per sempre?

Sono un grande fan del pensiero per principi primi. Per capire un problema, andare al nocciolo, e ragionare da lì.

Non fare questo è di solito la fonte della confusione: se non capisco come funzionano le cose, non so dove appendere i concetti. Il mio quadro mentale non è completo, quindi decido di ricordare e basta.

Come potete immaginare, questo non è l’ideale. Così, di tanto in tanto, mi concedo un esercizio di derivazione dalla fonte, e costruisco l’intuizione di come funzionano le cose.

Questa volta, stiamo costruendo l’intuizione di permutazioni e combinazioni.

Per esempio, sai perché la formula di una combinazione è (n C r)? Da dove viene? E perché si usano i fattoriali qui?

Cominciamo dalla fonte. Fattoriali, permutazioni e combinazioni sono nati da matematici che giocavano insieme, proprio come Steve Jobs e Steve Wozniak hanno fondato la Apple giocando insieme nel loro garage.

Proprio come la Apple è diventata una società a pieno titolo redditizia, il semplice fattoriale, !, è diventato l’atomo di un intero campo della matematica: la combinatoria.

Dimenticate tutto, cominciamo a pensare dal basso verso l’alto.

Il primo caso d’uso interessante conosciuto venne dalle chiese nel XVII secolo.

Vi siete chiesti come vengono suonate le campane nelle chiese? C’è una macchina che le “suona” in ordine. Siamo passati alle macchine perché le campane sono troppo grandi. Inoltre, ci sono tonnellate di campane.

Come ha fatto la gente a capire la sequenza migliore per suonarle? E se volevano cambiare le cose? Come potevano trovare il suono migliore? Ogni campanile aveva fino a 16 campane!

Non si poteva cambiare la velocità con cui si poteva suonare una campana – le macchine suonavano solo una campana al secondo. L’unica cosa che si poteva fare era cambiare l’ordine delle campane. Quindi, questa sfida consisteva nel capire l’ordine migliore.

Potremmo, strada facendo, scoprire anche tutti gli ordini possibili? Vogliamo conoscere tutti gli ordini possibili per capire se vale la pena provarli tutti.

Un campanaro, Fabian Stedman ha raccolto questa sfida.

Ha iniziato con 2 campane. In quale ordine poteva suonare queste campane?

1 e 2.
o
2 e 1.

Questo aveva senso. Non c’era altro modo.

Che ne dici di 3 campane?

1, 2, e 3.
1, 3, e 2.

Poi partendo dalla seconda campana,

2, 1, e 3.
2, 3, e 1.

Poi partendo dalla terza campana,

3, 1, e 2.
3, 2, e 1.

Totale, 6.

Poi si rese conto che questo era molto simile a due campane!

Se aveva fissato la prima campana, allora il numero di modi per ordinare le altre due campane era sempre due.

In quanti modi poteva fissare la prima campana? Una qualsiasi delle 3 campane poteva essere quella giusta!

Ok, continuò. Poi arrivò a 5 campane.

Questo è il momento in cui si rese conto che fare le cose a mano è ingombrante. Hai solo tanto tempo nella giornata, devi suonare le campane, non puoi rimanere bloccato a disegnare tutte le possibili campane. C’era un modo per capirlo velocemente?

Tornò alla sua intuizione.

Se aveva 5 campane, e aveva sistemato la prima campana, tutto quello che doveva fare era capire come ordinare 4 campane.

Per 4 campane? Beh, se aveva 4 campane, e ha riparato la prima campana, tutto quello che doveva fare era capire come ordinare 3 campane.

E lui sapeva come fare questo!

Così, ordine di 5 campane = 5 * ordine di 4 campane.

Ordine di 4 campane = 4 * ordine di 3 campane

Ordine di 3 campane = 3 * ordine di 2 campane.

. Vedi lo schema, vero?

Fatto divertente: Questa è la chiave per una tecnica di programmazione chiamata ricorsione.

Lo fece anche lui. Anche se gli ci volle molto più tempo, dato che nessuno vicino a lui l’aveva già scoperto.

Così, capì che l’ordinamento di 5 campane = 5 * 4 * 3 * 2 * 1.

Questa formula di ordinamento, nel 1808, divenne nota come fattoriale.

Pensiamo alla notazione fattoriale come alla base, ma l’idea esisteva molto prima che avesse un nome. Fu solo quando il matematico francese Christian Kramp notò che veniva usato in alcuni posti che gli diede il nome di fattoriale.

Questo ordinamento di campane è chiamato permutazione.

Una permutazione è un ordinamento di elementi.

Quando si impara qualcosa, penso che aiuti guardare le cose da ogni diversa angolazione, per solidificare la comprensione.

E se provassimo a ricavare la formula di cui sopra direttamente, senza cercare di ridurre il problema a un numero minore di campane?
Abbiamo 5 spazi, giusto?

In quanti modi possiamo scegliere la prima campana? 5, perché è il numero di campane che abbiamo.

La seconda campana? Beh, abbiamo consumato una campana quando l’abbiamo messa nella prima posizione, quindi ci restano 4 campane.

La terza campana? Bene, abbiamo scelto le prime due, quindi rimangono solo 3 campane tra cui scegliere.

La quarta campana? Sono rimaste solo 2 campane, quindi 2 opzioni.
La quinta campana? Ne è rimasta solo 1, quindi 1 opzione.

Ed ecco, il numero totale di ordinamenti è 5 * 4 * 3 * 2 * 1

Quindi, abbiamo la nostra prima formula generale.

Il numero di modi di ordinare N articoli è N!

Ora, ci troviamo di fronte a un problema diverso. Il re ha ordinato di fare nuove campane per ogni chiesa. Alcune sono belle, altre vanno bene, altre ti fanno diventare sordo. Ma ognuna è unica. Ognuna fa il suo suono. Una campana assordante circondata da belle campane può avere un suono maestoso.

Ma il nostro campanile contiene ancora 5 campane, quindi dobbiamo capire quale sia l’ordine migliore tra le 8 campane che gli abili costruttori hanno fatto.

Utilizzando la logica di cui sopra, possiamo procedere.

Per la prima campana, possiamo scegliere una qualsiasi delle 8 campane.

Per la seconda campana, possiamo scegliere una qualsiasi delle altre 7 campane… e così via.

Alla fine, otteniamo 8 * 7 * 6 * 5 * 4possibili ordinamenti di 8 campane in 5 spazi.

Se avete familiarità con la versione della formula (n P r), che è n! / (n-r)!, non preoccupatevi, deriveremo anche quella abbastanza presto!

Un brutto modo di ricavarla è quello di moltiplicare sia il numeratore che il denominatore per 3! nel nostro esempio sopra –

otteniamo 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.

Ma questo non ci aiuta a capire perché questa formula funziona. Prima di arrivarci, diamo un’occhiata alla scelta delle cose, o alla Combinazione.

La Combinazione

Ora che sappiamo come ordinare le cose, possiamo capire come scegliere le cose!

Consideriamo lo stesso problema. C’è un campanile con 5 campane, e tu hai 8 campane. Tuttavia, in questo momento, non vuoi capire l’ordine delle campane (ricorda che è una permutazione).

Invece, vuoi scegliere le 5 campane migliori, e lasciare che qualcun altro con un gusto musicale migliore capisca l’ordine. In effetti, stiamo dividendo il problema in due parti: Per prima cosa, capiamo quali campane scegliere. Poi, capiamo come ordinare le campane scelte.

Come si scelgono le campane? Questa è la “combinazione” da permutazioni e combinazioni.

La combinazione è una selezione. Tu sei selettivo. Stai scegliendo 5 campane su 8 che i tuoi artigiani hanno fatto.

Siccome sappiamo come ordinare le campane, useremo questa informazione per capire come scegliere le campane. Sembra impossibile? Aspettate di vedere la bellissima matematica coinvolta.

Immaginiamo che tutte le campane siano in fila.

Prima di trovare tutti i modi per scegliere le campane, concentriamoci su un modo per scegliere le campane.

Un modo è scegliere 5 a caso. Questo non ci aiuta molto a risolvere il problema, quindi proviamo un altro modo.

Mettiamo le campane in fila, e scegliamo le prime 5. Questo è un modo per scegliere le campane.

Nota che, anche se cambiamo la posizione delle prime 5 campane, la scelta non cambia. Sono ancora lo stesso unico modo di scegliere 5 campane uniche.

Questo è vero anche per le ultime tre campane.

Ora, il bel trucco matematico – per questo unico modo di scegliere le 5 campane, quali sono tutti gli ordinamenti di 8 campane dove scegliamo esattamente queste 5 campane? Dall’immagine sopra, sono tutti gli ordinamenti delle 5 campane (5!) e tutti gli ordinamenti delle tre campane rimanenti (3!).

Quindi, per ogni singolo modo di scegliere 5 campane, abbiamo (5! * 3!) ordinamenti di 8 campane.

Quali sono gli ordinamenti totali possibili di 8 campane? 8!.

Ricordo che per ogni scelta delle prime 5 campane, abbiamo (5! * 3!) ordinamenti di 8 campane che danno la stessa scelta.

Allora, se moltiplichiamo il numero di modi di scegliere le prime 5 campane con tutti gli ordinamenti possibili di una scelta, dovremmo ottenere il numero totale di ordinamenti.

Ways to choose 5 bells * orderings of one choice = Total orderings

Così,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice.

In matematica, questo diventa:

(8 C 5) = 8! / ( 5! * 3!)

Ecco, abbiamo trovato una spiegazione intuitiva per come scegliere 5 cose su 8.

Ora, possiamo generalizzare questo. Se abbiamo N cose, e vogliamo sceglierne R, significa che tracciamo una linea a R.

Il che significa che gli elementi rimanenti saranno N-R. Quindi, per una scelta di R oggetti, abbiamo R! * (N-R)! ordinamenti che danno gli stessi R oggetti.

Per tutti i modi di scegliere R oggetti, abbiamo N! / (R! * (N-R)!) possibilità.

Il numero di modi per scegliere r oggetti su n è (n C r) = n! / (r! * (n-r)!)

In termini colloquiali, (n C r) si pronuncia anche n choose r, il che aiuta a solidificare l’idea che le combinazioni sono per scegliere gli oggetti.

La Permutazione – rivisitata

Fatta la combinazione e spolverata, torniamo alla parte 2 del nostro lavoro. Il nostro caro amico ha scelto le migliori 5 campane capendo tutte le possibili combinazioni di 5 campane.

Ora il nostro compito è trovare la melodia perfetta capendo il numero di ordinamenti.

Ma questa è la parte facile. Sappiamo già come ordinare 5 elementi. È 5!, e abbiamo finito.

Quindi, per permutare (ordinare) 5 elementi su 8, prima scegliamo 5 elementi, poi ordiniamo i 5 elementi.

In altre parole,

(8 P 5) = (8 C 5) * 5!

E se espandiamo la formula, (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

E, siamo tornati alla nostra formula originale, derivata correttamente.

Il numero di modi per ordinare r elementi su n è (n P r) = n! / (n-r)!

Differenza tra permutazione e combinazione

Spero che questo renda chiara la differenza tra permutazioni e combinazioni.

Le permutazioni sono ordinamenti, mentre le combinazioni sono scelte.

Per ordinare N elementi, abbiamo trovato due modi intuitivi per capire la risposta. Entrambi portano alla risposta, N!.

Per permutare 5 elementi su 8, bisogna prima scegliere i 5 elementi, poi ordinarli. Si sceglie usando (8 C 5), poi si ordinano i 5 usando 5!.

E l’intuizione per scegliere R su N è capire tutti gli ordinamenti (N!) e dividere per gli ordinamenti dove il primo R e l’ultimo N-R rimangono uguali (R! e (N-R)!).

E questo è tutto quello che c’è nelle permutazioni e combinazioni.

Ogni permutazione e combinazione avanzata usa questo come base. Combinazione con sostituzione? Stessa idea. Permutazione con elementi identici? Stessa idea, cambia solo il numero di ordinamenti, dato che alcuni elementi sono identici.

Se ti interessa, possiamo approfondire i casi complessi in un altro esempio. Fatemelo sapere su Twitter.

Guarda altri post sul mio blog, e iscriviti alla mailing list settimanale.

Note finali

1. Questo è il modo in cui immagino abbia capito le cose. Non prenderla come una lezione di storia.
2. Gli indiani avevano, nel XII secolo, 400 anni prima di lui.