CN Onisifor Ghibu Oradea Cercul de...

CN Onisifor Ghibu Oradea Cercul de informatică

1

Noțiuni de combinatorică

1. Prezentare generală

Combinatorica se ocupă cu studiul mulțimilor (de obicei finite) de obiecte și modalitățile de a le "combina" sau asocia

sau pune laolaltă (Wikipedia).

Probleme “tipice” de combinatorică ar fi:

- determinarea numărului de elemente ale unei mulțimi sau submulțimi;

- precizarea elementelor unei mulțimi sau submulțimi;

- determinarea numărului de moduri de a alege elemente dintr-o mulțime;

- determinarea numărului de moduri de a combina elementele unei/unor mulțimi;

- etc;

În informatică ne interesează implementarea unor algoritmi eficienți pentru rezolvarea problemelor de combinatorică.

Pentru rezolvarea unor probleme există formule matematice, pentru alte probleme trebuie dedusă o formulă de calcul

și implementat un algoritm eficient pentru formula dedusă.

2. Principii fundamentale de numărare

2.1. Regula produsului

Fiind date două mulțimi A și B, dacă există X moduri de a alege un element din A și Y moduri de a alege un element din B,

atunci există X * Y moduri de a alege două elemente din cele două mulțimi.

Generalizare: Fiind date n mulțimi A1, A2 ... An, dacă există x1 moduri de a alege un element din A1, x2 moduri de

a alege un element din A2 ... xn moduri de a alege elemente din An, atuni există x1 * x2 * ... * xn moduri de a

alege n elemente din cele n mulțimi.

Exemplul 1: Roterb și Ațidu au meci cu echipa școlii. Antrenorul a pregătit 12 tricouri. În câte feluri se pot aloca

tricourile celor doi fotbaliști?

- alocarea se poate descompune în 2 operații distincte: alocarea unui tricou pentru Roterb, urmată de alocarea unui

tricou pentru Ațidu.

- există 12 alternative pentru prima operație, deoarece sunt 12 ticouri în total.

- există 11 alternative pentru operația a doua, deoarece tricoul alocat lui Roterb nu mai este liber.

- conform regulii produsului, sunt 12 * 11 = 132 variante.

Exemplul 2: Pentru a participa la un concurs echipa formată din Mănil, Rașer și Palu trebuie să realizeze un proiect. Ei

trebuie să precizeze limbajul de programare ales (C++, Pascal, Delphi, Visual C#, PHP) și un domeniu în care se

încadrează proiectul (WEB, POO, Gaming, Networking). Câte tipuri de proiecte pot realiza?

- există 5 moduri de a alege limbajul de programare.

- există 4 moduri de a alege domeniul.

- conform regulii produsului, sunt 5 * 4 = 20 de tipuri de proiecte.

Exemplul 3: Pentru că se plictisesc la ora de .... , Dna și Adny scriu pe caiet șiruri formate din 0 și 1. Câte șiruri diferite

de lungime 8 pot ei scrie?

- fiecare din cele 8 poziții poate fi aleasă în 2 feluri: 0 sau 1.

- conform regulii produsului, există 28 = 256 variante.

Exemplul 4: Sregiu și-a uitat codul de 4 cifre de la lacătul bicicletei. Câte variante de cod există

dacă: - pot exista cifre care apar de mai multe ori în cod;

https://ro.wikipedia.org/wiki/Mul%C8%9Bime_finit%C4%83


2

- în cod pot apărea doar cifre distincte două câte două.

Generalizare: - Câte funcții sunt de la o mulțime cu m elemente la o mulțime cu n elemente?

- Câte funcții injective sunt de la o mulțime cu m elemente la o mulțime cu n elemente (m ≤ n)?

2.2. Regula sumei

Fiind date două mulțimi A și B, dacă există X moduri de a alege un element din A și Y moduri de a alege un element din B,

atunci există X + Y moduri de a alege un elemente care să aparțină uneia dintre cele 2 mulțimi.

Generalizare: Fiind date n mulțimi A1, A2 ... An, dacă există x1 moduri de a alege un element din A1, x2 moduri de

a alege un element din A2 ... xn moduri de a alege elemente din An, atuni există x1 + x2 + ... + xn moduri de a

alege un element care să aparțină uneia din cele n mulțimi.

Exemplul 1: Partik are 9 oferte de la echipe din Anglia, 7 oferte de la echipe din Spania și 11 oferte de la echipe din

Italia. În câte moduri poate alege o ofertă?

- poate alege în 9 moduri o ofertă din Anglia.

- poate alege în 7 moduri o ofertă din Spania.

- poate alege în 11 moduri o ofertă din Italia.

- conform regulii sumei, sunt 9 + 7 + 11 = 27 variante de a alege o ofertă.

Exemplul 2: Valdy poate fi înscris pe foaia de joc în naționala U16 pe 5 posturi (PG, SG, SF, PF, C), în naționala U18 pe

4 posturi (PG, SG, SF, PF), iar la U20 pe 3 posturi (PG, SG, SF). Datorită calendarului poate participa doar la competițiile

a două dintre cele 3 naționale. În câte moduri poate fi înscris pe foaia de joc dacă participă la competiția a două naționale?

(pe foaia de joc se scrie un singur post pentru întreaga competiție).

- dacă participă la U16 + U18 poate fi înscris în 5 * 4 = 20 moduri.



- conform regulii sumei soluția va fi 20 + 15 + 12 = 47 de moduri.

Exemplul 3: Iamsina scrie un program în care numele variabilelor folosite conțin cel mult 3 caractere (litere mari, litere

mici și cifre). Câte variabile poate declara dacă primul caracter al variabilei trebuie să fie obligatoriu o literă? (sunt 10

cifre, 26 litere mari, 26 litere mici și se face deosebire între literele mari și literele mici).

- fie N1 numărul de variabile de lungime 1, N2 – numărul de variabile de lungime 2 și N3 – numărul de variabile de

lungime 3.

- N1 = 52 există 52 de moduri de a declara o variabilă de lungime 1 (26 litere mari + 26 litere mici).

- N2 - există 52 de moduri de a alege primul caracter al variabilei, 62 de moduri de a alege al doilea caracter al

variabilei (26 litere mari + 26 litere mici + 10 cifre). Conform regulii produsului N2 = 52 * 62 = 3224.

- N3 - există 52 de moduri de a alege primul caracter al variabilei, 62 de moduri de a alege al doilea caracter al

variabilei (26 litere mari + 26 litere mici + 10 cifre) și 62 de moduri de a alege al treilea caracter al variabilei

(26 litere mari + 26 litere mici + 10 cifre). Conform regulii produsului N3 = 52 * 62 * 62 = 199888.

- Conform regulii sumei în total pot fi declarate 52 + 3224 + 199888 = 203164 variabile.

2.3. Principiul includerii și excluderii

Fiind date două mulțimi A și B, care pot avea elemente comune. Dacă există X moduri de a alege un element din A și Y

moduri de a alege un element din B, atunci există X + Y - |X ∩ Y| moduri de a alege un elemente care să aparțină

uneia dintre cele 2 mulțimi, unde |X ∩ Y|reprezintă numărul de elemente comune care pot fi selectate.

Atunci când mulțimile au elemente comune prin regula sumei elementele comune sunt alese (incluse) de două ori, de

aceea acestea trebuie excluse ulterior din soluție.


3

Exemplul 1 – Și Dadiv se plictisește la ora de caligrafie (scrie foarte frumos și ordonat, nu mai are ce să învețe). Și el

scrie șiruri formate din 0 și 1. Câte șiruri distincte de lungime 8 care încep cu 1 sau se termină cu 00 poate el scrie?

- se determină numărul de șiruri de lungime 8, care încep cu 1. Pe prima poziție se poate alege un element, pe a

doua poziție se pot alege 2 elemente (0 sau 1), pe a treia poziție se pot alege 2 elemente (0 sau 1) ... pe a opta

poziție se pot alege 2 elemente (0 sau 1). Conform regulii produsului numărul de șiruri de lungime 8 care încep

cu 1 va fi 1 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 27

- se determină numărul de șiruri de lungime 8, care se termină cu 00. Pe prima poziție se pot alege 2 elemente (0

sau 1), pe a doua poziție se pot alege 2 elemente (0 sau 1), pe a treia poziție se pot alege 2 elemente (0 sau 1) ...

pe a șaptea și a opta poziție se poate alege câte un element (0). Conform regulii produsului numărul de șiruri de

lungime 8 care se termină cu 00 va fi 2 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 26

- dacă aplicăm regula sumei (adunăm numărul de șiruri care încep cu 1 cu numărul de șiruri care se termină cu 00)

soluția găsită va fi eronată, deoarece există șiruri care încep cu 1 și se termină cu 00, care au fost numărate de 2

ori. Acestea trebuie excluse din soluție.

- dar câte șiruri de lungime 8, care încep cu 1 și se termină cu 00 există? Pe poziția 1 se poate alege 1 element (1),

pe a doua poziție se pot alege 2 elemente (0 sau 1), pe a treia poziție se pot alege 2 elemente (0 sau 1) ... pe a

șaptea și a opta poziție se poate alege câte un element (0). Conform regulii produsului numărul de șiruri de

lungime 8 care încep cu 1 și se termină cu 00 va fi 1 * 2 * 2 * 2 * 2 * 2 * 1 * 1 = 25

- conform principiului includerii și excluderii soluția va fi 27 + 26 - 25 = 160.

Exemplul 2 – Câte numere mai mici sau egale cu 1000 sunt divizibile cu 3 sau cu 4?

- se determină numărul de numere divizibile cu 3: 1000 / 3 = 333

- se determină numărul de numere divizibile cu 4: 1000 / 4 = 250

- din cele două mulțimi trebuie excluse numerele care sunt divizibile atât cu 3 cât și cu 4, deaorece acestea au fost

numărate de două ori 1000 / 12 = 83

- conform principiului includerii și excluderii soluția va fi 333 + 250 – 83 = 500

Exemplul 3: Se știe că o parolă este un șir între 6 și 8 caractere lungime, și că fiecare caracter este fie o literă mare sau o

cifră zecimală. Fiecare parolă conține cel puțin o cifră. Câte parole posibile sunt?

- Se determină numărul de parole valide de lungime 6, de lungime 7 și de lungime 8.

- Pentru parolele de lungime 6, avem 36 de posibilități de a alege caracterul de pe poziția 1 (26 de litere și 10

cifre), 36 de posibilități de a alege caracterul de pe poziția 2 (26 de litere și 10 cifre), … 36 de posibilități de a

alege caracterul de pe poziția 6 (26 de litere și 10 cifre). Conform regulii produsului avem 366 posibilități de a

alege parolel de lungime 6. Dintre aceste posibilități trebuie excluse parolele care conțin numai litere. Câte astfel

de parole există? Conform raționamentului anterior 266. Astfel, parole valide de lungime 6, vom avea 366 -

266

- parole valide de lungime 7, vom avea 367 – 267

- parole valide de lungime 8, vom avea 368 – 268

- numărul total de parole va fi 368 – 268 + 367 – 267 + 366 – 266

3. Algoritmi combinatoriali

3.1. Permutări

Fie A o mulțime finită cu n elemente A = {a1, a2 … an}. O permutare a lui A este un aranjament al tuturor

elementelor lui A.

De exemplu: Dacă A = {1, 2, 3} atunci {3, 1, 2} și {1, 3, 2} sunt

permutri ale mulțimii A.


4

3.1.1. Permutări fără repetiție

Să presupunem că avem 5 scaune și 5 elevi care doresc să se așeze pe cele 5 scaune. În câte moduri distincte se pot ei

așeza?

Răspuns: pe primul scaun se poate așeza oricare din cei 5 copii. Pe al doilea scaun oricare din cei 4 rămași, etc. Obtinem:

5 * 4 * 3 * 2 * 1 variante de așezare. Notăm produsul 5 * 4 * 3 * 2 * 1 cu 5!

În general, numărul de moduri în care putem permuta o mulțime cu n elemente este: Pn = n! unsigned long long Perm(unsigned int n){

unsigned long long p = 1;

for(unsigned int i = 1; i <= n; i++) p = p * i;

return p;

}

3.1.2. Permutări cu repetiție

Dacă în mulțimea inițială avem cel puțin un element care se repetă, vorbim de permutări

cu repetiție. De exemplu, dacă avem 4 bile, iar bila roșie apare de două ori. Câte

permutări distincte putem obține? Din exemplul alăturat reiesă că 12.

În general, dacă avem n elemente, elementul 1 se repetă de k1 ori, elementul 2 se repetă de k2 ori, ... elementul m se

repetă de km ori numărul de permutări distinte ale mulțimii va fi:

Exemplul 1: Câte cuvinte distincte de 5 litere se pot forma cu literele cuvântului SOARE?

Răspuns: P5 = 5! = 120

Exemplul 2: Câte cuvinte distincte de 5 litere se pot forma cu literele cuvântului ACCES, dacă dorim ca literele CC să

rămână alăturate?

Răspuns: Vom trata grupul CC ca o singură literă. Astfel, vom avea practic 4 litere distincte P4 = 4! = 24

Exemplul 3: Câte cuvinte distincte de 5 litere se pot forma cu literele cuvântului ACCES?

Răspuns: Deoarece litera C apare de două ori, soluția va fi: 5!/2! = 60.

Exemplul 4: Câte cuvinte distincte de 11 litere se pot forma cu literele cuvântului MISSISSIPPI?

3.2. Aranjamente

3.2.1. Aranjamente fără repetiție

Să presupunem că avem la dispoziție cifrele 1, 2, 3, 4 și din aceste cifre extragen câte două pentru a forma numere

de câte două cifre distincte (după ce am extras două numerele extrase sunt puse înapoi). Numerele distincte pe care le

putem forma sunt: 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43. În total avem 12 posibilități de a

forma numere distincte.

Această modalitate de a forma mulțimea se numește aranjamente. Exemplul de mai sus se notează cu (se citește

aranjamente de 4 elemente luate câte 2).

Pentru calculul aranjamentelor există următoarea formulă

unsigned long long Aranjamente(unsigned int n, unsigned int k){

unsigned long long a = 1;

for(unsigned int i = n - k + 1; i <= n; i++) a = a * i;

return a;


5

}

Exercițiul 1: La un concurs de înot participă 8 elevi. În câte moduri se pot împărți locurile de pe podium, dacă nu există

concurenți cu același timp?

Răspuns: - pot fi 3 concurenți din 8 pe podium, iar ordinea contează deci răspunsul

Exercițiul 2: Fie mulțimea {1, 2, 3, 4, 5, 6}. Câte numere distincte cu exact 3 cifre se pot forma cu

elementele mulțimii? Câte numere distincte cu cel mult 3 cifre se pot forma cu elementele mulțimii?

Răspuns 1: - trebuie să selectăm 3 elemente din mulțime. Cum în formarea numerelor contează ordinea cifrelor

răspunsul va fi

Răspuns 2: - avem 6 numere de 1 cifră, 6 * 5 numere cu 2 cifre, 6 * 5 * 4 numere cu 3 cifre. Conform regulii

sumei soluția va fi: 6 + 6 * 5 + 6 * 5 * 4.

3.2.2. Aranjamente cu repetiție

Să presupunem că avem la dispoziție cifrele 1, 2, 3, 4 și din aceste cifre extragen câte două pentru a forma numere

de câte două cifre, cifre nu neapărat distincte (după ce am extras un număr acesta este pus înapoi). Numerele distincte

pe care le putem forma sunt: 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44. În total avem 16

posibilități de a forma numere distincte.

În general, dacă avem n elemente distincte, iar din acestea trebuie să alegem r, elemente, astfel încât elementele se pot

repeta atunci numărul de aranjamente cu repetiție este nr (pe prima poziție putem alege oricare dintre cele n elemente, pe

poziția a doua putem alege oricare dintre cele n elemente etc).

Noțiunea de aranjamente cu repetiție diferă de noțiunea de permutări cu repetiție. Permutările cu repetiție se referă la

faptul că printre elementele de permutat există elemente care se repetă (identice). În cazul aranjamentelor cu repetiție

elementele de aranjat sunt distincte, iar din aceste elemente distincte formăm aranjamente, astfel încât fiecare element

poate fi folosit de mai multe ori.

Permutările sunt un caz special de aranjamente (n = k), dar permutările cu repetiție nu sunt un caz particular al

aranjamentelor cu repetiție.

3.3. Combinări

3.3.1. Combinări fără repetiție

un elev are posibilitatea de a se înscrie la 3 sporturi, dar datorită timpului limitat el poate

practica doar două dintre acestea. În câte moduri poate alege două sporturi distincte dintre

cele 3? Răspunsul este 6. Atunci când trebuie să alegem dintre elementele unei mulțimi, așa

încât (spre deosebire de permutări) ordinea alegerii nu contează, vorbim de combinări.

Pentru calculul numărului de combinări există o formulă binecunoscută:

Prin convenție

.

a) Calculul numărului de combinări folosind triunghiul lui Pascal

În figura alăturată este prezentat triunghiul lui Pascal. Pe fiecare rând i există i

elemente. Elementele de pe margine au valoarea 1, iar celelalte elemente se obțin

adunând cele două elemente situate deasupra. Valoarea elementului de pe linia i,

coloana j este egală cu

int TriunghiulPascal(int n, int k) {


6

int a[NMAX][NMAX];

//o structură de date pentru a stoca elementele triunghiului

a[0][0] = 1;//elementul din varful triunghiului

for (int i = 1; i <= n; i++) {

for (int j = 0; j <= i; j++) {

if (j == i || j == 0) //prima si ultima valoare de pe fiecare linie

a[i][j] = 1; //este 1

else // in caz contrar

a[i][j] = a[i - 1][j - 1] + a[i - 1][j];

//elementul este suma elementelor de deasupra

}

}

return a[n][k];

}

Complexitatea algoritmului este O(n * k). În plus se folosește un tablou bidimensional. Acesta poate fi eliminat

având în vedere că pentru calculul unui element se folosesc doar elementele din linia anterioară.

Avantaje: - ușor de înțeles și de implementat, nu necesită calculul inversului modular;

Dezavantaje – complexitatea de timp și de memorie.

Totuși, triunghiul lui Pascal poate fi folosit atunci când e necesară preprocesarea valorilor numărulu de combinări.

Spre exemplu, trebuie să se răspundă la q (q = 105) întrebări de genul: să se precizeze valoarea

.

b) Calculul recursiv

Pentru calculul recursiv vom folosi formula recursivă dedusă la triunghiul lui Pascal:

C(n, k) = {

int CombRec(int n, int k) {

if (k == 0 || k == n) return 1;

else return CombRec(n - 1, k - 1) + CombRec(n - 1, k);

}

Algoritmul de mi sus e foarte ineficient, are loc o recursivitate în cascadă, unele valori sunt calculate de mai multe

ori etc. Acesta poate fi optimizat, dacă se procedează în felul următor:

- pentru alegerea a k elemente dintre cele n, se aleg k - 1 elemente;

- apoi din cele n – k + 1 elemente rămase trebuie ales unul. Dar, astfel, fiecare combinație va apărea de k

ori, deci rezultatul va trebui împărțit cu k.

Formula recursivă devine:

C(n, k) = {

int CombRec(int n, int k) {

if (k == 0 or k == n) return 1;

else return CombRec(n, k - 1) * (n - k + 1) / k;

}

c) Calculul iterativ

Ne vom baza pe următoarea observație:

Am simplificat fracția cu valoarea k!. int Comb(int n, int k){


7

int ans = 1;

for(int i = k + 1; i <= n; i++)

ans = ans * i / (i - k);

return ans;

}

În exemplul anterior am simplificat fracția cu k!. Pentru o complexitate mai bună e de preferat să se simplifice

fracția cu max(k!, (n – k)!).

Datorită faptului că pentru valori mari ale lui n, valoarea este un număr foarte mare, în multe probleme se cere

valoarea combinărilor modulo M. În acest caz algoritmul de mai sus devine incorect.

Se va proceda în felul următor:

- se calculează valoarea modulo M a numărătorului;

- se calculează valoarea modulo M a numitorului;

- se obține inversul modular al valorii numitorului obținut la pasul anterior;

- se înmulțește modulo M valoarea numărătorului (obținută la pasul 1) cu valoarea inversului modular (obținut la

pasul 3). long long invMod(long long x, int p, int M){

long long ans = 1;

while(p > 0){

if(p % 2 == 1) ans = ans * x % M;

x = x * x % M;

p = p / 2;

}

return ans;

}

long long int CombModuloM(int n, int k){

long long n1 = 1, n2 = 1;

//calculam numaratorul (k+1) * (k + 2) * … * n % M

for(int i = k + 1; i <= n; i++) n1 = n1 * i % M;

//calculam numitorul 1 * 2 * … * (n – k) % M

for(int i = 1; i <= n - k; i++) n2 = n2 * i % M;

n2 = invMod(n2, M – 2, M);//n2^(M-2)%M

return (n1 % M) * (n2 % M) % M;

}

Proprietăți:

-

- ∑

(hockey stick rule – urmăriți forma în triunghiul lui Pascal). (

– vezi

nmult – ONI 2015).

Exercițiul 1: În clasa a 10-a C sunt 15 băieți și 14 fete. În câte moduri pot fi selectați 4 băieți și 5 fete pentru a juca într-o

piesă de teatru?

Răspuns: - cei 4 băieți pot fi selectați în moduri.

- cele 5 fete pot fi selectate în moduri.

- conform regulii produsului soluția va fi: *

Exemplul 2: Rașer, Palu, Mănil și Adițu joacă cruce (joc de cărți care stimulează gândirea creativă). În câte moduri

distincte pot fi împărțite cele 24 de cărți în mod egal (6 cărți/elev) celor 4 elevi?


8

Răspuns 1: - presupunem că ordinea în care primesc cărțile este cea de mai sus. Rașer primește 6 cărți din 24. El

poate primi aceste cărți în . Palu primește următoarele 6 cărți din cele 18 rămase. În câte moduri le poate primi?

În

mod asemănător Mănil poate primi în , iar Ațidu în

moduri.

- Conform regulii produsului soluția va fi

Răspuns2: să întindem cărțile pe masă și să scriem sub fiecare numărul jucătorului care le primește.

- astfel, la fiecare împărție a cărților putem asocia un șir de 6 valori de 1, 6 valori de 2, 6 valori de 3, 6 valori de 4.

- câte astfel de șiruri putem avea?

Exemplul 3: Rașer face cărțile, dar pentru că “știe” să le împartă toți așii ajung la el. În câte moduri poate împărți cărțile,

astfel încât toți așii să ajungă la el?

Răspuns:

Exemplul 4: În cadrul campaniei de ajutorare a persoanelor nevoiașe Palu a adus la școală 20 de mere și 10 portocale. În

câte moduri poate forma pachete cu 10 fructe în care să fie exact 4 portocale? Dar pachete în care să fie cel puțin 6

portocale?

Răspuns1: - cele 4 portocale pot fi alese în moduri, iar merele în

moduri.

- conform regulii produsului soluția este

moduri

Răspuns2: - pachete cu exact 6 portocale pot fi formate în

moduri.

- pachete cu exact 7 portocale pot fi formate în

moduri.


moduri.


moduri.


moduri.

- conform regulii sumei soluția va fi

+

Exemplul 4: În clasa a X-a C sunt 15 băieți și 14 fete. În câte moduri se poate forma o echipă alcătuită din 3 fete și 2

băieți pentru a participa la un concurs de informatică? În câte moduri poate fi formată echipa alcătuită din 3 fete și 2

băieți, dacă eleva A s-a certat cu elevul B și ei nu pot face parte împreună din echipă?

Răspuns2: - cele 3 fete pot fi alese în moduri, iar cei doi băieți în

moduri.

- conform regulii produsului soluția este

moduri

Răspuns2: - dacă eleva A nu face parte din echipă, echipele pot fi formate în

moduri.

- dacă elevul B nu face parte din echipă, echipele pot fi formate în

moduri.

- dacă niciunul nu face parte din echipă, echipele pot fi formate în

moduri.

- conform regulii sumei soluția va fi

+

moduri.

3.3.2. Combinări cu repetiție


9

Avem 4 tipuri de înghețată. În câte feluri distincte putem cumpăra o înghețată formată din 3 globuri? Ordinea nu contează

și pot fi mai multe globuri de același tip.

Din exemplu reiese că pot fi cumpărate 20 de feluri distincte de înghețată.

Dacă avem n elemente distincte, din fiecare element avem o cantitate infinită și trebuie să alegem k elemente dintre cele n,

astfel încât ordinea elementelor nu contează, spunem că avem combinări cu repetiție. Să notăm combinările de n obiecte

luate câte k, în care repetiția obiectelor e permisă cu .

Exemplu de problemă: în câte moduri pot să așez n = 5 cărămizi în k = 3 lăzi? Cărămizile sunt identice.Pentru rezolvare,

să găsim întâi un mod de a codifica soluțiile. Codificăm o soluție prin n cifre între 1 și k. De exemplu, (2, 1, 2, 3, 1)

înseamnă că punem prima cărămidă în lada 2, a doua cărămidă în lada 1, a treia cărămidă în lada 2, a patra cărămidă în

lada 3, a cincea cărămidă în lada 1. Deoarece cărămizile sunt identice, soluția (2, 1, 2, 3, 1) este identică cu soluția (1, 1, 2,

2, 3), căci rezultatul este același: avem două cărămizi în prima ladă, două în a doua și una singură în a treia. Așadar,

soluțiile canonice sunt cele în care numerele lăzilor sunt ordonate crescător.

Câte soluții unice există? Să ne închipuim un robot care depozitează automat cărămizile dintr-o soluție ordonată, cum ar fi

(1, 1, 2, 2, 3). Robotul pornește din fața primei lăzi. La fiecare pas, el poate face două acțiuni:

- Depozitează o cărămidă în lada curentă. Notăm această acțiune cu caracterul '.' (punct).

- Avansează la lada următoare. Notăm această acțiune cu '/' (slash).

Iată câteva exemple de soluții canonice și reprezentările lor în limbajul robotului.

(1, 1, 2, 2, 3) <---> ../../.

(1, 1, 1, 1, 1) <---> .....//

(1, 3, 3, 3, 3) <---> .//....

(2, 2, 2, 3, 3) <---> /.../..

Deoarece robotul depozitează exact n cărămizi și avansează de k - 1 ori, șirul de caractere va avea mereu n + k - 1

simboluri, din care n vor fi punct și k - 1 slash. Mai mult, orice combinație de puncte și slashuri corespunde în mod

bijectiv unei soluții canonice.

Analogia cu robotul este interesantă pentru că ne dă și o metodă exhaustivă de a genera toate combinările cu repetiție prin

reducerea la combinări obișnuite (fără repetiție).

Exemplul 1: Câte piese de domino inscripționate cu puncte de la 0 la 8 există?

Rezolvare: - să notăm punctele de pe cele 2 părți cu x și y, astfel încât 0 ≤ x ≤ y ≤ 8.

- dacă nu ar exista piese cu valori egale pe cele 2 părți soluția ar fi .

- dar cum pot fi și piese cu valori egale pe ce două fețe soluția este


10

Exemplul 2: Partik aduce 10 mingi de fotbal identice de la Liverpool. Ajuns acasă el dorește să împartă aceste mingi la 4

copii din clasa pregătitoare. În câte moduri poate împărți mingile? În câte moduri poate împărți mingile, astfel încât

fiecare copil să primească cel puțin o minge?

Răspuns 1: - să aliniem cele 10 mingi și să le despărțim printr-o bară. Mingile până la prima bară vor reveni

primului copil, mingile între prima și a doua bară vor reveni celui de al doilea copil, mingile dintre a doua și a treia bară

vor reveni celui de al treilea copil, iar mingile de după a treia bară vor reveni celui de al patrulea copil. Așadar, avem

nevoie de 3 bare.

| | |

- configurația de mai sus corespunde următoarei împărțeli: copil 1 – 0 mingi, copil 2 – 0 mingi, copil 3 – 0 mingi,

copil 4 – 10 mingi.

- se pune problema în câte moduri distincte putem aranja mingile și barele? Avem 13 obiecte (3 bare, 10 mingi).

Soluția va fi

=

Răspuns 2: - dacă fiecare copil trebuie să primească cel puțin o minge, Partik va de pentru început o minge fiecărui

copil, apoi cele 6 mingi rămase le va împărți conform algoritmului de mai sus.

- soluția

Exemplul 3: În câte moduri poate fi scris numărul 2020 ca sumă de:

a) 7 numere naturale?

b) 7 numere naturale nenule?

Două sume se consideră distincte chiar dacă au aceeși termeni, dar în altă ordine.

Răspuns a) Ca și la exemplul anterior adăugăm 6 bare. Răspunsul va fi

Răspuns b)

Exemplul 4: Dispunem de 2 acvarii mari, 4 acvarii mici și 40 de peștișori aurii În câte moduri putem așeza peștișorii în

acvarii, astfel încât în acvariile mari să avem câte 10 peștișori, iar în acvariile mici câte 5 peștișori?

Răspuns: Din punct de vedere al modurior de așezare, așezarea peștișorului 1 în acvariul mare 1 și așezarea

peștișorului 2 în acvariul mare 2, este identică cu așezarea peștișorului 1 în acvariul mare 2 și așezarea peștișorului 2 în

acvariul mare 1 (peștișorii 1 și doi sunt în acvarii mari).

- dacă acvariile ar fi distincte două câte două atunci modurile de așezare ar fi

- cu această formulă numărăm ca modalitate distinctă și cazurile când aceleași grupuri de peștișori se află în acvarii

de aceeași mărime.

- aceste cazuri trebuie excluse (ca în cazul permutărilor cu repetiție). Soluția devine

Exemplul 5: Avem 4 bile roșii, o bilă albă, o bilă albastră, o bilă neagră și o bilă verde. În câte moduri putem forma

secvențe de câte 4 bile, dacă bilele de aceeași culoare nu se disting între ele. Două secvențe diferă, dacă există cel puțin o

poziție în care avem bile de culori diferite.

Răspuns: Să considerăm pe rând diferitele cazuri, în funcție de numărul de bile roșii cuprinse în secvență.

- Dacă avem 4 bile roșii numărul de secvențe este 1

- Dacă avem 3 bile roșii

- Dacă avem 2 bile roșii

- Dacă avem 1 bilă roșie


11

- Dacă nu avem bile roșii avem 24 de moduri

- Soluția va fi 1 + 16 + 144 + 96 + 24

Exemplul 6: Un magazin comercializează 10 tipuri de Laptopuri (Lenovo, Dell, HP, BenQ, Fujitsu, Acer, Apple, MSI,

Myria, Toshiba). În câte moduri putem cumpăra:

a) 8 laptopuri distincte?

b) 8 laptopuri?

c) 12 laptopuri?

Răspuns: a) b)

Bibliografie:

www.wikipedia.org

Király Balázs, Tóth László - Kombinatorika jegyzet és feladatgyujtemény, Pécsi Tudományegyetem, 2011

Mircea Marin - Teoria Grafurilor si Combinatorică

https://www.hackerearth.com/practice/math/combinatorics/basics-of-combinatorics/tutorial/

Bende Imre, Heizlerné Bakonyi Viktória, Menyhárt László, Szlávi Péter, Törley Gábor, Zsakó László -

Kombinatorikai algoritmusok (ELTE szakkör).

www.geeksforgeeks.com

algopedia - Clasele 9-10

http://www.wikipedia.org/

https://www.hackerearth.com/practice/math/combinatorics/basics-of-combinatorics/tutorial/

http://www.geeksforgeeks.com/

CN Onisifor Ghibu Oradea Cercul de...

Documents

Transcript of CN Onisifor Ghibu Oradea Cercul de...