Teoria Grafurilor ˘si Combinatoric a...

29
Teoria Grafurilor ¸ si Combinatoric˘ a recapitulare Principii de num˘ arare Ret ¸inet ¸i c˘ a: P (n, r) este num˘ arul de ¸ siruri (sau r-permut˘ ari) de forma hA 1 ,...,A r i unde A 1 , ..., A r sunt elemente distincte dintr-o mult ¸ime cu n elemente. Formula de calcul este P (n, r)= n! (n - r)! = n · (n - 1) · ... · (n - r + 1) C (n, r) este num˘ arul de submult ¸imi cu r elemente al unei mult ¸imi cu n elemente. Formula de calcul este C (n, r)= n! r!(n - r)! ˆ In total, o mult ¸ime cu n elemente are 2 n submult ¸imi. Exercit ¸ii rezolvate 1. Fie L mult ¸imea literelor {A,B,C,D,E}. (a)Cˆate¸ siruri de 7 litere din L exist˘ a? (b) Cˆ ate ¸ siruri de 9 litere din L cont ¸in A de exact 2 ori si B de exact 3 ori? (c) Cˆate ¸ siruri de 6 litere din L cont ¸in A de cel put ¸in 2 ori ¸ si B de cel put ¸in 2 ori? aspuns: Mai ˆ ıntˆ ai, observ˘am c˘ a L are 5 litere. (a) _______: cele 7 pozit ¸ii trebuiesc completate cu litere din L: Fiecare pozit ¸ie poate fi completat˘aˆ ın 5 feluri. Conform regulii produsului, avem 5 7 posibilit˘ at ¸i de a construi ¸ sirul de 7 litere 5 7 ¸ siruri. 1

Transcript of Teoria Grafurilor ˘si Combinatoric a...

Page 1: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Teoria Grafurilor si Combinatoricarecapitulare

Principii de numarare

Retineti ca:

• P (n, r) este numarul de siruri (sau r-permutari) de forma 〈A1, . . . , Ar〉 unde A1,. . . , Ar sunt elemente distincte dintr-o multime cu n elemente. Formula de calcul

este P (n, r) =n!

(n− r)!= n · (n− 1) · . . . · (n− r + 1)

• C(n, r) este numarul de submultimi cu r elemente al unei multimi cu n elemente.

Formula de calcul este C(n, r) =n!

r!(n− r)!

• In total, o multime cu n elemente are 2n submultimi.

Exercitii rezolvate

1. Fie L multimea literelor {A,B,C,D,E}.

(a) Cate siruri de 7 litere din L exista?

(b) Cate siruri de 9 litere din L contin A de exact 2 ori si B de exact 3 ori?

(c) Cate siruri de 6 litere din L contin A de cel putin 2 ori si B de cel putin 2ori?

Raspuns: Mai ıntai, observam ca L are 5 litere.

(a) _ _ _ _ _ _ _: cele 7 pozitii trebuiesc completate cu litere din L:Fiecare pozitie poate fi completata ın 5 feluri.

Conform regulii produsului, avem 57 posibilitati de a construi sirul de 7litere ⇒ 57 siruri.

1

Page 2: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

(b) _ _ _ _ _ _ _ _ _: cele 9 pozitii trebuiesc completate cu

I 2 din 9 pozitii cu A ⇒ C(9, 2) posibilitati, si mai raman de completat7 pozitii

I 2 din 7 pozitii cu B ⇒ C(7, 2) posibilitati, si mai raman de completat5 pozitii cu litere diferite de A, B

I 5 pozitii ramase cu litere din {C,D,E} ⇒ 35 posibilitati (conform re-gulii produsului)

Conform regulii produsului, avem un total de C(9, 2) ·C(7, 2) ·35 posibilitati⇒ C(9,2) ·C(7,2) · 35 siruri.

(c) Mai ıntai, identificam toate cazurile distincte posibile:

I A de 2 ori, B de 2 ori ⇒ C(6, 2) · C(4, 2) · 32 posibilitati

I A de 2 ori, B de 3 ori ⇒ C(6, 2) · C(4, 3) · 3 posibilitati

I A de 2 ori, B de 4 ori ⇒ C(6, 2) · C(4, 4) posibilitati

I A de 3 ori, B de 2 ori ⇒ C(6, 3) · C(3, 2) · 3 posibilitati

I A de 3 ori, B de 3 ori ⇒ C(6, 3) · C(3, 3) posibilitati

I A de 4 ori, B de 2 ori ⇒ C(6, 4) · C(2, 2) posibilitati

Conform regulii sumei, numarul total de astfel de siruri este

C(6, 2) · C(4, 2) · 32 + C(6, 2) · C(4, 3) · 3 + C(6, 2) · C(4, 4)+

C(6, 3) · C(3, 2) · 3 + C(6, 3) · C(3, 3) + C(6, 4) · C(2, 2)

2. Fie M = {1, 2, 3, 4, A,B,C,D,E, F,G}.

(a) Cate submultimi ale lui M contin 2 cifre si 3 litere?

(b) Cate submultimi ale lui M contin litera A sau cifra 4?

Raspuns

(a) Numaram ın cate feluri putem construi o multime de forma X ∪ Y undeX ⊆ {1, 2, 3, 4} are 2 cifre, si Y ⊆ {A,B,C,D,E, F,G} are 3 litere.

Pentru X avem de ales 2 din 4 cifre ⇒ C(4, 2) posibilitati.

Pentru Y avem de ales 3 din 7 litere ⇒ C(7, 3) posibilitati.

In total, sunt C(4,2) ·C(7,3) de astfel de submultimi.

2

Page 3: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

(b) Aceasta problema se rezolva cu principiul incluziunii si excluziunii. Numarulcautat este N1 +N2 −N3 unde

• N1 este numarul submultimilor care continA; Orice astfel de submultimeeste {A} ∪X unde X ⊆ {1, 2, 3, 4, B, C,D,E, F,G}, deci N1 = 210.

• N2 este numarul submultimilor care contin 4; Orice astfel de submultimeeste {4} ∪X unde X ⊆ {1, 2, 3, A,B,C,D,E, F,G}, deci N2 = 210.

• N3 este numarul submultimilor care contin A si 4; Orice astfel desubmultime este {A, 4} ∪ X unde X ⊆ {1, 2, 3, B, C,D,E, F,G}, deciN2 = 29.

⇒ numarul cautat este 210 + 210 − 29 = 3 · 29 = 1536.

3. Sa se rezolve ecuatia P (n, 2) = 56.

Rezolvare: P (n, 2) = n · (n − 1), deci avem de rezolvat n(n − 1) = 56 ⇒n2 − n− 56 = 0

n =1±√

1 + 4 · 56

2=

1±√

225

2=

1± 15

2

Rezulta ca n = 8 sau n = −7. Deoarece, din punct de vedere combinatorial, nnu trebuie sa fie negativ, rezulta ca n = 8.

4. Sa se rezolve ecuatia 4 · C(n, 2) = P (n, 3).

Rezolvare: Avem de rezolvat ecuatia

4 · n(n− 1)

2= n(n− 1)(n− 2)⇒ 2n(n− 1)− 2n(n− 1)(n− 2) = 0

⇒ 2n(n− 1)(3− n) = 0⇒ n = 0 sau n = 1 sau n = 3.

5. Cate numere cuprinse ıntre 10 si 2188 inclusiv

(a) Sunt divizibile cu 5 sau 7?

(b) Sunt divizibile cu 5 dar nu sunt divizibile cu 7?

(c) Nu sunt divizibile nici cu 5 nici cu 7?

Raspuns: Aceasta problema se rezolva aplicand principiul incluziunii si exclu-ziunii. Fie M = {n | 10 ≤ n ≤ 2188}, A = {n ∈ M | n este divizibil cu 5},B = {n ∈ M | n este divizibil cu 7}, si C = {n ∈ M | n este divizibil cu 5 si cu7, adica cu 35}.

3

Page 4: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Deasemenea, fie N1 numarul elementelor lui M divizibile cu 5 sau 7, N2 numarulcelor divizibile cu 5 dar nu cu 7, si N3 numarul celor care nu sunt divizibile nicicu 5 nici cu 7. Avem de calculat N1, N2 si N3.

CA B

M

N1 = |C|N2 = |A| − |C|N3 = |M | − (|A|+ |B| − |C|)

Ar trebui sa stiti ca daca L ≤ R atunci

• Multimea {n | L ≤ n ≤ R} are R− L+ 1 elemente.Deci |M | = 2188− 10 + 1 = 2179.

• Daca p > 0 atunci multimea multiplilor lui p cuprinsi ıntre L si R este ∅daca dL/pe > bR/pc, si {p · d | dL/pe ≤ d ≤ bR/pc} ın caz contrar. Deci,numarul multiplilor de p din multimea {n | L ≤ n ≤ R} este

max(0, bR/pc − dL/pe+ 1)

In particular, |A| = b2188/5c − d10/5e + 1 = 437 − 2 + 1 = 436, |B| =b2188/7c−d10/7e+1 = 312−2+1 = 311, |C| = b2188/35c−d10/35e+1 =62− 1 + 1 = 62.

Deci raspunsurile sunt:

(a) N1 = |C| = 62

(b) N2 = |A| − |C| = 436− 62 = 374

(c) N3 = |M | − (|A|+ |B| − |C|) = 2179− (436 + 311− 62) = 1494

6. Fie n > 0. Cate functii surjective exista de la o multime cu n + 1 elemente la omultime cu n elemente?

Raspuns: Trebuie sa numaram ın cate feluri putem defini o functie surjectivaf : A → B cand |A| = n + 1 si |B| = n. Se observa ca f este surjectiva daca sinumai daca

• Doua elemente diferite a1, a2 ∈ A sunt mapate la acelasi element b ∈ B.

• Elementele din a ∈ A\{a1, a2} sunt mapate la elemente diferite din B \{b}.

4

Page 5: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Deci pentru a defini functia surjectiva f trebuie sa alegem:

• Doua elemente diferite a1, a2 ∈ A. Sunt C(n + 1, 2) posibilitati (fiindca Aare n+ 1 elemente).

• Un element b ∈ B pentru care f(a1) = f(a2) = b. Sunt n posibilitati.

• Pentru fiecare a ∈ A− {a1, a2} (care are n− 1 elemente) un element diferitdin A− {a} (care are n− 1 elemente). Sunt (n− 1)! posibilitati.

Conform regulii produsului, ın total exista

C(n+ 1, 2) · n · (n− 1)! = C(n+ 1, 2) · n! =(n+ 1)! · n

2

7. Denis are 6 margele rosii si 8 margele verzi. In cate feluri poate ınsira Deniscele 14 margele pe o ata daca prima margea din sirag trebuie sa fie rosie, si estepermis sa se puna cel mult o margea verde ıntre doua margele rosii?

R ? ? ? ? ? ? ? ? ? ? ? ? ?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Sugestie: aplicati regula produsului numarand cate posibilitati aveti pentru plasareaurmatoarei margele rosii ın raport cu margeaua rosie precedenta.

Rezolvare: Intrucat la pozitia p1 = 1 este margea rosie, trebuie sa numaramın cate feluri putem alege pozitiile celorlalte 5 margele rosii din multimea {2, 3,4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}. Fie p2 < p3 < p4 < p5 < p6 pozitiile acestormargele. Deoarece putem avea cel mult o margea verde ıntre 2 margele rosii,rezulta ca

• p2 ∈ {p1 + 1, p1 + 2} = {2, 3}, deci avem 2 valori posibile pentru p2

• p3 ∈ {p2 + 1, p2 + 2} ⊆ {3, 4, 5}, deci avem 2 valori posibile pentru p3

• p4 ∈ {p3 + 1, p3 + 2} ⊆ {4, 5, 6, 7}, deci avem 2 valori posibile pentru p4

• p5 ∈ {p4, p4 + 1} ⊆ {5, 6, 7, 8, 9}, deci avem 2 valori posibile pentru p5

• p6 ∈ {p5, p5 + 1} ⊆ {6, 7, 8, 9, 10, 11}, deci avem 2 valori posibile pentru p6

Conform regulii produsului, exista 25 = 32 posibilitati de a alege pozitiile p2, p+3, p4, p5, p5. Deci, Denis poate ınsira margelele ın 32 feluri.

5

Page 6: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Exercitii propuse (Set 1)

1. Cate submultimi cu numar par de elemente are o multime cu 5 elemente?

2. Cate permutari are multimii {1, 2, 3, 4, 5} au primul element mai mic decat aldoilea element?

3. Cate submultimi ale multimii {a, b, c, d, 1, 2, 3} contin cel putin o litera si celputin o cifra?

4. Cate functii surjective exista de la o multime cu n+ 2 elemente la o multime cun elemente?

5. Fie M multimea numerelor cuprinse ıntre 20 si 723 inclusiv.

(a) Cate elemente are multimea M?

(b) Cate numere din M sunt divizibile cu 2 sau 17?

(c) Cate numere din M sunt divizibile cu 2 dar nu sunt divizibile cu 17?

6. Un robotel plasat ın originea cu coordonatele (0,0) poate face doar doua operatii:sa mearga 1 unitate la dreapta, sau 1 unitate ın sus. In cate feluri se poatedeplasa robotelul din origine la punctul de coordonate (m, n) daca m,n ∈ N?Observati ca, ın total, robotelul trebuie sa faca m+ n operatii.

sus

dreapta(0,0)

7. La o tombola participa 15 barbati si 10 femei si se acorda 3 premii de 100 lei si2 premii de 200 lei. Se stie ca o persoana poate castiga cel mult un premiu.

(a) In cate feluri se pot acorda cele 5 premii?

(b) In cate feluri se pot acorda cele 5 premii daca se stie ca exact 2 barbati suntcastigatori?

(c) In cate feluri se pot acorda cele 5 premii daca se stie ca nici o femeie nu acastigat un premiu de 100 lei?

6

Page 7: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Generarea si ordonarea permutarilor

• Permutarile unei multimi A = {1, 2, . . . , n} se pot ordona lexicografic. De exem-plu, ordonarea lexicografica a permutarilor multimii A = {1, 2, 3} este

Rang:Permutare: 〈1, 2, 3〉 〈1, 3, 2〉 〈2, 1, 3〉 〈2, 3, 1〉 〈3, 1, 2〉 〈3, 2, 1〉

0 1 2 3 4 5

Rangul unei permutari ın ordonare lexicografica este pozitia permutarii ın enu-merarea lexicografica. Prima permutare are rangul 0.

• In general, daca A = {a1, a2, . . . , an} cu a1 < a2 < . . . < an atunci rangulpermutarii 〈ap1 , ap2 , . . . , apn〉 a lui A este egal cu rangul permutarii 〈p1, p2, . . . , pn〉a multimii {1, 2, . . . , n}.

• Daca 〈p1, p2, . . . , pn〉 este permutare a multimii {1, 2, . . . , n} atunci

rang〈p1, p2, . . . , pn〉 = (p1 − 1) · (n− 1)! + rang〈p2, . . . , pn〉

• Daca 〈p1, p2, . . . , pn〉 este permutare a multimii {1, 2, . . . , n} cu rangul r atunci

p1 = p1 =

⌊r

(n− 1)!

⌋+ 1

Exemple de calcul al rangului unei permutari ın ordine lexicografica:

1. Rangul permutarii 〈4, 1, 3, 2, 5〉 a multimii {1, 2, 3, 4, 5} este:

rang〈4, 1, 3, 2, 5〉 = (4− 1) · 4! + rang〈1

1,3

3,2

2,4

5〉 = 72 + rang〈1, 3, 2, 4〉 = 72 + (1−1) ·(4−1)!+rang〈

2

3,1

2,3

4〉 = 72+rang〈2, 1, 3〉 = 72+(2−1) ·(3−1)!+rang〈1

1,2

3〉 =

72+2+rang〈1, 2〉 = 74+(1−1) · (2−1)!+rang〈1

2〉 = 75+rang〈1〉 = 74+0 = 74.

2. Rangul permutarii 〈d, b, a, c〉 a multimii A = {1a,2

b,3c,

4

d} cu a < b < c < d este:

rang〈4

d,2

b,1a,

3c〉 = rang〈4, 2, 1, 3〉 = (4−1)·(4−1)!+rang〈2, 1, 3〉 = 18+(2−1)·(3−

1)!+rang〈1

1,2

3〉 = 18+2+rang〈1, 2〉 = 20+(1−1)·(2−1)!+rang〈1

2〉 = 20+0 = 20.

Exemple de calcul al unei permutari care are un rang dat:

7

Page 8: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

1. Ce permutare a lui {1, 2, 3, 4, 5} are rangul 73?

Trebuie calculata permutarea 〈p1, p2, p3, p4, p5〉 lui {1, 2, 3, 4, 5} astfel ıncat

rang〈p1, p2, p3, p4, p5〉 = 73.

• q =⌊734!

⌋+ 1 = 4⇒ p1 = 4 si ramane de calculat permutarea 〈p2, p3, p4, p5〉

multimii {1

1,2

2,3

3,4

5} cu rangul 73− (q − 1) · 4! = 73− 72 = 1

• q =⌊

13!

⌋+ 1 = 1 ⇒ p2 = 1 si ramane de calculat permutarea 〈p3, p4, p5〉

multimii {1

2,2

3,3

5} cu rangul 1− (q − 1) · 3! = 1

•⌊

12!

⌋+ 1 = 1 ⇒ p3 = 2 si ramane de calculat permutarea 〈p4, p5〉 multimii

{1

3,2

5} cu rangul 1− (q − 1) · 2! = 1

•⌊

11!

⌋+ 1 = 2 ⇒ p4 = 5 si ramane de calculat permutarea 〈p5〉 multimii {

1

3}cu rangul 1− (q − 1) · 1! = 0.Rezulta ca p5 = 3.

Deci permutarea lui 〈1, 2, 3, 4, 5〉 cu rangul 73 este 〈4, 1, 2, 5, 3〉.

Exemple de calcul al permutarii care urmeaza dupa o permutare data ın ordine lexi-cografica:

1. Ce permutare urmeaza dupa permutarea 〈2, 1, 3, 8, 5, 6, 9, 7, 3〉 ın ordine lexi-cografica?

Raspuns:

• Mai ıntai detectam cel mai lung sufix descrescator al permutarii: 9,7,3.

• Apoi permutam elementul dinaintea sufixului (care este 6) cu cel mai micelement din sufix care este mai mare decat 6 (adica 7):

〈2, 1, 3, 8, 5, 6, 9, 7, 3〉 → 〈2, 1, 3, 8, 5, 7, 9, 6, 3〉

• In final, inversam ordinea elementelor din sufix, ıncat sa apara ın ordinecrescatoare:

〈2, 1, 3, 8, 5, 7, 9, 6, 3〉 → 〈2, 1, 3, 8, 5, 7, 3, 6, 9〉

2. Ce permutare urmeaza dupa 〈2, 3, 1, 5, 4〉 ın ordine lexicografica?

Raspuns: 〈4, 1, 3, 2, 5〉

8

Page 9: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

3. Ce permutare urmeaza dupa 〈5, 4, 3, 2, 1〉 ın ordine lexicografica?

Raspuns: nici una.

4. Ce permutare urmeaza dupa 〈1, 3, 2, 7, 6, 5, 4〉 ın ordine lexicografica?

Raspuns: 〈1, 3, 4, 2, 5, 6, 7〉.

Generarea si ordonarea permutarilor cu repetitie

Retineti ca

• O r-permutare cu repetitie a unei multimi ordonate A = {A1, . . . , An} pentrucare presupunem ca A1 < A2 < . . . < An, este

〈Ap1 , Ap2 , . . . , Apr〉 ın care p1, . . . , pr ∈ {1, . . . , n} nu trebuie sa fie distincte

• Exista nr permutari cu repetitie ale lui A = {A1, . . . , An}, iar acestea pot fi or-donate lexicografic. De exemplu, A = {a, b, c} are noua 2-permutari cu repetitie,iar ordonarea lor lexicografica este

Rang:Permutare cu repetitie: 〈a, a〉 〈a, b〉 〈a, c〉 〈b, a〉 〈b, b〉 〈b, c〉 〈c, a〉 〈c, b〉 〈c, c〉

0 1 2 3 4 5 6 7 8

• Rangul unei r-permutari cu repetitie 〈Ap1 , Ap2 , . . . , Apr〉 a lui A = {A1, . . . , An}ın ordine lexicografica este valoarea lui q1q2 . . . qr ın baza n, unde qi = pi − 1pentru toti i.

• Permutarea cu repetitie a multimii A = {A1, . . . , An} care are rangul k este〈Aq1+1, Aq2+1, . . . , Aqr+1〉 unde (q1q2 . . . qr)n este reprezentarea lui k ın baza n,folosind r cifre.

Exemple

1. Care este rangul 3-permutarii cu repetitie 〈b, a, a, d〉 a multimii A = {0a,1

b,2c,

3

d,4e}

ın ordine lexicografica?

Raspuns: rang〈b, a, a, d〉 = 10035 = 1 · 53 + 3 = 128.

9

Page 10: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

2. Care este 4-permutarea cu repetitie a lui A = {0a,1

b,2c,

3

d,4e,

5

f} cu rangul 53?

Raspuns: A are 6 elemente, deci trebuie sa calculam reprezentarea lui 29 ınbaza 6 folosind r = 4 cifre.

53 = 1 · 62 + 2 · 6 + 5 · 1⇒ 53 = 01256 ⇒ 4-permutarea cu repetitie cautata este〈a, b, c, f〉.

Generarea si ordonarea combinarilor

O combinare a unei multimi este o submultime a unei multimi.

• Orice submultime a unei multimi ordonate A = {A1, A2, . . . , An} are o reprezen-tare unica ca sir de n biti. Valoarea ın baza 2 a acestui sir se numeste rangulbinar al submultimii respective: De exemplu, submultimile lui A = {a, b, c} aurangurile binare indicate ın tabelul de mai jos:

sir binarrang binar c b a submultime

0 0 0 0 ∅1 0 0 1 {a}2 0 1 0 {b}3 0 1 1 {a, b}4 1 0 0 {c}5 1 0 1 {a, c}6 1 1 0 {b, c}7 1 1 1 {a, b, c}

Observati ca:

I Coloanele tabelului sunt enumerate ın ordine descrescatoare, adicaAn, An−1, . . . , A2, A1.

I Un sir binar bn . . . b2b1 reprezinta submultimea {Ai | bi = 1}.

Enumerarea submultimilor lui A ın ordine crescatoare a rangului binar se numesteordonare binara.

• Submultimile unei multimi ordonate A = {A1, A2, . . . , An} pot fi ordonate si lexi-cografic. De exemplu, enumerarea lexicografica a submultimilor lui A = {a, b, c}este ∅, {a}, {a, b}, {a, b, c}, {a, c}, {b}, {b, c}, {c}.

10

Page 11: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

• Submultimea care urmeaza dupa {Ap1 , Ap2 , . . . , Apk} ın ordine lexicografica secalculeaza astfel:

1. Daca {Ap1 , Ap2 , . . . , Apk} = ∅ atunci submultimea urmatoare este {A1}.2. Daca {Ap1 , Ap2 , . . . , Apk} = {An} atunci nu exista submultime urmatoare.

3. In caz contrar, daca pk = n atunci submultimea urmatoare este{Aq1 , Aq2 , . . . , Aqk−1

} unde qi = pi pentru 1 ≤ i < k − 1 si qk−1 = pk−1 + 1.

4. In caz contrar, submultimea urmatoare este {Ap1 , Ap2 , . . . , Apk , Apk+1}.

Exercitii

1. Sa se calculeze rangul binar al submultimii {b, c, e} al multimii {a, b, c, d, e, f}.Raspuns:

Submultime f e d c b a{a, c, e} 0 1 0 1 1 0

⇒ rangul binar al lui {a, c, e} este 0101102 = 24 + 22 + 2 = 22.

2. Sa se determine submultimea lui {1, 2, 3, 4, 5} cu rangul 11 ın ordonarea binara.

Raspuns: 11 = 1 · 23 + 1 · 2 + 1⇒ reprezentarea lui 11 ın baza 2 cu 5 biti este010112, deci

5 4 3 2 1 Submultime0 1 0 1 1 {1, 2, 4}

Submultimea cautata este {1, 2, 4}.

3. Sa se determine submultimile lui A = {a, b, c, d, e} care urmeza, ın ordine lexi-cografica, dupa

(a) ∅(b) {a, b, e}(c) {b, c}

Raspuns:

(a) Submultimea care urmeaza dupa ∅ este {A1} = {a}.(b) {a, b, e} = {A1, A2, A5} ⇒ dupa ea urmeaza {A1, A3} = {a, c}.(c) {b, c} = {A2, A3} ⇒ dupa ea urmeaza {A2, A4} = {b, d}.

11

Page 12: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Tehnici avansate de numarare

Se urmareste

I Verificarea abilitatilor de gasire a unei relatii de recurenta pentru rezolvarea unorprobleme concrete.

I Utilizarea corecta a tehnicilor de rezolvare a relatiilor de recurenta liniara omogenasi neomogena.

Exercitii rezolvate

1. Fie an numarul de siruri de n biti care nu contin trei zerouri consecutive.

(a) Sa se determine o formula de calcul pentru an.

(b) Care este valoarea lui a6?

Raspuns:

(a) Fie sn un sir de n biti care nu contine 000. Numaram ın cate feluri putemconstrui un astfel de sir.

Daca n = 0, sn poate fi doar sirul vid, care nu contine 000. Deci a0 = 1.

Daca n = 1 atunci sn ∈ {0, 1} si sn nu contine 000 ⇒ a1 = 2.

Daca n = 2 atunci sn ∈ {00, 01, 10, 11} nu contine 000 ⇒ a2 = 4.

Daca n ≥ 3 atunci distingem urmatoarele cazuri distincte:

C1. sn = 1sn−1. In acest caz sn−1 nu trebuie sa contina 000⇒ an−1 posibilitati.

C2. sn = 01sn−2. In acest caz sn−2 nu trebuie sa contina 000⇒ an−2 posibilitati.

C3. sn = 001sn−3. In acest caz sn−3 nu trebuie sa contina 000⇒ an−3 posibilitati.

Conform regulii sumei, pentru n ≥ 3 avem ın total an−1 + an−2 + an−3posibilitati de a construi un sir sn.

Am dedus relatia de recurenta liniara:

a0 = 1, a1 = 2, a2 = 4, an = an−1 + an−2 + an−3 daca n ≥ 3.

(b) a3 = a0 + a1 + a2 = 7a4 = a1 + a2 + a3 = 13a5 = a2 + a3 + a4 = 24a6 = a3 + a4 + a5 = 44

12

Page 13: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

2. Fie zn numarul de siruri de n biti care contin trei zerouri consecutive.

(a) Sa se determine o formula de calcul pentru zn.

(b) Sa se calculeze valoarea lui z6.

Raspuns:

(a) Fie sn un sir de lungime n, si an numarul de siruri de lungime n care contin000. Observam ca:

• Exista 2n astfel de siruri sn.

• sn satisface exact una din urmatoarele conditii: sn contine 000, sau snnu contine 000. Rezulta ca 2n = an + zn.

• Din exercitiul precedent stim cun sa calculam an pentru n ≥ 0.

Deci zn = 2n − an unde a0 = 1, a1 = 2, a2 = 4 si an = an−1 + an−2 + an−3pentru n ≥ 3.

(b) z6 = 26 − a6 = 64− 44 = 20.

3. Fie An numarul de feluri ın care poate fi achitata o suma de n lei daca aveti ladispozitie bancnote de 1 leu, 5 lei si 10 lei (ordinea ın care se platesc bancnotelenu conteaza). De exemplu, A12 = deoarece 12 lei pot fi achitati ın 4 feluri:

1) 1× 10LEI + 2× 1LEU

2) 2× 5LEI + 2× 1LEU

3) 1× 5LEI + 7× 1LEU

4) 12× 1LEU

(a) Sa se deduca o formula recursiva pentru calculul lui An.

(b) Folositi formula pe care ati descoperit-o pentru a calcula A12.

Raspuns:

(a) Fie S o multime de tipuri de bancnote posibile pentru a achita o suma,adica S ⊆ {1, 5, 10}. Deasemenea, fie ASn ın cate feluri se pot achita n lei

folosind toate tipurile de bancnote din S si doar acestea. De exemplu, A{1,10}n

reprezinta ın cate feluri se pot achita n lei folosind cel putin 1 bancnota de1 leu, cel putin 1 bancnota de 5 lei, si doar bancnote de 1 leu si de 5 lei.

13

Page 14: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Este evident ca A{k}n =

{1 daca n este multiplu de k,0 ın caz contrar.

Conform regulii sumei, avem:

• An = A{1,5,10}n + A

{1,5}n + A

{1,10}n + A

{5,10}5 + A

{1}n + A

{5}n + A

{10}n

• Daca S are cel putin 2 elemente si k ∈ S atunci

ASn =

{0 daca n < k,

ASn−k + AS−{k}n−k daca n ≥ k.

(b) A12 = A{1,5,10}12 + A

{1,5}12 + A

{1,10}12 + A

{5,10}5 + A

{1}12 + A

{5}12 + A

{10}12 .

Deoarece 12 nu este multiplu de 5 si nici de 10, A{5}12 = A

{10}12 = 0. Deaseme-

nea, A{1}12 = 1 si A

{5,10}5 = 0 deoarece 5 < 10. Deci

A12 = A{1,5,10}12 + A

{1,5}12 + A

{1,10}12 + 1.

A{1,5,10}12 = A

{1,5,10}2 + A

{1,5}2 = 0 + 0 = 0.

A{1,5}12 = A

{1,5}7 + A

{1}7 = A

{1,5}7 + 1 = A

{1,5}2 + A

{1}2 + 1 = 0 + 1 + 1 = 2

A{1,10}12 = A

{1,10}2 + A

{1}2 = 0 + 1 = 1.

Rezulta ca A12 = 0 + 2 + 1 + 1 = 4.

4. Sa se rezolve relatia de recurenta liniara omogena

a1 = 8, a2 = 7, an = 4 · an−1 − 4 · an−2 daca n ≥ 3.

Rezolvare: Ecuatia caracteristica a relatiei de recurenta ester2 − 4 · r + 4 = 0 ⇒ r1 = r2 = 2. Deoarece 2 este radacina cu multiplicitatea 2,an este un polinom de grad 1 ınmultit cu 2n:

an = (A · n+B) · 2n for all n ≥ 1

Mai avem de calculat valorile lui A si B:

a1 =8 = (A+B) · 21 = 2 · A+ 2 ·Ba2 =7 = (2 · A+B) · 22 = 8 · A+ 4 ·B

⇒ A = −9

4, B =

25

4. Deci an = (−9n/4 + 25/4) · 2n.

14

Page 15: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

5. Sa se rezolve relatia de recurenta liniara neomogena

a1 = 14, a2 = 72, an = 4 · an−1 − 4 · an−2 + (n2 + n+ 1) · 2n daca n ≥ 3.

Rezolvare: Stim ca solutia acestei relatii de recurenta este

an = a(h)n + a(p)n

unde

• a(h)n este o solutie a relatiei de recurenta omogene

a(h)n = 4 · a(h)n−1 − 4 · a(h)n−2 ⇒ a(h)n = (A · n+B) · 2n.

• Deoarece r = 2 are multiplicitatea 2 ın ecuatia caracteristica a recurenteiomogene, iar partea neomogena este (n2 + n+ 1) · 2n, rezulta ca

a(p)n = n2(C · n2 +D · n+ E) · 2n.

Din faptul ca a(p)n = 4 · a(p)n−1− 4 · a(p)n−2 + (n2 +n+ 1) · 2n pentru toti n ≥ 3 rezulta

ca

((12C−1)n2+(6D−24C−1)n+2E−6D+14C−1) 2n = 0 pentru toti n ≥ 3.

Rezulta ca

12C − 1 = 06D − 24C − 1 = 0

2E − 6D + 14C − 1 = 0

C = 1/12D = 1/2E = 17/12

deci

an = (An+B) · 2n + n2(n2/12 + n/2 + 17/12) · 2n

= (n4/12 + n3/2 + 17n2/12 + An+B) · 2n

Din a1 = 14, a2 = 72 rezulta A = 2, B = 3, deci

an = (2n+ 3) · 2n + n2(n2/12 + n/2 + 17/12) · 2n pentru toti n ≥ 3.

15

Page 16: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

6. Sa se rezolve relatia de recurenta liniara omogena

a0 = −1, a1 = −7, an = −4 · an−1 + 5 · an−2 daca n ≥ 2.

Rezolvare: Ecuatia caracteristica a recurentei liniare este r2 + 4 r − 5 = 0 ⇒r1 = −5, r2 = 1 ⇒ an = A · (−5)n + B · 1n = A · (−5)n + B pentru toti n ≥ 0.Mai avem de calculat valorile lui A si B.

−1 = a0 = A+B−7 = a1 = 5A+B

}⇒ A = 1, B = −2⇒ an = (−5)n − 2.

Exercitii propuse (Set 2)

1. Un sir de litere din multimea {a, b, c, d} este acceptabil daca nu contine subsirulaa. Fie An multimea de siruri acceptabile de lungime n.

(a) Sa se determine o formula de calcul pentru An.

(b) Care este valoarea lui A5?

2. Un sir de litere din multimea {a, b, c, d, e} este alternant daca nu contine doualitere consecutive identice. Fie an multimea de siruri alternante de lungime n.

(a) Sa se determine o formula de calcul pentru an.

(b) Care este valoarea lui a5?

3. Fie xn numarul de siruri de n biti care nu contin subsirul 10. Sa se determine oformula de calcul pentru xn.

4. Un sir de cifre zecimale este special daca are un numar par de zerouri. Fie Snnumarul sirurilor speciale de lungime n.

(a) Sa se gaseasca o formula de calcul a lui Sn.

(b) Care este valoarea lui S6?

Structura ciclica a permutarilor

Retineti ca

16

Page 17: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

• O permutare π = 〈p1, p2, . . . , pn〉 reprezinta si functia bijectivaπ : {1, 2, . . . , n} → {1, 2, . . . , n}, π(i) = pi pentru 1 ≤ i ≤ n.

Rezulta ca putem calcula cu permutari ca functii: sa le compunem (π1 ◦ π2), sale inversam (π−1), sa le ridicam la putere (πn = π ◦ . . . ◦ π︸ ︷︷ ︸

n ori

; π0 = 〈1, 2, . . . , n〉).

• Interpretarea unei permutari π ca functie bijectiva cu ajutorul reprezentarii pozitionale:

1 2 n↓ ↓ . . . ↓

π = 〈p1 p2 . . . pn〉

• Un ciclu este o functie bijectiva π : {a1, a2, . . . , an} → {a1, a2, . . . , an} astfel ıncatπ(a1) = a2, π(a2) = a3, . . . , π(an) = a1.

I Notatia pentru un ciclu: (a1, a2, . . . , an)

I Interpretarea unui ciclu ca functie bijectiva: (a1 → a2 → . . .→ an)

• Orice permutare poate fi descompusa ıntr-o compozitie de cicluri disjuncte, nu-mita structura ciclica a permutarii respective.

• Reprezentarea permutarilor ca structuri ciclice permite studiul grupului de simetriial unor configuratii de interes (vezi Teoria lui Polya).

Exemple

1. Fie π = 〈7, 6, 5, 1, 3, 2, 4〉.

(a) Sa se indice structura ciclica si tipul permutarii π.

(b) Sa se calculeze permutarile π2 si π−1.

Raspuns: Stim ca

1 2 3 4 5 6 7↓ ↓ ↓ ↓ ↓ ↓ ↓

π = 〈7 6 5 1 3 2 4〉

(a) π are structura ciclica π = (1, 7, 4)(2, 6)(3, 5). Rezulta ca tipul permutariiπ este [0, 2, 1, 0, 0, 0, 0]

17

Page 18: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

(b)

1 2 3 4 5 6 7↓ ↓ ↓ ↓ ↓ ↓ ↓

π2 = π ◦ π = 〈4 2 3 7 5 6 1〉

1 2 3 4 5 6 7↑ ↑ ↑ ↑ ↑ ↑ ↑

π−1 = 〈7 6 5 1 3 2 4〉 = 〈4, 6, 5, 7, 3, 2, 1〉

2. Fie permutarea π = (1, 10, 3, 7, 6)(2)(4, 9)(5)(8, 12, 11).

(a) Sa se calculeze permutarile π2, π3 si π−1.

(b) Sa se indice reprezentarea pozitionala a permutarii π.

Raspuns:

(a) π2 = π ◦ π = (1, 3, 6, 10, 7)(2)(4)(9)(5)(8, 11, 12)π3 = π2 ◦ π = (1, 7, 10, 6, 3)(2)(4, 9)(5)(8)(11)(12)π−1 = (1, 6, 7, 3, 10)(2)(4, 9)(5)(8, 11, 12)

(b) π = 〈10, 2, 7, 9, 5, 1, 6, 12, 4, 3, 8, 11〉

Teoria lui Polya

Ofera criterii de numarare a tuturor configuratiilor posibile, daca se tine cont de

• grupul de simetrii al configuratiei

• cate culori se pot folosi pentru a colora configuratia respectiva.

Exemple comentate:

Ex.1 Se considera un sirag de margele cu culori dintr-o colectie dem culori. Configuratiaspatiala a siragului este

1

2

3 4

5

6

Fiecare cerculet n reprezinta pozitia n a unei margele ın sirag. Cate siraguridiferite de acest fel se pot alcatui?

18

Page 19: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Raspuns: Lema lui Burnside ne permite sa raspundem la aceasta ıntrebare.

Mai ıntai determinam operatiile care nu modifica aranjamentul spatial al acesteiconfiguratii. Multimea acestor operatii se numeste grup de simetrii al configuratiei.In acest exemplu, grupul de simetrii G este format din operatiile urmatoare:

(a) Permutarea identitate (nu muta nici o margea): (1)(2)(3)(4)(5)(6)

(b) Rotatia cu 180◦ ın jurul mijlocului segmentului 3− 4: (1,6)(2,5)(3,4)

1

2

3 4

5

6

⇒6

5

4 3

2

1

(c) Rotatia ın jurul axei verticale de simetrie: (1,5)(2,6)(3,4)

1

2

3 4

5

6

⇒5

6

4 3

1

2

19

Page 20: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

(d) Rotatia ın jurul axei orizontale de simetrie: (1,2)(3)(4)(5,6)

1

2

3 4

5

6

⇒2

1

3 4

6

5

⇒ G = { (1)(2)(3)(4)(5)(6),(1, 6)(2, 5)(3, 4),(1, 5)(2, 6)(3, 4),(1, 2)(3)(4)(5, 6)}.

Conform lemei lui Burnside, daca avem m culori disponibile numarul de siraguri

diferite de acest fel este N =1

|G|∑π∈G

|Cπ|, unde

• |G| este numarul de permutari din G,

• |Cπ| este ma unde a este numarul de cicluri al permutarii π.

Pentru siragul nostru, numarul de variante posibile este

N =1

4(|C(1)(2)(3)(4)(5)(6)|+ |C(1,6)(2,5)(3,4)|+ |C(1,5)(2,6)(3,4)|+ |C(1,2)(3)(4)(5,6)|)

=1

4

(m6 +m3 +m3 +m4

)= (m6 +m4 + 2m3)/4

Observatie: Pentru a aplica Lema lui Burnside, trebuie sa descoperiti toate simetriileunei configuratii. Lema lui Burnside se poate aplica si pentru configuratii spatiale.(Vezi exemplul urmator.)

Ex.2. In cate feluri pot fi colorate varfurile unui tetraedru regulat cu cel mult 3 culori?

Raspuns: Vom desena un tetraedru regulat cu varfurile numerotate de la 1 la4, si vom determina grupul de simetrii al configuratiei tetraedrale:

1

23

4

20

Page 21: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

• Cea mai evidenta simetrie este permutarea identitate, care nu schimbapozitia nici unui colt: (1)(2)(3)(4)

• Apoi, putem rasuci teraedrul cu 120◦ sau cu 240◦ ın jurul unei ınaltimi:

– In jurul ınaltimii din varful 1: (1)(2, 3, 4), (1)(2, 4, 3)

– In jurul ınaltimii din varful 2: (2)(1, 3, 4), (2)(1, 4, 3)

– In jurul ınaltimii din varful 3: (3)(2, 3, 4), (3)(2, 4, 3)

– In jurul ınaltimii din varful 4: (4)(1, 2, 3), (4)(1, 3, 2)

• Alt tip de simetrii rasucesc tetraedrul cu 180◦ ın jurul uneia din cele treiaxe care trec prin mijloacele a doua muchii opuse:

1

23

4

2

14

3

(1, 2)(3, 4)

1

23

4

3

41

2

(1, 3)(2, 4)

1

2

4

3 ⇒

4

32

1

(1, 4)(2, 3)

⇒ G = { (1)(2)(3)(4),(1)(2, 3, 4), (1)(2, 4, 3), (2)(1, 3, 4), (2)(1, 4, 3),(3)(1, 2, 4), (3)(1, 4, 2), (4)(1, 2, 3), (4)(1, 3, 2),(1, 2)(3, 4), (1, 3)(2, 4), (1, 4)(2, 3)}

Numarul cautat este N =1

12(m4+11m2) pentru m = 3, adica (34+11 ·32)/12 =

(81 + 99)/12 = 15.

21

Page 22: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Exercitii propuse (Set 3)

1. Cate coliere diferite cu 6 margele de cel mult 3 culori exista?

1

2

34

5

6

2. In cate feluri se pot colora muchiile unui tetraedru cu cel mult 3 culori?

1

2

3

4

5

6

3. Sa se calculeze numarul de colorari diferite a configuratiei urmatoare cu cel mult2 culori.

1

2

3 4

5

6

7

Polya a descoperit si o metoda de calcul al colorarilor diferite al unei configuratii C,daca se precizeaza de cate ori se foloseste fiecere culoare:

• La fel ca si pentru Lema lui Burnside, mai ıntai se determina grupul de simetriiG al configurtiei C.

• Apoi se calculeaza inventarul de modele al configuratiei C pentru m culori.Daca configuratia C are n componente care se coloreaza cu cel mult m culoriy1, y2, . . . , ym, atunci inventarul de modele este polinomul FG(y1, . . . , ym) cucoeficienti ıntregi si variabilele y1, y2, . . . , yn astfel ıncat

FG(y1, . . . , ym) =∑

k1,...,km

a(k1,k2,...,km)yk11 y

k22 . . . ykmm

unde fiecare a(k1,...,km) este numarul de colorari diferite a configuratiei C cu

22

Page 23: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

k1 componente colorate cu culoarea y1k2 componente colorate cu culoarea y2. . .km componente colorate cu culoarea ym.

FG(y1, . . . , ym) se poate calcula ın 2 pasi:

P1. Mai ıntai se determina polinomul ın x1, . . . , xn:

PG(x1, x2, . . . , xn) =1

|G|∑π∈G

Mπ(x1, x2, . . . , xn)

unde Mπ(x1, x2, . . . , xn) = xλ11 xλ22 . . . xλnn si permutarea π are tipul

[λ1, λ2, . . . , λn].

P2. FG(y1, y2, . . . , ym) = PG

(m∑i=1

yi,m∑i=1

y2i , . . . ,m∑i=1

yni

)Altfel spus, FG(y1, y2, . . . , ym) we obtine din PG(x1, x2, . . . , xn) ınlocuind

x1 cu y1 + y2 + . . .+ ymx2 cu y21 + y22 + . . .+ y2m. . .xn cu yn1 + yn2 + . . .+ ynm

De multe ori, calculul inventarului de modele FG(y1, y2, . . . , ym) este foartecostisitor. Se recomanda folosirea unui sistem de calcul simbolic (de exem-plu, Mathematica) pentru efectuarea de calcule cu aceste polinoame.

Exemplu ilustrat:

Ex.3. Doua molecule sunt izomeri daca au aceeasi compozitie de atomi, dar au structurispatiale diferite. Molecula de naftalina are 10 atomi de carbon dispusi ın colturileunei structuri dublu hexagonale, iar 8 din cei 10 atomi, situati la pozitiile nu-merotate ın figura de mai jos, sunt legati la cate un atom de hidrogen:

12

34

56

78

(a) Naftolul se obtine ınlocuind unul din atomii de hidrogen ai naftalinei de lapozitiile numerotate cu un grup hidroxil (OH). Cati izomeri de naftol exista?

23

Page 24: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

(b) Tetrametilnaftalina se obtine ınlocuind patru din atomii de hidrogen ai naf-talinei de la pozitiile numerotate cu grupuri de metil (CH3). Cati izomeride tetrametilnaftalina exista?

Raspuns: Raspunsurile la ambele ıntrebari pot fi gasite calculand inventarul de modeleal moleculei de naftalina, careia i se coloreaza nodurile numerotate de la 1 la 8 cu douaculori: rosu (r) si galben (g). Vom considera ca pozitiile colorate cu rosu sunt cele cucarbon legat la hidrogen. Atunci

• Coeficientul lui r7g este numarul de izomeri de naftol.

• Coeficientul lui r4g4 este numarul de izomeri de tetrametilnaftalina.

Se vede usor ca grupul de simetrii al naftalinei este

G = { (1)(2)(3)(4)(5)(6)(7)(8), (1, 5)(2, 6)(3, 7)(4, 8),(1, 4)(2, 3)(5, 8)(6, 7), (1, 8)(2, 7)(3, 6)(4, 5)}

Rezulta ca PG(x1, x2, x3, x4, x5, x6, x7, x8) = 14

(x81 + 3 · x42), deci

FG(r, g) =1

4

(r + g)8 + 3 · (r2 + g2)4

)= r8 + 2 r7g + 10 r6g2 + 14 r5g3 + 22 r4g4 + 14 r3g5 + . . .+ g8

Coeficientul lui r7g este 2 ⇒ sunt 2 izomeri de naftol.Coeficientul lui r4g4 este 22 ⇒ sunt 22 izomeri de tetrametilnaftalina.

Exercitii propuse (Set 4)

1. Cate coliere diferite cu 6 margele se pot forma daca se folosesc 2 margele verzi,doua galbene, si doua rosii?

1

2

34

5

6

2. In cate feluri se pot colora 2 muchii ale unui tetraedru cu rosu, una cu albastru,si 3 cu galben?

24

Page 25: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

1

2

3

4

5

6

3. Cate zaruri diferite se pot alcatui daca i se numeroteaza fetele cu numere de la 1la 6?

4. Benzenul este o hidrocarbura cu 6 atomi de carbon plasati ın varfurile unuihexagon regulat, si 6 atomi de hidrogen, fiecare legat la cate un atom de carbon.

1

2

34

5

6

(a) Cati izomeri se pot obtine daca ın molecula de benzen se ınlocuiesc doi atomide hidrogen cu doi atomi de clor?

(b) Cati izomeri se pot obtine daca ın molecula de benzen se ınlocuiesc doi atomide hidrogen cu doi atomi de clor si alti 2 atomi de hidrogen cu doi atomi debrom?

Numere Stirling

I[nk

]= numarul Stirling de cicluri: ın cate feluri pot fi puse n persoane la k mese

rotunde identice astfel ıncat nici o masa sa nu ramana neocupata.

Exemplu:[31

]= 2 deoarece sunt 2 posibilitati de a pune 3 persoane la o masa

rotunda:

1

2 3

posibilitatea 1ciclul (1, 3, 2)

1

3 2

posibilitatea 2ciclul (1, 2, 3)

25

Page 26: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

I{nk

}= numarul Stirling de multimi: ın cate feluri se poate partitiona o multime

cu n elemente ın k submultimi nevide disjuncte.

Exemplu:{32

}= 3 deoarece sunt 3 posibilitati de ımpartire ın 2 grupuri:

grup 1 grup 2posibilitatea 1 {2, 3} {1}posibilitatea 2 {1, 3} {2}posibilitatea 3 {1, 2} {3}

Formule de calcul pentru C(n, k)

•(n0

)=(nn

)= 1.

• Daca n > k > 0 atunci(nk

)=(n−1k

)+(n−1k−1

).

Triunghiul numerelor C(n, k) (sau(nk

)):(

nk

)k = 0 1 2 3 4 5 6 7 8 . . . n!

n = 0 1 11 1 1 12 1 2 1 23 1 3 3 1 64 1 4 6 4 1 245 1 5 10 10 5 1 1206 1 6 15 20 15 6 1 7207 1 7 21 35 35 21 7 1 50408 1 8 28 56 70 56 28 8 1 40320...

...

Formule de calcul pentru[nk

]•[n0

]=

{1 daca n = 00 daca n > 0

Daca n ≥ 1 atunci[n1

]= 1 si

[nn−1

]= C(n, 2) = n(n− 1)/2

• Daca n ≥ 1 si k ≥ 1 atunci[nk

]= (n− 1)

[n−1k

]+[n−1k−1

]

26

Page 27: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Triunghiul numerelor[nk

]:[

nk

]k = 0 1 2 3 4 5 6 7 8 . . . n!

n = 0 1 11 0 1 12 0 1 1 23 0 2 3 1 64 0 6 11 6 1 245 0 24 50 35 10 1 1206 0 120 274 225 85 15 1 7207 0 720 1764 1624 735 175 21 1 50408 0 5040 13068 13132 6769 1960 322 28 1 40320...

. . ....

Formule de calcul pentru{nk

}•{n1

}={nn

}= 1.

{n0

}=

{1 daca n = 0,0 daca n > 0.

Daca n > k ≥ 1 atunci{nk

}= k ·

{n−1k

}+{n−1k−1

}.

Triunghiul numerelor{nk

}:{

nk

}k = 0 1 2 3 4 5 6 7 8 . . .

n = 0 11 0 12 0 1 13 0 1 3 14 0 1 7 6 15 0 1 15 25 10 16 0 1 31 90 65 15 17 0 1 63 301 350 140 21 18 0 1 127 966 1701 1050 266 28 1... 0 1

......

......

......

.... . .

Exercitii rezolvate

1. In cate feluri se poate forma un sir de 7 caractere, daca se folosesc doar litere dinmultimea {a, b, c, d} si fiecare litera trebuie sa apara cel putin o data ın sir?

27

Page 28: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

Raspuns: Fie s un astfel de sir, si f(x) multimea pozitiilor din x unde aparelitera x ∈ {a, b, c, d}. De exemplu, daca s = aabddcb atunci f(a) = {1, 2},f(b) = {3, 7}, f(c) = {6} si f(d) = {4, 5}. Se observa ca f este o functiebijectiva de la multimea A = {a, b, c, d} la P , unde P este o partitie a multimiide pozitii {1, 2, 3, 4, 5, 6, 7} ın 4 grupuri astfel ıncat fiecare grup sa aibe cel putinun element. Stim ca

• Numarul de astfel de partitii P este numarul Stirling de multimi{74

}.

• Pentru fiecare astfel de partitie P exista 4! functii bijective de la A la P(deoarece A si P sunt multimi cu 4 elemente.)

Conform regulii produsului, exista 4! ·{74

}= 24 · 350 = 8400 astfel de functii f ,

deci 8400 astfel de siruri.

2. Fie rn,k numarul de posibilitati de a ımparti n persoane ın k grupuri disjuncte,astfel ıncat fiecare grup sa aibe cel putin 2 persoane.

Folositi un rationament combinatorial pentru a demonstra ca, daca n > k > 1,atunci rn,k = k · rn−1,k + (n− 1) · rn−2,k−1.Raspuns: Faptul ca partea dreapta este o suma de 2 termeni ne sugereaza saıncercam sa aplicam regula sumei. Distingem doua cazuri disjuncte:

Cazul 1: Persoana n face parte dintr-un grup de 2 persoane. Acest cazpoate fi descompus ın o secventa de 2 pasi: (1) alegem una din celelalten − 1 persoane care sa stea la masa cu persoana n, apoi (2) formam k − 1grupuri de cel putin 2 persoane din clee n − 2 persoane ramase. Conformregulii produsului, acest caz se poate realiza ın (n− 1) · rn−2,k−1 moduri.

Cazul 2: Persoana n face parte dintr-un grup de cel putin 3 persoane.Si acest caz poate fi descompus ın o secventa de 2 pasi: (1) formam kgrupuri de cel putin 2 persoane cu primele n−1 persoane, apoi (2) adaugampersoana n la oricare din cele k grupuri formate la primul pas. Conformregulii produsului, acest caz se poate realiza ın rn−1,k · k moduri.

Conform regulii sumei, rezulta ca

rn,k = (n− 1) · rn−2,k−1 + rn−1,k · k = k · rn−1,k + (n− 1) · rn−2,k−1.

Exercitii propuse (Set 5)

28

Page 29: Teoria Grafurilor ˘si Combinatoric a recapitularestaff.fmi.uvt.ro/~mircea.marin/lectures/TGC/recap-Combinatorica.pdf · Deci pentru a de ni funct˘ia surjectiv a ftrebuie s a alegem:

1. Folositi un rationament combinatorial (regula sumei, regula produsului) pentrua gasi o fomula simpla de calcul a numarului Stirling

[n+2n

]cand n ≥ 2.

2. Folositi un rationament combinatorial (regula sumei, regula produsului) pentrua gasi o fomula simpla de calcul a numarului Stirling

{n+2n

}cand n ≥ 2.

3. Fie A = {a, b, c, . . . , x, y, z} alfabetul de 26 caractere latine minuscule. Cate siruride 50 de caractere din A se pot forma daca fiecare litera din A trebuie sa aparacel putin o data?

4. Folositi un rationament combinatorial pentru a demonstra ca, daca n > k > 1,atunci C(n, k) = C(n− 1, k) + C(n− 1, k − 1).

29