Capitolul 1Analiză combinatorică

§1. Aranjamente, permutări, combinări simple şi cu repetiţie. Modele combinatoriale pentru acestea

Analiza combinatorică este o parte a matematicii ce studiază mulţimi discrete de obiecte,

de obicei finite. Ea are conexiuni cu alte ramuri ale matematicii ca algebra, teoria probabilităţilor şi geometria având aplicaţii în informatică şi fizica statistică. Analiza combinatorică include:

- numărarea unor obiecte sau anumite clase de echivalenţă de obiecte care se identifică pe baza unei anumite relaţii (combinatorica enumerativă);

- verificarea dacă un criteriu poate fi satisfăcut şi construirea sau analizarea obiectelor ce satisfac criteriul respectiv (modele combinatoriale şi teoria matroizilor);

- găsirea obiectului „celui mai mare”, „celui mai mic” sau „optimal” (combinatorica extremală sau optimizare combinatorială);

- găsirea unor structuri algebrice pe care o formează anumite obiecte (combinatorica algebrică).

De obicei în aceasă lucrare vom studia probleme de combinatorica enumerativă, modele combinatoriale sau optimizare combinatorială. Prin notaţiile m, n sau k vom înţelege numere naturale. O problemă de combinatorică enumerativă este cea prezentată în cele ce urmează.

Problemă. Presupunem că sunt date n mărgele de diferite culori, două mărgele de aceeaşi culoare ne putând fi deosebite una de alta. Se cere să se numere câte şiraguri de n mărgele se pot forma cu mărgele de m culori. Desigur soluţia depinde de definiţia exactă a unui şirag, adică în ce condiţii două şiraguri se consideră identice. De exemplu putem considera următoarele cazuri:

a) Cele n mărgele sunt puse pe aceeaşi linie pe n poziţii fixate;b) Mărgelele sunt puse pe o sfoară care are capetele libere (şirag deschis);c) Mărgelele sunt puse pe o sfoară care are capetele lipite (şirag închis);d) Mărgelele sunt puse pe o sfoară care are capetele lipite iar două şiraguri închise se

consideră identice dacă se obţin unul din altul prin schimbarea culorilor (model de şirag închis).În fig. 1 sunt prezentate aceste cazuri pentru n=3 şi m=2.

1

De obicei se încearcă găsirea unei formule explicite ca rezultat al numărării unor obiecte sau clase de obiecte. De exemplu în cazul a) al problemei anterioare numărul şiragurilor este deoarece pe fiecare din cele n poziţii pot apare m tipuri de bile. Totuşi uneori este dificilă sau chiar imposibilă găsirea unei formule explicite dar este mai uşor să se determine soluţia cu ajutorul unei formule de recurenţă care reduce găsirea acesteia folosind unele rezultate anterioare.

O metodă de demonstrare a unor anumitor relaţii utile este folosirea a două moduri distincte pentru numărarea unor obiecte sau clase de obiecte.

Exemplul 1.1. Fie numărul partiţiilor lui n în exact k părţi adică numărul de scrieri unde

Atunci este egal cu numărul partiţiilor lui n având cea mai mare parte cu k elemente. Acest lucru rezultă uşor folosind o numărare dublă. Fie de exemplu n=7, k=4 şi partiţia lui n

ce are k=4 părţi reprezentată grafic cu diagrama Ferrer şi transpusa ei (v. fig. 2).

Deoarece numărul pătratelor care apar este egal cu n în ambele cazuri iar transpusa corespunde unei partiţii cu cea mai mare parte egală cu k, 7=1+2+4 rezultă egalitatea numărului celor două tipuri de partiţii căci există o funcţie bijectivă ce duce o diagramă Ferrer în transpusa sa.

2

Vom prezenta unele noţiuni şi rezultate de analiză combinatorică completând unele cunoştinţe dobândite în timpul liceului.

Considerăm n obiecte distincte a1, a2,…,an. Dacă un aranjament (simplu) a celor

n obiecte luate câte m este o mulţime (grupare) ordonată de m obiecte distincte din

cele n date. Două aranjamente , a celor n obiecte luate câte m se

consideră distincte dacă ele diferă prin ordinea elementelor sau prin natura lor, adică există astfel încât obiectele şi sunt distincte.

Exemplul 1.2. Fie obiectele distincte a,b,c. Aranjamentele (simple) ce se pot forma cu aceste trei obiecte luate câte două sunt:

Date cele n obiecte distincte a1, a2,…,an, vom nota numărul tuturor aranjamentelor celor n obiecte luate câte m cu În aceste condiţii putem demonstra rezultatul ce urmează.

Teorema 1.1. Cu notaţiile anterioare (1.1.1)

Demonstraţie. Vom stabili pentru început o formula de recurenţă unde (1.1.2)

Pentru aceasta observăm că un aranjament de n obiecte luate câte k-1 conţine k-1

obiecte deci n-k+1 obiecte nu apar în acest aranjament. Adăugând pe ultima poziţie oricare dintre aceste n-k+1 obiecte la cele k-1 fixate obţinem n-k+1 aranjamente de n obiecte luate câte k care sunt distincte două câte două deoarece ele diferă prin ultimul element. Dacă procedăm în acelaşi mod cu două aranjamente distincte de n obiecte luate câte k-1 obţinem aranjamente de n obiecte luate câte k care sunt distincte două câte două. În acest mod găsim aranjamente distincte de n obiecte luate câte k. Cum orice aranjament de n obiecte luate câte k se poate obţine prin acest procedeu din aranjamentul de n obiecte luate câte k-1 determinat de primele k-1 elemente ale sale rezultă formula (1.1.2). Deoarece utilizând succesiv formula (1.1.2) pentru k=m,m-1,…,2 obţinem

de unde rezultă formula (1.1.1). □

Exemplul 1.3. Fie A şi B două mulţimi finite. Presupunem că , unde prin notăm cardinalul mulţimii A (numărul de elemente din A). În cazul că există funcţii injective Pentru a demonstra această afirmaţie este suficient să observăm că f este injectivă dacă şi numai dacă unde Dacă

funcţia f este unic determinată de mulţimea ordonată

de unde rezultă afirmaţia.

3

Dacă în definiţia aranjamentelor renunţăm la restricţia ca cele m obiecte din gruparea

să fie distincte obţinem un aranjament cu repetiţie de n obiecte luate câte m. În acest

caz nu este necesar să presupunem .

Exemplul 1.4. Fie obiectele distincte a,b,c. Aranjamentele cu repetiţie ce se pot forma cu aceste trei obiecte luate câte două sunt:

Dacă sunt date n obiecte distincte a1, a2, … , an, vom nota numărul tuturor aranjamentelor cu repetiţie a celor n obiecte luate câte m cu Vom demonstra rezultatul ce urmează.

Teorema 1.2. Cu notaţiile anterioare (1.1.3)

Demonstraţie. Analog ca în demonstraţia teoremei 1.1 vom stabili o formula de recurenţă unde (1.1.4)

Pentru aceasta observăm că dat un aranjament cu repetiţie de n obiecte luate câte k-1

putem obţine n aranjamente cu repetiţie de n obiecte luate câte k, distincte două câte

două, adăugând pe ultima poziţie unul dintre cele n obiecte distincte date iniţial. De aici rezultă formula (1.1.4). Deoarece utilizând succesiv formula (1.1.4) pentru k=m,m-1,…,2 găsim

,deci relaţia (1.1.3) este demonstrată. □

Exemplul 1.5. Fie A şi B două mulţimi finite cu . Analog ca în exemplul 1.3 se arată că există funcţii

Date n obiecte distincte a1, a2, …, an, o permutare (simplă) a celor n obiecte este o

mulţime (grupare) ordonată ce conţine toate cele n obiecte distincte date. Evident o

permutare este un aranjament de n obiecte luate câte n. Vom nota cu Pn sau n! numărul tuturor permutărilor celor n obiecte date. Din relaţia (1.1.1) se obţine formula

(1.1.5)

Prin convenţie se consideră Dacă în definiţia permutărilor renunţăm la restricţia ca cele n obiecte din gruparea

să fie distincte obţinem o permutare cu repetiţie a celor n obiecte. Se observă că o

permutare cu repetiţie a celor n obiecte este un aranjament cu repetiţie de n obiecte luate câte n. Dacă notăm cu numărul tuturor permutărilor cu repetiţie a celor n obiecte date, din formula (1.1.3) deducem relaţia

(1.1.6)

Fie din nou n obiecte distincte a1, a2,…,an. Dacă o combinare (simplă) a celor n

obiecte luate câte m este o mulţime (grupare) de m obiecte distincte din cele n date.

Două combinări , a celor n obiecte luate câte m se consideră distincte

4

dacă ele diferă prin natura lor, adică există astfel încât obiectul este diferit de toate

obiectele , t=1,2,…,m.

Exemplul 1.6. Fie obiectele distincte a,b,c. Combinările (simple) ce se pot forma cu aceste trei obiecte luate câte două sunt:

Date cele n obiecte distincte a1, a2, … , an, vom nota numărul tuturor combinărilor celor n

obiecte luate câte m cu sau . Formula de calcul al acestui număr este dată în rezultatul ce

urmează.

Teorema 1.3. Cu notaţiile anterioare (1.1.7)

Demonstraţie. Observăm că dintr-o combinare de n obiecte luate câte m obţinem m! aranjamente de n obiecte luate câte m, distincte două câte două, efectuând toate permutările posibile ale celor m obiecte. Deci şi din relaţiile (1.1.1) şi (1.1.5) rezultă

ceea ce demonstrează teorema. □

Prin convenţie se consideră

Exemplul 1.7. Folosind definiţia combinărilor deducem că dacă o mulţime A are n elemente, atunci pentru orice A are exact submulţimi cu m elemente.

Din exemplul 1.7 rezultă , (1.1.8)

deoarece într-o mulţime cu n elemente există acelaşi număr de submulţimi cu m elemente şi de submulţimi cu m-n elemente (există o corespondenţă biunivocă între aceste familii de submulţimi care asociază unei submulţimi complementara sa).

Dacă în definiţia combinărilor renunţăm la restricţia ca cele m obiecte din gruparea

să fie distincte obţinem o combinare cu repetiţie de n obiecte luate câte m. Analog

ca în cazul aranjamentelor cu repetiţie, nici aici nu este necesar să presupunem .

Exemplul 1.8. Fie obiectele distincte a,b,c. Combinările cu repetiţie ce se pot forma cu aceste trei obiecte luate câte două sunt:

Dacă notăm numărul tuturor combinărilor cu repetiţie ale celor n obiecte luate câte m cu

sau formula de calcul al acestui număr este dată în rezultatul ce urmează.

Teorema 1.4. Folosind notaţiile anterioare este adevărată formula (1.1.9)

5

Demonstraţie. Vom stabili pentru început o formula de recurenţă

unde (1.1.10)

Pentru aceasta considerăm toate combinările cu repetiţie a celor de n obiecte date a1, a2, …, an

luate câte k şi observăm ca numărând toate obiectele ce apar în aceste combinări, indiferent dacă

sunt distincte sau nu, găsim elemente. Atunci un obiect fixat, de exemplu a1, apare de

ori în toate combinările cu repetiţie a celor de n obiecte date luate câte k. Dacă eliminăm o singură dată obiectul a1 din toate combinările cu repetiţie a celor de n obiecte date luate câte k

numărul acestor combinări modificate este şi ele conţin pe a1 de ori conform

formulei stabilite. Deoarece a1 a fost eliminat de ori deducem că acest element apare de

ori în toate combinările cu repetiţie a celor de n obiecte date

luate câte k. Deci de unde rezultă relaţia (1.1.10). Deoarece

utilizând succesiv formula (1.1.10) pentru k=m,m-1,…,2 obţinem

de unde rezultă relaţia (1.1.9). □

Observaţia 1.1. Din formulele (1.1.7) şi (1.1.9) deducem următoarea relaţie între numărul combinărilor simple şi a celor cu repetiţie

(1.1.11)

6