Acest articol se va concentra pe o secțiune specială de matematică numită combinatorică. Formule, reguli, exemple de rezolvare a problemelor - toate acestea le puteți găsi aici citind articolul până la capăt.
Deci, ce este această secțiune? Combinatoria se ocupă de problema numărării oricăror obiecte. Dar în acest caz, obiectele nu sunt prune, pere sau mere, ci altceva. Combinatoria ne ajută să găsim probabilitatea unui eveniment. De exemplu, când se joacă cărți, care este probabilitatea ca adversarul să aibă un atu? Sau un astfel de exemplu - care este probabilitatea ca să obțineți exact alb dintr-o pungă de douăzeci de bile? Pentru acest tip de sarcini trebuie să cunoaștem cel puțin elementele de bază ale acestei secțiuni de matematică.
Configurații combinate
Având în vedere problema conceptelor și formulelor de bază ale combinatoriei, nu putem decât să acordăm atenție configurațiilor combinatorii. Ele sunt folosite nu numai pentru formulare, ci și pentru rezolvarea diferitelor probleme combinatorii. Exemple de astfel de modele sunt:
- plasament;
- permutare;
- combinație;
- compoziția numărului;
- număr împărțit.
Vom vorbi despre primele trei mai în detaliu mai târziu, dar vom acorda atenție compoziției și împărțirii în această secțiune. Când vorbesc despre compoziția unui anumit număr (să zicem, a), se referă la reprezentarea numărului a ca o sumă ordonată a unor numere pozitive. Și o împărțire este o sumă neordonată.
Secțiuni
Înainte de a trece direct la formulele combinatoriei și la luarea în considerare a problemelor, merită să acordăm atenție faptului că combinatoria, ca și alte secțiuni ale matematicii, are propriile subsecțiuni. Acestea includ:
- enumerativ;
- structural;
- extreme;
- Teoria Ramsey;
- probabilistic;
- topologic;
- infinit.
În primul caz, vorbim de combinatorică enumerativă, problemele au în vedere enumerarea sau numărarea diferitelor configurații care sunt formate din elemente de mulțimi. De regulă, asupra acestor seturi sunt impuse unele restricții (diferențiere, indistinguire, posibilitatea de repetare etc.). Iar numărul acestor configurații se calculează folosind regula adunării sau înmulțirii, despre care vom vorbi puțin mai târziu. Combinatoria structurală include teoriile graficelor și matroidelor. Un exemplu de problemă de combinatorică extremă este care este cea mai mare dimensiune a unui graf care satisface următoarele proprietăți… În al patrulea paragraf, am menționat teoria Ramsey, care studiază prezența structurilor regulate în configurații aleatorii. Probabilisticăcombinatoria este capabilă să răspundă la întrebarea - care este probabilitatea ca o mulțime dată să aibă o anumită proprietate. După cum ați putea ghici, combinatoria topologică aplică metode în topologie. Și, în sfârșit, al șaptelea punct - combinatoria infinită studiază aplicarea metodelor combinatorice la mulțimi infinite.
Regulă de adăugare
Printre formulele de combinatorie se găsesc unele destul de simple, cu care suntem familiarizați de mult. Un exemplu este regula sumei. Să presupunem că ni se dau două acțiuni (C și E), dacă se exclud reciproc, acțiunea C poate fi efectuată în mai multe moduri (de exemplu, a), iar acțiunea E poate fi efectuată în moduri b, atunci oricare dintre ele (C sau E) se poate face în moduri a + b.
În teorie, acest lucru este destul de greu de înțeles, vom încerca să transmitem întreaga idee cu un exemplu simplu. Să luăm numărul mediu de elevi dintr-o clasă - să spunem că este douăzeci și cinci. Printre ei se numără cincisprezece fete și zece băieți. Un însoțitor este repartizat în clasă zilnic. Câte moduri există de a desemna un însoțitor de clasă astăzi? Soluția problemei este destul de simplă, vom recurge la regula adunării. Textul sarcinii nu spune că numai băieții sau doar fetele pot fi de serviciu. Prin urmare, ar putea fi oricare dintre cele cincisprezece fete sau oricare dintre cei zece băieți. Aplicând regula sumei, obținem un exemplu destul de simplu căruia un elev de școală primară îl poate face față cu ușurință: 15 + 10. După ce am calculat, obținem răspunsul: douăzeci și cinci. Adică, există doar douăzeci și cinci de moduriatribuiți o clasă de serviciu pentru astăzi.
Regulă de înmulțire
Regula înmulțirii aparține și formulelor de bază ale combinatoriei. Să începem cu teorie. Să presupunem că trebuie să efectuăm mai multe acțiuni (a): prima acțiune este efectuată în 1 moduri, a doua - în 2 moduri, a treia - în 3 moduri, și așa mai departe până când ultima a-acțiune este efectuată în acele moduri. Atunci toate aceste acțiuni (dintre care avem un total) pot fi efectuate în N moduri. Cum se calculează N necunoscut? Formula ne va ajuta cu aceasta: N \u003d c1c2c3…ca.
Din nou, nimic nu este clar în teorie, să trecem la un exemplu simplu de aplicare a regulii înmulțirii. Să luăm aceeași clasă de douăzeci și cinci de oameni, în care învață cincisprezece fete și zece băieți. Doar că de data aceasta trebuie să alegem doi însoțitori. Pot fi fie doar băieți, fie fete, fie un băiat cu o fată. Ne întoarcem la soluția elementară a problemei. Alegem primul însoțitor, așa cum am decis în ultimul paragraf, avem douăzeci și cinci de opțiuni posibile. A doua persoană de serviciu poate fi oricare dintre persoanele rămase. Am avut douăzeci și cinci de studenți, am ales unul, ceea ce înseamnă că oricare dintre cei douăzeci și patru de oameni rămași poate fi al doilea de serviciu. În cele din urmă, aplicăm regula înmulțirii și constatăm că cei doi însoțitori pot fi aleși în șase sute de moduri. Am obținut acest număr înmulțind douăzeci și cinci și douăzeci și patru.
Schimbare
Acum vom lua în considerare încă o formulă combinatorică. În această secțiune a articolului, noiSă vorbim despre permutări. Luați în considerare problema imediat cu un exemplu. Să luăm bile de biliard, avem numărul al n-a dintre ele. Trebuie să calculăm: câte opțiuni există pentru a le aranja pe rând, adică pentru a face un set ordonat.
Să începem, dacă nu avem bile, atunci avem și opțiuni de plasare zero. Și dacă avem o minge, atunci aranjamentul este și el același (matematic, aceasta poate fi scrisă astfel: Р1=1). Două bile pot fi aranjate în două moduri diferite: 1, 2 și 2, 1. Prin urmare, Р2=2. Trei bile pot fi aranjate în șase moduri (Р3=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, ci zece sau cincisprezece? A enumera toate opțiunile posibile este foarte lung, atunci combinatoria ne vine în ajutor. Formula de permutare ne va ajuta să găsim răspunsul la întrebarea noastră. Pn=nP(n-1). Dacă încercăm să simplificăm formula, obținem: Pn=n (n - 1) … 21. Și acesta este produsul primelor numere naturale. Un astfel de număr se numește factorial și este notat cu n!
Să luăm în considerare problema. Conducătorul în fiecare dimineață își construiește detașamentul într-o linie (douăzeci de oameni). În detașament sunt trei cei mai buni prieteni - Kostya, Sasha și Lesha. Care este probabilitatea ca ei să fie unul lângă altul? Pentru a găsi răspunsul la întrebare, trebuie să împărțiți probabilitatea unui rezultat „bun” la numărul total de rezultate. Numărul total de permutări este de 20!=2,5 chintilioane. Cum să numărăm numărul de rezultate „bune”? Să presupunem că Kostya, Sasha și Lesha sunt un singur supraom. Atunci noiAvem 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 triplul lor indivizibil, iar acesta este încă 3!=6 opțiuni. Deci avem 18 constelații „bune” în total! 3! Trebuie doar să găsim probabilitatea dorită: (18!3!) / 20! Care este aproximativ 0,016. Dacă este convertit într-un procent, se dovedește a fi doar 1,6%.
Cazare
Acum vom lua în considerare o altă formulă de combinatorie foarte importantă și necesară. Cazarea este următoarea noastră problemă, pe care vă sugerăm să o luați în considerare în această secțiune a articolului. Ne vom complica mai mult. Să presupunem că vrem să luăm în considerare posibile permutări, numai că nu din întreaga mulțime (n), ci din una mai mică (m). Adică, luăm în considerare permutările a n articole cu m.
Formulele de bază ale combinatoriei nu trebuie doar memorate, ci înțelese. Chiar și în ciuda faptului că devin mai complicate, deoarece nu avem un parametru, ci doi. Să presupunem că m \u003d 1, apoi A \u003d 1, m \u003d 2, apoi A \u003d n(n - 1). Dacă simplificăm și mai mult formula și trecem la notație folosind factoriali, obținem o formulă destul de concisă: A \u003d n! / (n - m)!
Combinație
Am luat în considerare aproape toate formulele de bază ale combinatoriei cu exemple. Acum să trecem la etapa finală de luare în considerare a cursului de bază al combinatoriei - cunoașterea combinației. Acum vom alege m articole din cele n pe care le avem, în timp ce le vom alege pe toate în toate modurile posibile. Prin ce se deosebește acest lucru de cazare? Nu vomluați în considerare ordinea. Acest set neordonat va fi o combinație.
Introduceți imediat notația: C. Luăm plasări de m bile din n. Încetăm să fim atenți la comandă și obținem combinații repetate. Pentru a obține numărul de combinații, trebuie să împărțim numărul de plasări la m! (m factorial). Adică, C \u003d A / m! Astfel, există câteva moduri de a alege dintre n bile, aproximativ egale cu câte să alegi aproape totul. Există o expresie logică pentru aceasta: a alege puțin este la fel cu a arunca aproape totul. De asemenea, este important să menționăm în acest moment că numărul maxim de combinații poate fi atins atunci când încercați să selectați jumătate dintre articole.
Cum să alegi o formulă pentru a rezolva o problemă?
Am examinat în detaliu formulele de bază ale combinatoriei: plasare, permutare și combinare. Acum sarcina noastră este să facilităm alegerea formulei necesare pentru rezolvarea problemei în combinatorică. Puteți folosi următoarea schemă destul de simplă:
- Întrebați-vă: este luată în considerare ordinea elementelor în textul problemei?
- Dacă răspunsul este nu, atunci utilizați formula de combinație (C=n! / (m!(n - m)!)).
- Dacă răspunsul este nu, atunci trebuie să mai răspunzi la o întrebare: toate elementele sunt incluse în combinație?
- Dacă răspunsul este da, atunci utilizați formula de permutare (P=n!).
- Dacă răspunsul este nu, atunci utilizați formula de alocare (A=n! / (n - m)!).
Exemplu
Am luat în considerare elementele de combinatorie, formule și alte câteva probleme. Acum să trecem laavând în vedere o problemă reală. Imaginează-ți că ai în față un kiwi, o portocală și o banană.
Întrebarea unu: în câte moduri pot fi rearanjate? Pentru a face acest lucru, folosim formula de permutare: P=3!=6 moduri.
Întrebarea a doua: în câte moduri poate fi ales un fruct? Acest lucru este evident, avem doar trei opțiuni - alegeți kiwi, portocală sau banană, dar aplicăm formula de combinație: C \u003d 3! / (2!1!)=3.
Întrebarea trei: în câte moduri pot fi alese două fructe? Ce optiuni avem? Kiwi si portocala; kiwi și banane; portocala si banana. Adică, trei opțiuni, dar acest lucru este ușor de verificat folosind formula de combinație: C \u003d 3! / (1!2!)=3
Întrebarea patru: în câte moduri pot fi alese trei fructe? După cum puteți vedea, există o singură modalitate de a alege trei fructe: luați un kiwi, o portocală și o banană. C=3! / (0!3!)=1.
Întrebarea cinci: în câte moduri poți alege cel puțin un fruct? Această condiție implică faptul că putem lua unul, două sau toate cele trei fructe. Prin urmare, adăugăm C1 + C2 + C3=3 + 3 + 1=7. Adică avem șapte moduri de a lua cel puțin o bucată de fruct de pe masă.
