Formulele de bază ale combinatoricii. Combinatorics: formula pentru permutare, plasare

În acest articol vom discuta o secțiune specială de matematică numită combinatorică. Formule, reguli, exemple de rezolvare a problemelor - toate acestea găsiți aici, după citirea articolului până la sfârșitul lui.

Deci, ce este această secțiune? Combinatorics se ocupă de chestiunea numărării oricăror obiecte. Dar în acest caz obiectele nu sunt prune, pere sau mere, ci altceva. Combinatorics ne ajută să găsim probabilitatea unui eveniment. De exemplu, atunci când joci cărți - care este probabilitatea că adversarul are un atu? Sau un exemplu - care este probabilitatea că veți primi o pungă albă dintr-o pungă cu douăzeci de bile? Pentru astfel de probleme este necesar să cunoaștem cel puțin elementele de bază ale acestei secțiuni a matematicii.

Combinatoriale configurații

Având în vedere problema conceptelor de bază și formulelor combinatorice, nu putem decât să acordăm atenție configurațiilor combinatoriale. Ele sunt folosite nu numai pentru formulare, ci și pentru rezolvarea diferitelor probleme combinatoriale. Exemple de astfel de modele sunt:

• cazare;
• permutare;
• combinație;
• compoziția numărului;
• împărțirea numărului.

Despre primele trei, vom vorbi mai în detaliu mai târziu, dar vom acorda atenție compozițiilor și partiționării în această secțiune. Atunci când se vorbește despre o compoziție de un anumit număr (de exemplu, a), atunci înțelegem reprezentarea numărului a sub formă de sumă ordonată de anumite numere pozitive. Divizarea este o sumă neordonată.

secţiuni

Înainte de a merge direct la formulele combinatorice și luarea în considerare a problemelor, merită acordată atenția faptului că combinatoriile, ca și alte ramuri ale matematicii, au propriile subsecțiuni. Acestea includ:

• enumerativă;
• structurale;
• extreme;
• Teoria lui Ramsey;
• probabilitate;
• topologice;
• infinitului.

În primul caz vorbim despre calculul combinatoricii, problemele iau în considerare enumerarea sau numărarea diferitelor configurații care sunt formate din elementele seturilor. De regulă, se impun restricții asupra acestor seturi (distinctivitate, indiscutabilitate, posibilitatea repetării și așa mai departe). Iar numărul acestor configurații se calculează folosind regula adunării sau multiplicării, despre care vom vorbi puțin mai târziu. Teoriile grafurilor și matroidelor sunt combinatorice structurale. Un exemplu de problema combinatorică extreme - ceea ce este cea mai mare dimensiune a graficului, care satisface următoarea svoystvamhellip- În al patrulea paragraf am menționat teoria Ramsay, care studiază în prezența unor configurații aleatorii ale structurilor regulate. Combinatoria probabilistă este capabilă să răspundă la întrebarea - care este probabilitatea ca un anumit set să aibă o anumită proprietate. Nu este greu de ghicit că o combinatorică topologică aplică metode în topologie. Și, în sfârșit, al șaptelea punct - combinatoria infinitară - studiază aplicarea metodelor combinatoriale în seturi infinite.

Regula de adăugare

Printre formulele combinatorice se găsesc cele destul de simple, cu care am fost mult timp familiarizați. Un exemplu este regula valorii. Să presupunem că avem două etape (C și E), în cazul în care se exclud reciproc, în vigoare din greu de realizat în mai multe moduri (de exemplu, a), iar efectul E greu de realizat b-moduri, pentru a se conforma cu oricare dintre ele (C sau E) pot fi un + b moduri .

În teorie, acest lucru este greu de înțeles, încercăm să transmitem întregul punct pe un exemplu simplu. Să luăm numărul mediu de elevi dintr-o clasă - să zicem, douăzeci și cinci. Printre ele sunt cincisprezece fete și zece băieți. În fiecare zi în clasă i se atribuie o persoană la datorie. Câte moduri există pentru a numi un ofițer de serviciu astăzi? Soluția problemei este destul de simplă, recurgem la regula de adăugare. Textul problemei nu spune că doar băieți sau fete pot fi la datorie. În consecință, pot fi oricare dintre cincisprezece fete sau oricare dintre cei zece băieți. Aplicând regula sumelor, primim un exemplu destul de simplu, cu care studentul școlii elementare poate face față cu ușurință: 15 + 10. După numărare, primim răspunsul: douăzeci și cinci. Adică, există doar douăzeci și cinci de modalități de a numi o clasă de serviciu pentru ziua de azi.

Regula de multiplicare

Regula de multiplicare se aplică formulelor de bază ale combinatoricii. Să începem cu teoria. De exemplu, trebuie să efectuăm mai multe acțiuni (a): prima acțiune este efectuată în 1 mod, al doilea în căi c2, al treilea cu metode c3 și așa mai departe până la ultima acțiune a efectuată în același mod. Apoi, toate aceste acțiuni (despre care avem toți a) pot fi realizate în mod N. Cum de a calcula N necunoscut? În acest lucru vom fi ajutați de formula: N = c1 * c2 * c3 * hellip- * sa.

Din nou, în teorie nimic nu este clar, ne îndreptăm spre un exemplu simplu de aplicare a regulii de multiplicare. Să luăm aceeași clasă de douăzeci și cinci de oameni, în care cincisprezece fete și zece băieți studiază. Numai de data asta avem nevoie să alegem doi oameni la datorie. Ele pot fi de îndată ce sunt băieți sau fete și un băiat cu o fată. Trecem la rezolvarea elementară a problemei. Alegem prima persoană la datorie, așa cum am decis în ultimul paragraf, obținem douăzeci și cinci de opțiuni posibile. A doua persoană de serviciu poate fi oricare dintre oamenii rămași. Aveam douăzeci și cinci de studenți, cel pe care l-am ales, astfel încât a doua persoană aflată la datorie ar putea fi oricare dintre celelalte douăzeci și patru de persoane. În cele din urmă, aplicăm regula de multiplicare și constatăm că doi oameni aflați la datorie pot fi aleși în șase sute de moduri. Am înmulțit acest număr cu douăzeci și cinci și douăzeci și patru.

permutare

Acum vom lua în considerare o altă formulă combinatorică. În această secțiune a articolului vom vorbi despre permutări. Luați în considerare imediat problema cu un exemplu. Ia bile de biliard avem numărul lor n. Trebuie să calculați: câte opțiuni există pentru a le aranja într-un rând, adică pentru a compune un set ordonat.

Să începem, dacă nu avem bile, atunci avem aceleași variante ale aranjamentului ca și zero. Și dacă avem o minge, atunci aranjamentul este același (matematic, acesta poate fi scris astfel: P1 = 1). Două bile pot fi plasate în două moduri diferite: 1,2 și 2,1. Prin urmare, P2 = 2. Trei sfere pot fi aranjate în șase moduri (P3 = 6): 1,2,3-1,3,2-2,1,3-2,3,1-3,2,1-3 , 1.2. Și dacă nu sunt trei astfel de bile, dar zece sau cincisprezece? Enumerați toate opțiunile posibile pentru o perioadă lungă de timp, apoi ajungem la combinatorii de salvare. Formula de permutare ne va ajuta să găsim răspunsul la întrebarea care ne interesează. Pn = n * P (n-1). Dacă încercăm să simplificăm formula, obținem: Pn = n * (n-1) * hellip- * 2 * 1. Și acesta este produsul primelor numere naturale. Un astfel de număr este numit factorial și este notat ca n!

Luați în considerare problema. Conducătorul în fiecare dimineață își construiește echipajul într-o linie (douăzeci de persoane). Detașamentul are trei prieteni cei mai buni - Kostya, Sasha și Lesha. Care este probabilitatea ca ei să stea alături? Pentru a găsi răspunsul la întrebare, probabilitatea unui rezultat "bun" ar trebui împărțită în numărul total de rezultate. Numărul total de permutări este de 20! = 2,5 chintilion. Cum se calculează numărul de rezultate "bune"? Să presupunem că Kostya, Sasha și Lesha sunt un superman. Apoi avem doar optsprezece subiecte. Numărul de permutări în acest caz este 18 = 6,5 cvadrilioane. Cu toate acestea, Kostya, Sasha și Lesha se pot mișca în mod arbitrar între ei în trei, indivizibile, iar acesta este 3! = 6 opțiuni. Așadar, avem doar 18 aranjamente "bune"! * 3! Putem găsi doar probabilitatea necesară: (18! * 3!) / 20! Care este egal cu aproximativ 0,016. Dacă traduceți într-un procent, atunci se dovedește doar 1,6%.

plasare

Acum vom lua în considerare o altă formulă foarte importantă și necesară a combinatoricii. Plasarea este următoarea întrebare, pe care o sugerăm să o luați în considerare în această secțiune a articolului. Vom complica lucrurile. Să presupunem că vrem să luăm în considerare posibile permutări, numai nu din întregul set (n), ci din cel mai mic (m). Asta este, considerăm permutările n de obiecte în m.

Formulele de bază ale combinatoricii nu sunt doar de a învăța, ci de a le înțelege. Chiar și în ciuda faptului că sunt complicate, pentru că nu avem un parametru, ci două. Să presupunem că m = 1, atunci A = 1, m = 2, atunci A = n * (n - 1). Dacă vom simplifica mai mult formula și vom merge la înregistrare cu ajutorul factorialiilor, vom obține o formulă complet concisă: A = n! / (n-m)!

combinație

Am luat în considerare aproape toate formulele de bază ale combinatoricii cu exemple. Acum vom trece la etapa finală de examinare a cursului de bază al combinatoricii - cunoașterea combinației. Acum vom alege m elemente de la n existente, în timp ce vom alege totul prin toate mijloacele posibile. Care este atunci diferența de plasare? Nu vom lua în considerare ordinea. Acest set neordonat va fi o combinație.

Imediat introducem notația: C. Luăm plasarea de bile de m. Nu mai acordăm atenție ordinului și obținem combinații repetate. Pentru a obține numărul de combinații, trebuie să împărțim numărul de destinații de plasare cu m! (factorial m). Aceasta este, C = A / m! Astfel, modurile de a alege de la n bile un pic, este la fel de mult ca alegerea aproape totul. Aceasta este o expresie logică: să alegi puțin, oricum, pentru a arunca aproape totul. Chiar și în acest paragraf este important să menționăm că numărul maxim de combinații poate fi atins atunci când încercați să selectați jumătate din elemente.

Cum de a alege o formulă pentru rezolvarea unei probleme?

Am examinat în detaliu formulele de bază ale combinatoricii: plasarea, permutarea și combinația. Acum sarcina noastră este de a facilita alegerea formulei necesare pentru rezolvarea problemei combinatoricii. Putem folosi următoarea schemă simplă:

1. Întrebați-vă întrebarea: ordinea plasării elementelor este luată în considerare în textul sarcinii?
2. Dacă răspunsul este negativ, utilizați formula combinație (C = n! / (M! * (N - m)!)).
3. Dacă nu există un răspuns, atunci este necesar să răspundeți la o altă întrebare: sunt toate elementele incluse în combinație?
4. Dacă răspunsul este da, utilizați formula de permutare (P = n!).
5. Dacă răspunsul este negativ, utilizați formula de plasare (A = n! / (N - m)!).

exemplu

Am examinat elementele combinatorice, formulele și alte întrebări. Acum ne îndreptăm spre adevărata problemă. Imaginați-vă că înainte de a vă stabili kiwi, portocali și banane.

Prima întrebare: câte moduri pot fi rearanjate? Pentru a face acest lucru, vom folosi formula de permutare: P = 3! = 6 moduri.

Întrebarea a doua: câte moduri pot alege un fruct? Acest lucru este evident, avem doar trei optiuni - sa alegem kiwi, portocala sau banana, dar sa aplicam formula de combinatii: C = 3! / (2! * 1!) = 3.

Întrebarea a treia: câte moduri puteți alege două fructe? Ce opțiuni avem în general? Kiwi și kiwi portocalii și banane-portocaliu și banane. Aceasta este, trei opțiuni, dar este ușor să verificați folosind formula combinație: C = 3! / (1! * 2!) = 3

Întrebarea a patra: câte moduri puteți alege trei fructe? Aparent, puteți alege trei fructe într-un fel: luați kiwi, portocale și banane. C = 3! / (0! * 3!) = 1.

Întrebarea a cincea: câte moduri pot alege cel puțin un fruct? Această condiție implică faptul că putem lua unul, două sau toate cele trei fructe. De aceea, adaugam C1 + C2 + C3 = 3 + 3 + 1 = 7. Cu alte cuvinte, avem șapte modalități de a lua de pe masa cel puțin o bucată de fruct.