Să vorbim despre una dintre secțiunile teoriei probabilității - combinatorice.
Combinatorics este o ramură a matematicii care studiază combinațiile și permutarea obiectelor. O altă combinatorie poate fi înțeleasă ca o căutare a opțiunilor posibile. Combinatoricii își au originea în secolul al XVII-lea. Pentru o lungă perioadă de timp se afla în afara mainstream-ului dezvoltării matematicii.
Cu provocările pe care a trebuit să aleagă anumite elemente, le aranja într-o anumită ordine și de căutare printre cele mai bune locații diferite, oamenii s-au confruntat chiar și în timpurile preistorice, alegerea cea mai bună poziție pentru vânători, războinici - în timpul luptei, unelte - în timpul funcționării .
Competențele combinatoriale au fost, de asemenea, utile în timpul orelor de relaxare. Nu putem spune cu siguranță că, împreună cu concurența în alergare, aruncarea de discuri, săriturile au apărut jocuri care impunea, în primul rând, capacitatea de a număra, de a face planuri și de a respinge planurile adversarului.
De-a lungul timpului, au fost diferite jocuri (table, cărți, dame, șah etc.). În fiecare dintre aceste jocuri, a trebuit să luăm în considerare diferite combinații de figuri, iar cel care le-a învățat mai bine a câștigat, a cunoscut combinațiile câștigătoare și a știut cum să evite pierderile. Nu numai jocurile de noroc au dat alimente pentru reflexiile combinatoriale ale matematicii. De mult timp, diplomații, încercând să păstreze secretul corespondenței, au inventat coduri complexe, iar serviciile secrete ale altor state au încercat să descopere aceste coduri. A început să folosească cipuri bazate pe principii combinatoriale, de exemplu, pe diverse permutări ale literelor, înlocuirea literelor utilizând cuvinte cheie etc.
Combinatorică ca știință a început să se dezvolte în secolul al 18-lea, în paralel cu apariția teoriei probabilității ca pentru a rezolva problemele de probabilitate a fost necesar pentru a contoriza numărul de diferite combinații de elemente. Primul studiu științific al combinatorică aparțin savantul italian Dzh.Kardano, N.Tartale (1499-1557), G.Galileyu (1564-1642) și de oamenii de știință din Franța B.Paskalyu (1623-1662) și Fermat.
Deci, produsul tuturor numerelor naturale de la 1 la n inclusiv este numit n-factorial și scrie: n! = 1 2 3 ... (n-1) n
Combinatorics rezolvă probleme legate de examinarea seturilor și compilarea diferitelor combinații de elemente ale acestor seturi. În funcție de regulile de compilare, se pot distinge trei tipuri de combinații: permutări, plasări, combinații.
Vom continua să funcționăm numai cu seturi care conțin un număr finit de elemente. În seturile infinite nu se aplică toate regulile și formulele de mai jos.
THEOREM 2.1. Fie ca seturile finite disjuncte să fie date. Apoi, puterea de a combina aceste seturi este egală cu suma puterilor acestor seturi:
Dovada acestei teoreme este evidentă. Dar suntem interesați de o altă interpretare a acestei teoreme, pe care o formulăm pentru două seturi.
Dacă un element poate fi selectat în moduri și un element în moduri și orice mod de selectare a unui element diferă de orice metodă de selectare a unui element, atunci alegerea "sau" se poate face în moduri. Această regulă se numește regula sumă.
Fie ca seturile finite disjuncte să fie date. Să denotăm numărul elementelor din aceste seturi (puterile lor). Luați în considerare produsul cartezian al acestor seturi. Reamintim că elementele acestui produs vor fi vectori (tupluri) de lungime a speciilor.
TEOREM 2.2. Numărul de elemente din produsul cartezian al seturilor este egal cu produsul puterii acestor seturi:
Ca și în cazul precedent, formulăm această teoremă într-un mod simplificat pentru două seturi. Dacă un element poate fi selectat în moduri și un element în moduri și orice mod de selectare a unui element diferă de orice metodă de selectare a unui element, atunci alegerea "și" (respectiv, perechi) poate fi făcută în moduri. Această regulă se numește regula produsului sau înmulțire.
Ambele reguli formulate sunt valabile pentru orice număr finit de seturi finite și, în forma corespunzătoare, sunt numite generalizate.
a) Există trei clase a cincea în școala secundară, respectiv 28, 31 și respectiv 26 de elevi. Este necesar să alegeți unul dintre ei pentru a participa la consiliul școlar. Câte moduri puteți alege?
Prin regula sumelor pe care le obținem.
b) În secțiunea de patinaj, sunt implicați 14 băieți și 18 fete. Câte moduri diferite de la copiii implicați în secțiune, puteți forma cupluri sportive.
Prin regula produsului, ajungem.
Definiția. Orice vector de lungime, compus din elemente ale unui element în care toate elementele sunt diferite, se numește plasare fără repetiții asupra elementelor. Numărul tuturor destinațiilor de plasare fără repetiții pe elemente ale acestora este notat și egal.
Exemplul 2. A cumpărat 12 cărți. Pe raft poți pune într-un rând exact 6 cărți. Câte moduri diferite pot fi făcute?
Vom lua în considerare diferite nu numai acele cazuri în care se iau cărți diferite, ci și când sunt plasate diferit pe un raft (într-o ordine diferită). Apoi vorbim despre permutarea a 6 din 12. Obținem :.
Luați în considerare un caz esențial diferit, și anume, atunci când elementele unui set în vectori pot fi repetate.
Definiția. Orice vector de lungime compus din elemente dintr-un set de elemente alcătuit din elemente în care toate elementele sunt diferite se numește o plasare cu repetări asupra elementelor de. Numărul tuturor destinațiilor de plasare cu repetări pe elemente ale lui este notat și egal.
Exemplul 3. Câte combinații pot apărea când sunt aruncate trei zaruri?
Fiecare zar este un cub, ale cărui fețe sunt reprezentate de la unu până la șase puncte. La fiecare aruncare, vom primi seturi de tipul în care - numărul de puncte a scăzut pe osul corespunzător. Vorbim despre permutări cu repetiții de 3 elemente din 6. Obținem :.
Notă. Evident, alocările fără repetiții sunt un caz special de plasări cu repetări.
Definiția. Orice vector de lungime compus din elemente dintr-un element în care toate elementele sunt diferite este numit permutare fără repetarea elementelor. Numărul tuturor permutărilor fără repetiții din elemente este notat și egal.
Din definiție și formulă este clar că permutările fără repetiții sunt un caz special de plasări fără repetiții, cu condiția ca acestea să fie efectuate.
Exemplul 4. Câte moduri diferite puteți pune 10 cărți diferite pe raft?
Aici, spre deosebire de exemplul 2, valoarea este doar ordinea distribuției cărților. Deci, vorbim despre permutarea a 10 elemente. Obținem :.
Să luăm în considerare cazul când elementele setului se repetă de mai multe ori. Pentru caracterul clar, lăsați elementul 1 să se repete o dată, elementul 2 - o dată și așa mai departe. Apoi, vectorii de lungime format din elementele unui set dat se numesc permutări ale elementelor cu repetări. Numărul acestor permutări este notat și egal.
Punând în următoarea formulă, obținem o formulă pentru permutări fără repetiții.
Exemplul 5. Câte numere de șase cifre pot fi scrise folosind cifrele 1, 2, 2, 2, 3, 3?
Există un set de șase cifre în care numărul 2 se repetă de trei ori, iar numărul 3 se repetă de două ori. Numerele obținute vor fi permutări cu repetări ale a 6 elemente. Obținem :.
În primul rând, observăm o diferență semnificativă între permutațiile din destinații de plasare. Dacă în alocări vectorii diferă atât în componența elementelor cât și în aranjamentul (ordinea) lor în set, atunci în permutări vectorii diferă numai în aranjamentul elementelor. Este firesc să se examineze cazul în care vectorii, dimpotrivă, diferă doar prin compoziția elementelor.
Definiția. Orice vectori de lungime diferite, compuși din elemente dintr-un set de elemente, care diferă într-un set de elemente, dar nu prin aranjarea lor într-un set, se numesc combinații de elemente de.
Dacă toate elementele care formează combinațiile sunt diferite, ele sunt numite combinații fără repetiții. Desemnarea tuturor combinațiilor fără repetare. Formula de calcul. Dacă unele (sau toate) elementele care formează combinații pot fi repetate, ele sunt numite combinații de repetiții. Desemnarea tuturor combinațiilor fără repetare. Formula de calcul. Amintiți-vă că ultima formulă nu este necesară.
Observație 1. Combinațiile reprezintă un caz special de plasare. Diferența dintre combinații și destinații de plasare din definiție nu este evidentă, dar este ușor de văzut cu exemple concrete. De exemplu, vectorii sunt aranjamente diferite, dar denotă aceeași combinație.
Observația 2. Pentru combinațiile fără repetiții, o cerință este neapărat, iar în cazul egalității obținem un rezultat natural. Dar pentru combinațiile cu repetiții această cerință nu este necesară, așa cum se va vedea din exemplul de mai jos.
a) În departament există 10 angajați. Este necesar să selectați trei dintre ei pentru a le trimite într-o călătorie de afaceri. Câte moduri puteți face acest lucru?
Deoarece contează numai acei angajați selectați, atunci vorbim de combinații fără repetiții de 3 elemente din 10. Obținem:
b) În magazinul de flori sunt disponibile pentru vânzare 5 tipuri diferite de flori. Cumparatorul trebuie sa faca un buchet de 7 culori. Câte moduri puteți face acest lucru?
Vom lua în considerare diferitele buchete care diferă una de alta în alegerea culorilor. Deoarece florile din buchet pot fi repetate, atunci vorbim de combinații cu repetiții de 7 elemente din 5. Apoi vom ajunge.
Unul dintre cele mai cunoscute exemple de utilizare a formulelor combinatoriale este așa-numitul binomial Newton. În forma generală, formula binomială Newton (binomial) arată astfel:
Cu cazuri speciale de aplicare a acestei formule (pentru cazuri și) se ciocnesc în școală atunci când studiază formule de multiplicare prescurtată:
În practică, pentru folosire, binomul Newton folosește așa-numitul triunghi Pascal, care conține coeficienții numerici ai polinomului din partea dreaptă a formulei: