Permutare vs. combinare: Care este diferența dintre formula de permutare și formula de combinare?

Permutare vs. combinare: Care este diferența dintre formula de permutare și formula de combinare?

Iată varianta scurtă.

Să luăm ca exemplu dangătul clopotelor într-o biserică.

O permutare este o ordonare a clopotelor. Îți dai seama care este cea mai bună ordine în care să le suni.

O combinație este alegerea clopotelor. Alegi clopotele pe care să le suni. Dacă aveți prea multe clopote, mai întâi le alegeți și apoi vă gândiți să le ordonați.

Acest lucru dă naștere la identitatea familiară: (n P r) = (n C r) * r!

Modalitatea de a ordona r elemente din n este de a alege mai întâi r elemente din n, apoi de a ordona r elemente (r! )

Și, acest lucru înseamnă (n P r) = n! / (n-r)! și (n C r) = n! / ( (n-r)! * r! )

Dar vreți să știți cum să vă amintiți acest lucru pentru totdeauna?

Sunt un mare fan al gândirii bazate pe primele principii. Pentru a înțelege o problemă, ajungeți la miezul ei și raționați de acolo.

Nu face acest lucru este, de obicei, sursa confuziei: dacă nu înțeleg cum funcționează lucrurile, nu știu de unde să agăț conceptele. Cadrul meu mental nu este complet, așa că decid doar să mi-l amintesc.

Așa cum vă puteți imagina, acest lucru nu este ideal. Așa că, din când în când, mă complac într-un exercițiu de derivare a lucrurilor de la sursă și de construire a intuiției pentru modul în care funcționează lucrurile.

De data aceasta, construim intuiția pentru permutări și combinații.

De exemplu, știți de ce formula pentru o combinație este (n C r)? De unde a apărut aceasta? Și de ce sunt folosiți factoriali aici?

Să începem de la sursă. Factorialele, permutările și combinațiile s-au născut din faptul că matematicienii s-au jucat împreună, la fel cum Steve Jobs și Steve Wozniak au fondat Apple jucându-se împreună în garajul lor.

La fel cum Apple a devenit o companie profitabilă cu drepturi depline, simplul factorial, !, a devenit atomul unui întreg domeniu al matematicii: combinatorica.

Să lăsăm totul baltă, să începem să gândim de jos în sus.

Primul caz de utilizare interesant cunoscut a venit de la biserici în secolul al XVII-lea.

V-ați întrebat cum se trag clopotele în biserici? Există o mașină care le „sună” în ordine. S-a trecut la mașini pentru că clopotele sunt prea mari. De asemenea, sunt tone de clopote.

Cum și-au dat seama oamenii care este cea mai bună succesiune în care să le sune? Ce se întâmpla dacă voiau să schimbe lucrurile? Cum puteau găsi cel mai bun sunet? Fiecare turn de clopote avea până la 16 clopote!

Nu puteai schimba cât de repede puteai să suni un clopot – mașinile sunau doar un clopot la fiecare secundă. Singurul lucru pe care îl puteai face era să schimbi ordinea clopotelor. Așadar, această probă consta în a afla cea mai bună ordine.

Am putea, pe parcurs, să aflăm și toate ordinele posibile? Vrem să știm toate ordinele posibile pentru a ne da seama dacă merită să le încercăm pe toate.

Un clopotar, Fabian Stedman a acceptat această provocare.

A început cu 2 clopote. Care sunt diferitele ordini în care ar putea suna aceste clopote?

1 și 2.
sau
2 și 1.

Aceasta avea sens. Nu exista o altă cale.

Ce zici de 3 clopote?

1, 2 și 3.
1, 3 și 2.

Apoi, începând cu al doilea clopot,

2, 1 și 3.
2, 3 și 1.

Apoi, începând cu al treilea clopot,

3, 1 și 2.
3, 2, și 1.

Total, 6.

Apoi și-a dat seama că acest lucru era foarte asemănător cu două clopote!

Dacă a fixat primul clopot, atunci numărul de moduri de a ordona celelalte două clopote rămase era întotdeauna două.

Câte moduri ar putea fixa primul clopot? Oricare dintre cele 3 clopote putea fi acela!

Bine, a continuat el. A ajuns apoi la 5 clopote.

Acesta este momentul în care și-a dat seama că a face lucrurile de mână este greoi. Ai doar atât timp în zi, trebuie să suni clopote, nu poți să te blochezi desenând toate clopotele posibile. Exista o modalitate de a rezolva rapid acest lucru?

El s-a întors la intuiția sa.

Dacă avea 5 clopote, și a reparat primul clopot, tot ce trebuia să facă era să-și dea seama cum să comande 4 clopote.

Pentru 4 clopote? Ei bine, dacă avea 4 clopote și a reparat primul clopot, tot ce trebuia să facă era să se gândească cum să comande 3 clopote.

Și știa cum să facă asta!

Deci, ordonarea a 5 clopote = 5 * ordonarea a 4 clopote.

Ordonarea a 4 clopote = 4 * ordonarea a 3 clopote

Ordonarea a 3 clopote = 3 * ordonarea a 2 clopote.

… Vedeți tiparul, nu-i așa?

Fun Fact: Aceasta este cheia pentru o tehnică de programare numită recursivitate.

Așa a făcut și el. Deși i-a luat mult mai mult timp, deoarece nimeni din apropierea lui nu descoperise deja acest lucru.

Așa, el și-a dat seama că ordonarea a 5 clopote = 5 * 4 * 3 * 2 * 1.

Această formulă de ordonare, în 1808, a ajuns să fie cunoscută sub numele de factorială.

Noi ne gândim la notația factorială ca fiind baza, dar ideea a existat cu mult înainte de a avea un nume. Abia când matematicianul francez Christian Kramp a observat că era folosită în câteva locuri, a numit-o factorială.

Această ordonare a clopotelor se numește permutare.

O permutare este o ordonare a elementelor.

Când înveți ceva, cred că ajută să privești lucrurile din toate unghiurile diferite, pentru a consolida înțelegerea.

Ce-ar fi dacă am încerca să obținem direct formula de mai sus, fără a încerca să reducem problema la un număr mai mic de clopote?
Avem 5 spații, corect?

În câte moduri putem alege primul clopot? 5, pentru că acesta este numărul de clopote pe care îl avem.

Cel de-al doilea clopot? Ei bine, am folosit un clopot când l-am pus în prima poziție, așa că ne-au mai rămas 4 clopote.

Cel de-al treilea clopot? Ei bine, le-am ales pe primele două, așa că au mai rămas doar 3 clopote din care să alegem.

Cele de-al patrulea clopot? Au mai rămas doar 2 clopote, deci 2 opțiuni.
Cel de-al cincilea clopot? A mai rămas doar 1 singur clopot, deci 1 opțiune.

Și iată că numărul total de comenzi este 5 * 4 * 3 * 2 * 1

Atunci, avem prima noastră formulă generală.

Numărul de moduri de a comanda N elemente este N!

Acum, ne confruntăm cu o problemă diferită. Regele a ordonat să se facă clopote noi pentru fiecare biserică. Unele sunt frumoase, altele sunt ok, altele te vor face să surzești. Dar fiecare dintre ele este unic. Fiecare face un sunet propriu. Un clopot asurzitor înconjurat de clopote frumoase poate suna maiestuos.

Dar, în clopotnița noastră încă mai încap 5 clopote, așa că trebuie să ne dăm seama care este cea mai bună comandă din cele 8 clopote pe care le-au făcut clopotarii pricepuți.

Utilizând logica de mai sus, putem proceda.

Pentru primul clopot, putem alege oricare dintre cele 8 clopote.

Pentru al doilea clopot, putem alege oricare dintre cele 7 clopote rămase… și așa mai departe.

În final, obținem 8 * 7 * 6 * 5 * 4ordonări posibile ale celor 8 clopote în 5 spații.

Dacă sunteți familiarizați cu varianta de formulă a lui (n P r), care este n! / (n-r)!, nu vă faceți griji, o vom deduce și pe aceasta destul de curând!

Un mod greșit de a o deriva este de a înmulți atât numitorul cât și numitorul cu 3! în exemplul nostru de mai sus –

obținem 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.

Dar acest lucru nu ne ajută să înțelegem de ce funcționează această formulă. Înainte de a ajunge acolo, să aruncăm o privire la alegerea lucrurilor, sau la Combinație.

Combinația

Acum că știm cum să ordonăm lucrurile, ne putem da seama cum să alegem lucrurile!

Să luăm în considerare aceeași problemă. Există o clopotniță cu 5 clopote, iar tu ai 8 clopote. Cu toate acestea, în acest moment, nu vreți să vă dați seama de ordinea clopotelor (amintiți-vă că asta este o permutare).

În schimb, vreți să alegeți cele mai bune 5 clopote și să lăsați pe altcineva cu gusturi muzicale mai bune să-și dea seama de ordinea lor. De fapt, descompunem problema în două părți: În primul rând, ne dăm seama ce clopote să alegem. Apoi, ne dăm seama cum să ordonăm clopotele alese.

Cum se aleg clopotele? Aceasta este „combinația” din permutări și combinații.

Combinația este o selecție. Tu ești selectiv. Alegi 5 clopote din cele 8 pe care le-au făcut meșterii tăi.

Din moment ce știm cum să comandăm clopotele, vom folosi aceste informații pentru a ne da seama cum să alegem clopotele. Sună imposibil? Așteptați să vedeți frumoasa matematică implicată.

Să ne imaginăm că toate clopotele sunt în linie.

Înainte de a găsi toate modurile de a alege clopotele, să ne concentrăm asupra unui singur mod de a alege clopotele.

Un mod este de a alege oricare 5 la întâmplare. Acest lucru nu ne ajută prea mult să rezolvăm problema, așa că să încercăm un alt mod.

Punem clopotele în linie și le alegem pe primele 5. Acesta este un mod de a alege clopotele.

Observați că, chiar dacă schimbăm pozițiile primelor 5 clopote, alegerea nu se schimbă. Sunt în continuare același mod unic de a alege 5 clopote unice.

Acest lucru este valabil și pentru ultimele trei clopote.

Acum, frumosul truc matematic – pentru acest mod unic de a alege cele 5 clopote, care sunt toate ordonările celor 8 clopote în care alegem exact aceste 5 clopote? Din imaginea de mai sus, sunt toate ordonările celor 5 clopote (5!) și toate ordonările celor trei clopote rămase (3!).

Atunci, pentru fiecare mod unic de a alege 5 clopote, avem (5! * 3!) ordonări a 8 clopote.

Care sunt toate ordonările posibile ale celor 8 clopote? 8!.

Amintiți-vă, pentru fiecare alegere a primelor 5 clopote, avem (5! * 3!) ordonări de 8 clopote care dau aceeași alegere.

Atunci, dacă înmulțim numărul de moduri de alegere a primelor 5 clopote cu toate ordonările posibile ale unei singure alegeri, ar trebui să obținem numărul total de ordonări.

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

Deci,

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

În matematică, asta devine:

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

Iată că am găsit o explicație intuitivă pentru modul de alegere a 5 lucruri din 8.

Acum, putem generaliza acest lucru. Dacă avem N lucruri și vrem să alegem R dintre ele, înseamnă că tragem o linie la R.

Ceea ce înseamnă că elementele rămase vor fi N-R. Deci, pentru o alegere de R obiecte, avem R! * (N-R)! ordonări care dau aceleași R obiecte.

Pentru toate modurile de a alege R obiecte, avem N! / (R! * (N-R)!) posibilități.

Numărul de moduri de a alege r elemente din n este (n C r) = n! / (r! * (n-r)!)

În termeni colocviali, (n C r) se pronunță și n choose r, ceea ce ajută la consolidarea ideii că combinațiile sunt pentru a alege elemente.

Permutația – revizuită

Cu combinația făcută și spulberată, să ne întoarcem la partea a doua a lucrării noastre. Dragul nostru prieten a ales cele mai bune 5 clopote prin calcularea tuturor combinațiilor posibile de 5 clopote.

Este treaba noastră acum să găsim melodia perfectă prin calcularea numărului de ordonări.

Dar, aceasta este partea cea mai ușoară. Știm deja cum să comandăm 5 elemente. Este 5!, și am terminat.

Atunci, pentru a permuta (ordona) 5 elemente din 8, mai întâi alegem 5 elemente, apoi ordonăm cele 5 elemente.

Cu alte cuvinte,

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

Și dacă extindem formula, (8 P 5) = (8! / ( 5! * 3!)) * 5!

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

Și, am revenit complet la formula noastră inițială, derivată corect.

Numărul de moduri de a ordona r elemente din n este (n P r) = n! / (n-r)!

Diferența dintre permutare și combinație

Sper că acest lucru face ca diferența dintre permutări și combinații să fie foarte clară.

Permutările sunt ordonări, în timp ce combinațiile sunt alegeri.

Pentru a ordona N elemente, am găsit două moduri intuitive de a ne da seama de răspuns. Ambele conduc la răspunsul, N!.

Pentru a permuta 5 din 8 elemente, trebuie mai întâi să alegeți cele 5 elemente, apoi să le ordonați. Se alege folosind (8 C 5), apoi se ordonează cele 5 folosind 5!.

Și intuiția pentru a alege R din N este de a calcula toate ordonările (N!) și de a împărți cu ordonările în care primul R și ultimul N-R rămân aceleași (R! și (N-R)!).

Și, asta e tot ce există în materie de permutări și combinații.

Toate permutările și combinațiile avansate folosesc acest lucru ca bază. Combinație cu înlocuire? Aceeași idee. Permutare cu elemente identice? Aceeași idee, doar că numărul de ordonări se schimbă, deoarece unele elemente sunt identice.

Dacă vă interesează, putem trece la cazurile complexe într-un alt exemplu. Anunțați-mă pe Twitter.

Vezi mai multe articole pe blogul meu și înscrieți-vă în lista de discuții săptămânală.

Note de final

1. Acesta este modul în care îmi imaginez că și-a dat seama de lucruri. Nu o luați ca pe o lecție de istorie.
2. Indienii au avut, în secolul al XII-lea, cu 400 de ani înaintea lui.

.