Subiect 2. ELEMENTE DE COMBINARE
Obiectivele și obiectivele studierii subiectului
În acest subiect sunt avute în vedere principiile combinatorice și algoritmii de generare a obiectelor combinatoriale.
Combinatorica este una dintre secțiunile de matematică discretă, care a dobândit o mare importanță în legătură cu utilizarea ei în teoria probabilităților, logica matematică, teoria numerelor, tehnologia informatică, cibernetica.
Dăm un exemplu de cea mai simplă problemă combinatorică. Lăsați orașul A în orașul B să ajungeți cu barca, trenul, autobuzul, avionul; de la orașul B până la orașul C - abur și autobuz. Câte moduri puteți face o călătorie pe traseul A - B - C?
Soluția. Evident, numărul de căi diferite de la A la C este 4 × 2 = 8, deoarece prin alegerea uneia dintre cele patru căi posibile de a călători de la A la B, avem două modalități posibile de a călători de la B la C.
Plecând de la aceste considerente, formulăm regula principală a combinatoricii - regula produsului.
Regula de lucru. Dacă o anumită alegere a lui A poate fi efectuată în moduri m și pentru fiecare dintre aceste metode o altă alegere a lui B poate fi efectuată în n moduri, atunci alegerea "A și B" în ordinea indicată poate fi efectuată în moduri m × n.
Această regulă poate fi generalizată după cum urmează.
Să i se solicite să efectueze acțiunile k unul câte unul. În cazul în care prima acțiune pentru a efectua mijloace n1, oa doua acțiune - căi n2, a treia cale - căile n3, și așa mai departe până la acțiunea k care pot fi efectuate moduri nk, atunci toate acțiunile k pot fi executate moduri n1 × n2 × n3 × ... × NK.
Când se calculează numărul de combinații diferite, se folosește și regula sumă.
Regula sumelor. Dacă o alegere a lui A poate fi realizată în m moduri și o alegere a lui B în alte moduri, atunci alegerea fie "A. sau B" poate fi efectuată în moduri m + n.
Norma sumă poate fi, de asemenea, generalizată la un număr arbitrar de acțiuni.
În secțiunea 1.1.1, a fost dată noțiunea de set. Vom defini un set finit S printr-o listă a elementelor sale: S = s1, s2, ..., sn>, unde s1, s2, ..., sn sunt elemente ale S (neapărat distincte).
Introducem conceptul de multiset. Un multiset este o uniune de obiecte neapărat diferite. Acesta poate fi considerat un set în care fiecărui element i se atribuie un întreg pozitiv numit multiplicitate.
Vom scrie un multiset S finit în următoarea formă:
Aici toate sunt distincte și ki este multiplicitatea lui si. Atunci cardinalitatea S este.
Acum ia în considerare câteva dintre obiectele combinatoriale.
Subseturile. Un set M este numit un subset al mulțimii S (notația M ÌS sau S ÉM; citiți M, S, S conține M) dacă și numai dacă orice element din setul M aparține setului S.
Teorema. Numărul de subseturi ale unui set n-element S este 2 n.
Dovada. Asociem cu fiecare subset M al setului S un set binar de lungime n conform următoarei reguli: si ÎM dacă și numai dacă cifra i este egală cu una. Numărul de seturi binare de lungime n. conform regulii produsului, este 2 × 2 × ... × 2 = 2 n. În consecință, numărul tuturor subseturilor unui set n-element este 2 n.
Permutări. O permutare este aranjamentul elementelor setului într-o anumită ordine.
Teorema. Numărul de permutări ale unui set n-element S. Numărul de modalități de ordonare este exprimat de formula Pn = n !.
Simbolul n. (n-factorial este citit) denotă produsul de numere naturale de la 1 la n: n! = 1 × 2 ×. × n. Se presupune că 0! = 1.
Dovada. Selectăm secvențial elementele setului S și le aranjăm într-o anumită ordine în n locuri. În primul rând, puteți pune oricare dintre elementele n. După ce primul loc este umplut, al doilea loc poate fi plasat oricare dintre celelalte elemente n -1, etc. Apoi, prin regula produsului, toate n locurile pot fi umplute cu n × (n -1) × (n -2) ×. × 2 × 1 = n. moduri. În consecință, setul n-element poate fi comandat în n moduri.
Destinație de plasare. Ordonate subseturi k-element ale unui set de elemente n sunt numite un aranjament de n elemente cu k.
Teorema. Numărul de locații de la n la k este dat de formula:
.
Dovada. Selectăm succesiv elementele k din setul n-element și le aranjăm într-o anumită ordine în locurile k. În primul rând, puteți pune oricare dintre elementele n, apoi al doilea - oricare dintre restul de n-1, etc. Conform regulii de producție, avem
.
Combinații. O combinație de elemente n peste k este un subset k-element al unui set de elemente n.
Teorema. Numărul de combinații de elemente n peste k este exprimat prin următoarea formulă:
.
Dovada. De la un set n-element, este posibil să se formeze diferite subseturi de elemente k-comandate. Fiecare subset k-element poate fi comandat în moduri Pk. Apoi, numărul de combinații de la n la k - numărul de subseturi k element neordonate ale setului n-element va fi egal cu
.
Pentru numărul unei combinații,
,
,
.
Ultima proprietate rezultă din teorema privind numărul de subseturi dintr-un set finit (explicați de ce).
Permutări cu repetări. O permutare cu repetări este dispunerea elementelor unui multiset într-o anumită ordine.
Teorema. Numărul de permutări cu repetiții pentru multiset este exprimat prin formula
,
Dovada 1. Luați în considerare o permutare a unui multiset și înlocuiți toate elementele identice în el prin diferite. Apoi, numărul de permutări diferite care pot fi alcătuite din permutația luată în considerare este k1! × k2! × ... × km !. După ce am făcut acest lucru pentru fiecare permutare, obținem n. permutări. Prin urmare,
Numărul Cn (k1, k2, ..., km) se numește coeficientul polinomial. Dăm o altă dovadă a acestei teoreme.
Dovada 2. Pentru a comanda o multiset este necesar să alegeți din locurile k1 locuri pentru elementul s1, care se poate face în moduri, apoi din n-k1 rămase locurile, alegeți k2 locuri pentru elementul s2. ce se poate face în moduri etc. Apoi, numărul de modalități de a comanda o mulțime de mulțimi S conform regulii de produs este (reamintind că 0! = 1)
.
Combinații cu repetări. Combinațiile de elemente m cu elemente n cu repetări sunt grupuri care conțin elemente n, fiecare element aparținând unuia dintre tipurile m.
Un exemplu. Dintre cele trei elemente (m = 3) a. b. c este posibil să se facă astfel de combinații pe două cu repetiții: aa. ab. Al. bb. bc. cc.
Teorema. Numărul de combinații diferite de elemente m peste n cu repetări este
.
Dovada. Fiecare combinație este complet determinată prin specificarea câtor elemente din fiecare dintre tipurile m sunt incluse în ea. Cu fiecare combină o secvență de zero-uri și cele compuse de regula ca un unități rând, ca elemente de primul tip este inclus în combinație, apoi setați la zero, și după mai multe unități de scriere, cât de multe elemente de al doilea tip cuprinde o combinație etc. . De exemplu, combinațiile de trei litere de două vor corespunde următoarelor secvențe:
1100, 1010, 1001, 0110, 0101, 0011.
Astfel, pentru fiecare combinație de la m la n corespunde o secvență de n și m -1 zerouri. Numărul acestor secvențe este egal cu numărul de moduri în care puteți selecta m-1 locuri pentru zerouri de la n + m -1 din numărul total de locuri () sau același număr de moduri de a selecta n locuri pentru unități de la n + m-1 locuri. Egalitatea rezultă din egalitate.
Compoziții și partiții. Lăsați sarcina de a genera partiții unui întreg pozitiv n la secvența de numere întregi p1, p2, ..., pk>, astfel încât p1 + p2 + ... + = n și pk pi pot fi aplicate pe diverse constrângeri.
Dacă ordinea numerelor pi este importantă, atunci (p1, p2, ..., pk) se numește compoziția n. Căutarea compozițiilor este realizată cu restricția pi> 0.
Dacă k este fix, atunci astfel de compoziții sunt numite compoziții de n de părți k. Atunci când sunt căutate, restricția pi> 0 poate fi eliminată, adică pi = 0 este rezolvată.
Să explicăm diferența dintre compoziții, compoziții ale componentelor k și partiții în următorul exemplu:
compoziții: (3), (1,2), (2,1), (1,1,1),
compoziții din două părți (pi> 0): (1,2), (2,1),
compoziții de două părți (pi3): (0,3), (1,2), (2,1), (3,0),
Teorema. Numărul de compoziții n este 2 n-1.
Dovada. Împărțim un segment de lungime n în n segmente de lungime a unității prin intermediul punctelor (n-1). Apoi compoziția n corespunde unei marcări de corespondență unu la unu dintre unele puncte de separare. Elementele compoziției în acest caz sunt distanța dintre punctele adiacente. De exemplu, compoziția (2,2,1), n = 5 este prezentată în figura 2.1.
Prin urmare, fiecare compoziție n corespunde unei metode de selectare a unui subset de puncte (n-1). Asta este, numărul de compoziții n este 2 n-1.
Teorema. Numărul de compoziții n ale părților k cu restricția pi> 0 este egal cu.
Dovada. Reprezentăm compoziția și ca dovadă a teoremei precedente. Fiecare compoziție n de părți k (pi> 0) corespunde unei metode de selecție (k -1) - un subset de elemente de puncte de n-1 puncte. Adică numărul acestor compoziții este.
Teorema. Numărul de compoziții n de părți k dacă pi0 este egal cu.
Dovada. Fiecare compoziție de n componente în timp ce k pi ³0 una corespondență între setul binar astfel încât primul termen este egal cu numărul de unități care se confruntă cu primul zero din setul, al doilea - numărul de unități care se confruntă cu primul și zero secunde, etc. Un exemplu de astfel de reprezentare a compoziției n = 4, k = 3 este dat în Tabelul 2.1.
Lungimea set este n + k -1, numărul de zerouri este egal cu k -1, prin urmare, numărul de seturi (compozițiilor dorite) este numărul de moduri k -1 plasează zerouri de alegere pentru n + k -1 locuri () sau același număr de moduri de a alege n locurile pentru unități de la n + k-1 locuri ().
Ilustrație a teoremei privind numărul de compoziții ale n de părți k