Teoria Grafurilor şi Combinatoricărecapitulare

Principii de numărare

Reţineţi că:

• P (n, r) este numărul de şiruri (sau r-permutări) de forma 〈A1, . . . , Ar〉 unde A1,. . . , Ar sunt elemente distincte dintr-o mulţ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ărul de submulţimi cu r elemente al unei mulţimi cu n elemente.

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

r!(n− r)!

• În total, o mulţime cu n elemente are 2n submulţimi.

Exerciţii rezolvate

1. Fie L mulţimea literelor {A,B,C,D,E}.

(a) Câte şiruri de 7 litere din L există?

(b) Câte şiruri de 9 litere din L conţin A de exact 2 ori si B de exact 3 ori?

(c) Câte şiruri de 6 litere din L conţin A de cel puţin 2 ori şi B de cel puţin 2ori?

Răspuns: Mai ı̂ntâi, observăm că L are 5 litere.

(a) _ _ _ _ _ _ _: cele 7 poziţii trebuiesc completate cu litere din L:Fiecare poziţie poate fi completată ı̂n 5 feluri.

Conform regulii produsului, avem 57 posibilităţi de a construi şirul de 7litere ⇒ 57 şiruri.

1

(b) _ _ _ _ _ _ _ _ _: cele 9 poziţii trebuiesc completate cu

I 2 din 9 poziţii cu A ⇒ C(9, 2) posibilităţi, şi mai rămân de completat7 poziţii

I 2 din 7 poziţii cu B ⇒ C(7, 2) posibilităţi, şi mai rămân de completat5 poziţii cu litere diferite de A, B

I 5 poziţii rămase cu litere din {C,D,E} ⇒ 35 posibilităţi (conform re-gulii produsului)

Conform regulii produsului, avem un total de C(9, 2) ·C(7, 2) ·35 posibilităţi⇒ C(9,2) ·C(7,2) · 35 şiruri.

(c) Mai ı̂ntâi, identificăm toate cazurile distincte posibile:

I A de 2 ori, B de 2 ori ⇒ C(6, 2) · C(4, 2) · 32 posibilităţiI A de 2 ori, B de 3 ori ⇒ C(6, 2) · C(4, 3) · 3 posibilităţiI A de 2 ori, B de 4 ori ⇒ C(6, 2) · C(4, 4) posibilităţiI A de 3 ori, B de 2 ori ⇒ C(6, 3) · C(3, 2) · 3 posibilităţiI A de 3 ori, B de 3 ori ⇒ C(6, 3) · C(3, 3) posibilităţiI A de 4 ori, B de 2 ori ⇒ C(6, 4) · C(2, 2) posibilităţi

Conform regulii sumei, numărul total de astfel de şiruri 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) Câte submulţimi ale lui M conţin 2 cifre şi 3 litere?

(b) Câte submulţimi ale lui M conţin litera A sau cifra 4?

Răspuns

(a) Numărăm ı̂n câte feluri putem construi o mulţime de forma X ∪ Y undeX ⊆ {1, 2, 3, 4} are 2 cifre, şi Y ⊆ {A,B,C,D,E, F,G} are 3 litere.Pentru X avem de ales 2 din 4 cifre ⇒ C(4, 2) posibilităţi.Pentru Y avem de ales 3 din 7 litere ⇒ C(7, 3) posibilităţi.În total, sunt C(4,2) ·C(7,3) de astfel de submulţimi.

2

(b) Această problemă se rezolvă cu principiul incluziunii şi excluziunii. Numărulcăutat este N1 +N2 −N3 unde• N1 este numărul submulţimilor care conţinA; Orice astfel de submulţime

este {A} ∪X unde X ⊆ {1, 2, 3, 4, B, C,D,E, F,G}, deci N1 = 210.• N2 este numărul submulţimilor care conţin 4; Orice astfel de submulţime

este {4} ∪X unde X ⊆ {1, 2, 3, A,B,C,D,E, F,G}, deci N2 = 210.• N3 este numărul submulţimilor care conţin A şi 4; Orice astfel de

submulţime este {A, 4} ∪ X unde X ⊆ {1, 2, 3, B, C,D,E, F,G}, deciN2 = 2

9.

⇒ numărul căutat este 210 + 210 − 29 = 3 · 29 = 1536.

3. Să se rezolve ecuaţia 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 · 562

=1±√

225

2=

1± 152

Rezultă că n = 8 sau n = −7. Deoarece, din punct de vedere combinatorial, nnu trebuie să fie negativ, rezultă că n = 8.

4. Să se rezolve ecuaţia 4 · C(n, 2) = P (n, 3).Rezolvare: Avem de rezolvat ecuaţia

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. Câte numere cuprinse ı̂ntre 10 şi 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?

Răspuns: Această problemă se rezolvă aplicând principiul incluziunii şi exclu-ziunii. Fie M = {n | 10 ≤ n ≤ 2188}, A = {n ∈ M | n este divizibil cu 5},B = {n ∈ M | n este divizibil cu 7}, şi C = {n ∈ M | n este divizibil cu 5 şi cu7, adică cu 35}.

3

Deasemenea, fie N1 numărul elementelor lui M divizibile cu 5 sau 7, N2 numărulcelor divizibile cu 5 dar nu cu 7, şi N3 numărul celor care nu sunt divizibile nicicu 5 nici cu 7. Avem de calculat N1, N2 şi N3.

CA B

M

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

Ar trebui să ştiţi că dacă L ≤ R atunci

• Mulţimea {n | L ≤ n ≤ R} are R− L+ 1 elemente.Deci |M | = 2188− 10 + 1 = 2179.• Dacă p > 0 atunci mulţimea multiplilor lui p cuprinşi ı̂ntre L şi R este ∅

dacă dL/pe > bR/pc, şi {p · d | dL/pe ≤ d ≤ bR/pc} ı̂n caz contrar. Deci,numărul multiplilor de p din mulţimea {n | L ≤ n ≤ R} este

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

În 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 răspunsurile 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. Câte funcţii surjective există de la o mulţime cu n + 1 elemente la omulţime cu n elemente?

Răspuns: Trebuie să numărăm ı̂n câte feluri putem defini o funcţie surjectivăf : A → B când |A| = n + 1 şi |B| = n. Se observă că f este surjectivă dacă şinumai dacă

• Două elemente diferite a1, a2 ∈ A sunt mapate la acelaşi element b ∈ B.• Elementele din a ∈ A\{a1, a2} sunt mapate la elemente diferite din B \{b}.

4

Deci pentru a defini funcţia surjectivă f trebuie să alegem:

• Două elemente diferite a1, a2 ∈ A. Sunt C(n + 1, 2) posibilităţi (fiindcă Aare n+ 1 elemente).

• Un element b ∈ B pentru care f(a1) = f(a2) = b. Sunt n posibilităţi.• Pentru fiecare a ∈ A− {a1, a2} (care are n− 1 elemente) un element diferit

din A− {a} (care are n− 1 elemente). Sunt (n− 1)! posibilităţi.

Conform regulii produsului, ı̂n total există

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

7. Denis are 6 mărgele roşii şi 8 mărgele verzi. În câte feluri poate ı̂nşira Deniscele 14 mărgele pe o aţă dacă prima mărgea din şirag trebuie să fie roşie, şi estepermis să se pună cel mult o mărgea verde ı̂ntre două mărgele roşii?

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

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

Sugestie: aplicaţi regula produsului numărând câte posibilităţi aveţi pentru plasareaurmătoarei mărgele roşii ı̂n raport cu mărgeaua roşie precedentă.

Rezolvare: Întrucăt la poziţia p1 = 1 este mărgea roşie, trebuie să numărămı̂n câte feluri putem alege poziţiile celorlalte 5 mărgele roşii din mulţimea {2, 3,4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}. Fie p2 < p3 < p4 < p5 < p6 poziţiile acestormărgele. Deoarece putem avea cel mult o mărgea verde ı̂ntre 2 mărgele roşii,rezultă că

• 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, există 25 = 32 posibilităţi de a alege poziţiile p2, p+3, p4, p5, p5. Deci, Denis poate ı̂nşira mărgelele ı̂n 32 feluri.

5

Exerciţii propuse (Set 1)

1. Câte submulţimi cu număr par de elemente are o mulţime cu 5 elemente?

2. Câte permutări are mulţimii {1, 2, 3, 4, 5} au primul element mai mic decât aldoilea element?

3. Câte submulţimi ale mulţimii {a, b, c, d, 1, 2, 3} conţin cel puţin o literă şi celpuţin o cifră?

4. Câte funcţii surjective există de la o mulţime cu n+ 2 elemente la o mulţime cun elemente?

5. Fie M mulţimea numerelor cuprinse ı̂ntre 20 şi 723 inclusiv.

(a) Câte elemente are mulţimea M?

(b) Câte numere din M sunt divizibile cu 2 sau 17?

(c) Câte numere din M sunt divizibile cu 2 dar nu sunt divizibile cu 17?

6. Un roboţel plasat ı̂n originea cu coordonatele (0,0) poate face doar două operaţii:să meargă 1 unitate la dreapta, sau 1 unitate ı̂n sus. În câte feluri se poatedeplasa roboţelul din origine la punctul de coordonate (m, n) dacă m,n ∈ N?Observaţi că, ı̂n total, roboţelul trebuie să facă m+ n operaţii.

sus

dreapta(0,0)

7. La o tombolă participă 15 bărbaţi şi 10 femei şi se acordă 3 premii de 100 lei şi2 premii de 200 lei. Se ştie că o persoană poate câştiga cel mult un premiu.

(a) În câte feluri se pot acorda cele 5 premii?

(b) În câte feluri se pot acorda cele 5 premii dacă se ştie că exact 2 bărbaţi suntcâştigători?

(c) În câte feluri se pot acorda cele 5 premii dacă se ştie că nici o femeie nu acâştigat un premiu de 100 lei?

6

Generarea şi ordonarea permutărilor

• Permutările unei mulţimi A = {1, 2, . . . , n} se pot ordona lexicografic. De exem-plu, ordonarea lexicografică a permutărilor mulţimii 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 permutări ı̂n ordonare lexicografică este poziţia permutării ı̂n enu-merarea lexicografică. Prima permutare are rangul 0.

• În general, dacă A = {a1, a2, . . . , an} cu a1 < a2 < . . . < an atunci rangulpermutării 〈ap1 , ap2 , . . . , apn〉 a lui A este egal cu rangul permutării 〈p1, p2, . . . , pn〉a mulţimii {1, 2, . . . , n}.

• Dacă 〈p1, p2, . . . , pn〉 este permutare a mulţimii {1, 2, . . . , n} atunci

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

• Dacă 〈p1, p2, . . . , pn〉 este permutare a mulţimii {1, 2, . . . , n} cu rangul r atunci

p1 = p1 =

⌊r

(n− 1)!

⌋+ 1

Exemple de calcul al rangului unei permutări ı̂n ordine lexicografică:

1. Rangul permutării 〈4, 1, 3, 2, 5〉 a mulţimii {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 permutării 〈d, b, a, c〉 a mulţimii 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 permutări care are un rang dat:

7

1. Ce permutare a lui {1, 2, 3, 4, 5} are rangul 73?Trebuie calculată permutarea 〈p1, p2, p3, p4, p5〉 lui {1, 2, 3, 4, 5} astfel ı̂ncâtrang〈p1, p2, p3, p4, p5〉 = 73.

• q =⌊734!

⌋+ 1 = 4⇒ p1 = 4 şi rămâne de calculat permutarea 〈p2, p3, p4, p5〉

mulţimii {1

1,2

2,3

3,4

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

⌊13!

⌋+ 1 = 1 ⇒ p2 = 1 şi rămâne de calculat permutarea 〈p3, p4, p5〉

mulţimii {1

2,2

3,3

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

12!

⌋+ 1 = 1 ⇒ p3 = 2 şi rămâne de calculat permutarea 〈p4, p5〉 mulţimii

{1

3,2

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

•⌊

11!

⌋+ 1 = 2 ⇒ p4 = 5 şi rămâne de calculat permutarea 〈p5〉 mulţimii {

1

3}cu rangul 1− (q − 1) · 1! = 0.Rezultă că p5 = 3.

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

Exemple de calcul al permutării care urmează după o permutare dată ı̂n ordine lexi-cografică:

1. Ce permutare urmează după permutarea 〈2, 1, 3, 8, 5, 6, 9, 7, 3〉 ı̂n ordine lexi-cografică?

Răspuns:

• Mai ı̂ntâi detectăm cel mai lung sufix descrescător al permutării: 9,7,3.• Apoi permutăm elementul dinaintea sufixului (care este 6) cu cel mai mic

element din sufix care este mai mare decât 6 (adică 7):

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

• În final, inversăm ordinea elementelor din sufix, ı̂ncât să apară ı̂n ordinecrescătoare:

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

2. Ce permutare urmează după 〈2, 3, 1, 5, 4〉 ı̂n ordine lexicografică?Răspuns: 〈4, 1, 3, 2, 5〉

8

3. Ce permutare urmează după 〈5, 4, 3, 2, 1〉 ı̂n ordine lexicografică?Răspuns: nici una.

4. Ce permutare urmează după 〈1, 3, 2, 7, 6, 5, 4〉 ı̂n ordine lexicografică?Răspuns: 〈1, 3, 4, 2, 5, 6, 7〉.

Generarea şi ordonarea permutărilor cu repetiţie

Reţineţi că

• O r-permutare cu repetiţie a unei mulţimi ordonate A = {A1, . . . , An} pentrucare presupunem că A1 < A2 < . . . < An, este

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

• Există nr permutări cu repetiţie ale lui A = {A1, . . . , An}, iar acestea pot fi or-donate lexicografic. De exemplu, A = {a, b, c} are nouă 2-permutări cu repetiţie,iar ordonarea lor lexicografică este

Rang:Permutare cu repetiţie: 〈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-permutări cu repetiţie 〈Ap1 , Ap2 , . . . , Apr〉 a lui A = {A1, . . . , An}ı̂n ordine lexicografică este valoarea lui q1q2 . . . qr ı̂n baza n, unde qi = pi − 1pentru toţi i.

• Permutarea cu repetiţie a mulţimii 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-permutării cu repetiţie 〈b, a, a, d〉 a mulţimii A = {0a,1

b,2c,

3

d,4e}

ı̂n ordine lexicografică?

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

9

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

b,2c,

3

d,4e,

5

f} cu rangul 53?Răspuns: A are 6 elemente, deci trebuie să calculăm reprezentarea lui 29 ı̂nbaza 6 folosind r = 4 cifre.

53 = 1 · 62 + 2 · 6 + 5 · 1⇒ 53 = 01256 ⇒ 4-permutarea cu repetiţie căutată este〈a, b, c, f〉.

Generarea şi ordonarea combinărilor

O combinare a unei mulţimi este o submulţime a unei mulţimi.

•

• Orice submulţime a unei mulţimi ordonate A = {A1, A2, . . . , An} are o reprezen-tare unică ca şir de n biţi. Valoarea ı̂n baza 2 a acestui şir se numeşte rangulbinar al submulţimii respective: De exemplu, submulţimile lui A = {a, b, c} aurangurile binare indicate ı̂n tabelul de mai jos:

şir binarrang binar c b a submulţime

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}

Observaţi că:

I Coloanele tabelului sunt enumerate ı̂n ordine descrescătoare, adicăAn, An−1, . . . , A2, A1.

I Un şir binar bn . . . b2b1 reprezintă submulţimea {Ai | bi = 1}.

Enumerarea submulţimilor lui A ı̂n ordine crescătoare a rangului binar se numeşteordonare binară.

• Submulţimile unei mulţimi ordonate A = {A1, A2, . . . , An} pot fi ordonate şi lexi-cografic. De exemplu, enumerarea lexicografică a submulţimilor lui A = {a, b, c}este ∅, {a}, {a, b}, {a, b, c}, {a, c}, {b}, {b, c}, {c}.

10

• Submulţimea care urmează după {Ap1 , Ap2 , . . . , Apk} ı̂n ordine lexicografică secalculează astfel:

1. Dacă {Ap1 , Ap2 , . . . , Apk} = ∅ atunci submulţimea următoare este {A1}.2. Dacă {Ap1 , Ap2 , . . . , Apk} = {An} atunci nu există submulţime următoare.

3. În caz contrar, dacă pk = n atunci submulţimea următoare este{Aq1 , Aq2 , . . . , Aqk−1} unde qi = pi pentru 1 ≤ i < k − 1 şi qk−1 = pk−1 + 1.

4. În caz contrar, submulţimea următoare este {Ap1 , Ap2 , . . . , Apk , Apk+1}.

Exerciţii

1. Să se calculeze rangul binar al submulţimii {b, c, e} al mulţimii {a, b, c, d, e, f}.Răspuns:

Submulţime 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. Să se determine submulţimea lui {1, 2, 3, 4, 5} cu rangul 11 ı̂n ordonarea binară.Răspuns: 11 = 1 · 23 + 1 · 2 + 1⇒ reprezentarea lui 11 ı̂n baza 2 cu 5 biţi este010112, deci

5 4 3 2 1 Submulţime0 1 0 1 1 {1, 2, 4}

Submulţimea căutată este {1, 2, 4}.

3. Să se determine submulţimile lui A = {a, b, c, d, e} care urmeză, ı̂n ordine lexi-cografică, după

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

Răspuns:

(a) Submulţimea care urmează după ∅ este {A1} = {a}.(b) {a, b, e} = {A1, A2, A5} ⇒ după ea urmează {A1, A3} = {a, c}.(c) {b, c} = {A2, A3} ⇒ după ea urmează {A2, A4} = {b, d}.

11

Tehnici avansate de numărare

Se urmăreşte

I Verificarea abilităţilor de găsire a unei relaţii de recurenţă pentru rezolvarea unorprobleme concrete.

I Utilizarea corectă a tehnicilor de rezolvare a relaţiilor de recurenţă liniară omogenăşi neomogenă.

Exerciţii rezolvate

1. Fie an numărul de şiruri de n biţi care nu conţin trei zerouri consecutive.

(a) Să se determine o formulă de calcul pentru an.

(b) Care este valoarea lui a6?

Răspuns:

(a) Fie sn un şir de n biţi care nu conţine 000. Numărăm ı̂n câte feluri putemconstrui un astfel de şir.

Dacă n = 0, sn poate fi doar şirul vid, care nu conţine 000. Deci a0 = 1.

Dacă n = 1 atunci sn ∈ {0, 1} şi sn nu conţine 000 ⇒ a1 = 2.Dacă n = 2 atunci sn ∈ {00, 01, 10, 11} nu conţine 000 ⇒ a2 = 4.Dacă n ≥ 3 atunci distingem următoarele cazuri distincte:C1. sn = 1sn−1. În acest caz sn−1 nu trebuie să conţină 000⇒ an−1 posibilităţi.

C2. sn = 01sn−2. În acest caz sn−2 nu trebuie să conţină 000⇒ an−2 posibilităţi.

C3. sn = 001sn−3. În acest caz sn−3 nu trebuie să conţină 000⇒ an−3 posibilităţi.

Conform regulii sumei, pentru n ≥ 3 avem ı̂n total an−1 + an−2 + an−3posibilităţi de a construi un şir sn.

Am dedus relaţia de recurenţă liniară:

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

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

12

2. Fie zn numărul de şiruri de n biţi care conţin trei zerouri consecutive.

(a) Să se determine o formulă de calcul pentru zn.

(b) Să se calculeze valoarea lui z6.

Răspuns:

(a) Fie sn un şir de lungime n, şi an numărul de şiruri de lungime n care conţin000. Observăm că:

• Există 2n astfel de şiruri sn.• sn satisface exact una din urmatoarele condiţii: sn conţine 000, sau sn

nu conţine 000. Rezultă că 2n = an + zn.

• Din exerciţiul precedent ştim cun să calculăm an pentru n ≥ 0.Deci zn = 2

n − an unde a0 = 1, a1 = 2, a2 = 4 şi an = an−1 + an−2 + an−3pentru n ≥ 3.

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

3. Fie An numărul de feluri ı̂n care poate fi achitată o sumă de n lei dacă aveţi ladispoziţie bancnote de 1 leu, 5 lei şi 10 lei (ordinea ı̂n care se plătesc bancnotelenu contează). De exemplu, A12 = deoarece 12 lei pot fi achitaţi ı̂n 4 feluri:

1) 1× 10LEI + 2× 1LEU2) 2× 5LEI + 2× 1LEU3) 1× 5LEI + 7× 1LEU4) 12× 1LEU

(a) Să se deducă o formulă recursivă pentru calculul lui An.

(b) Folosiţi formula pe care aţi descoperit-o pentru a calcula A12.

Răspuns:

(a) Fie S o mulţime de tipuri de bancnote posibile pentru a achita o sumă,adică S ⊆ {1, 5, 10}. Deasemenea, fie ASn ı̂n câte feluri se pot achita n leifolosind toate tipurile de bancnote din S şi doar acestea. De exemplu, A

{1,10}n

reprezintă ı̂n câte feluri se pot achita n lei folosind cel puţin 1 bancnotă de1 leu, cel puţin 1 bancnotă de 5 lei, şi doar bancnote de 1 leu şi de 5 lei.

13

Este evident că A{k}n =

{1 dacă 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

• Dacă S are cel puţin 2 elemente şi k ∈ S atunci

ASn =

{0 dacă n < k,

ASn−k + AS−{k}n−k dacă 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 şi nici de 10, A{5}12 = A

{10}12 = 0. Deaseme-

nea, A{1}12 = 1 şi 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.

Rezultă că A12 = 0 + 2 + 1 + 1 = 4.

4. Să se rezolve relaţia de recurenţă liniară omogenă

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

Rezolvare: Ecuaţia caracteristică a relaţiei de recurenţă ester2 − 4 · r + 4 = 0 ⇒ r1 = r2 = 2. Deoarece 2 este rădăcină cu multiplicitatea 2,an este un polinom de grad 1 ı̂nmulţit cu 2

n:

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

Mai avem de calculat valorile lui A şi 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

5. Să se rezolve relaţia de recurenţă liniară neomogenă

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

Rezolvare: Ştim că soluţia acestei relaţii de recurenţă este

an = a(h)n + a

(p)n

unde

• a(h)n este o soluţie a relaţiei de recurenţă 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 ecuaţia caracteristică a recurenţeiomogene, iar partea neomogenă este (n2 + n+ 1) · 2n, rezultă că

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

Din faptul că a(p)n = 4 · a(p)n−1− 4 · a

(p)n−2 + (n

2 +n+ 1) · 2n pentru toţi n ≥ 3 rezultăcă

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

Rezultă că

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 rezultă A = 2, B = 3, deci

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

15

6. Să se rezolve relaţia de recurenţă liniară omogenă

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

Rezolvare: Ecuaţia caracteristică a recurenţei liniare este r2 + 4 r − 5 = 0 ⇒r1 = −5, r2 = 1 ⇒ an = A · (−5)n + B · 1n = A · (−5)n + B pentru toţi n ≥ 0.Mai avem de calculat valorile lui A şi B.

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

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

Exerciţii propuse (Set 2)

1. Un şir de litere din mulţimea {a, b, c, d} este acceptabil dacă nu conţine subşirulaa. Fie An mulţimea de şiruri acceptabile de lungime n.

(a) Să se determine o formulă de calcul pentru An.

(b) Care este valoarea lui A5?

2. Un şir de litere din mulţimea {a, b, c, d, e} este alternant dacă nu conţine douălitere consecutive identice. Fie an mulţimea de şiruri alternante de lungime n.

(a) Să se determine o formulă de calcul pentru an.

(b) Care este valoarea lui a5?

3. Fie xn numărul de şiruri de n biţi care nu conţin subşirul 10. Să se determine oformulă de calcul pentru xn.

4. Un şir de cifre zecimale este special dacă are un număr par de zerouri. Fie Snnumărul şirurilor speciale de lungime n.

(a) Să se găsească o formulă de calcul a lui Sn.

(b) Care este valoarea lui S6?

Structura ciclică a permutărilor

Reţineţi că

16

• O permutare π = 〈p1, p2, . . . , pn〉 reprezintă şi funcţia bijectivăπ : {1, 2, . . . , n} → {1, 2, . . . , n}, π(i) = pi pentru 1 ≤ i ≤ n.Rezultă că putem calcula cu permutări ca funcţii: să le compunem (π1 ◦ π2), săle inversăm (π−1), să le ridicăm la putere (πn = π ◦ . . . ◦ π︸ ︷︷ ︸

n ori

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

• Interpretarea unei permutări π ca funcţie bijectivă cu ajutorul reprezentării poziţionale:

1 2 n↓ ↓ . . . ↓

π = 〈p1 p2 . . . pn〉

• Un ciclu este o funcţie bijectivă π : {a1, a2, . . . , an} → {a1, a2, . . . , an} astfel ı̂ncâtπ(a1) = a2, π(a2) = a3, . . . , π(an) = a1.

I Notaţia pentru un ciclu: (a1, a2, . . . , an)

I Interpretarea unui ciclu ca funcţie bijectivă: (a1 → a2 → . . .→ an)

• Orice permutare poate fi descompusă ı̂ntr-o compoziţie de cicluri disjuncte, nu-mită structură ciclică a permutării respective.

• Reprezentarea permutărilor ca structuri ciclice permite studiul grupului de simetriial unor configuraţii de interes (vezi Teoria lui Pólya).

Exemple

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

(a) Să se indice structura ciclică şi tipul permutării π.

(b) Să se calculeze permutările π2 şi π−1.

Răspuns: Ştim că

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

π = 〈7 6 5 1 3 2 4〉

(a) π are structura ciclică π = (1, 7, 4)(2, 6)(3, 5). Rezultă că tipul permutăriiπ este [0, 2, 1, 0, 0, 0, 0]

17

(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) Să se calculeze permutările π2, π3 şi π−1.

(b) Să se indice reprezentarea poziţională a permutării π.

Răspuns:

(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

Oferă criterii de numărare a tuturor configuraţiilor posibile, dacă se ţine cont de

• grupul de simetrii al configuraţiei

• câte culori se pot folosi pentru a colora configuraţia respectivă.

Exemple comentate:

Ex.1 Se consideră un şirag de mărgele cu culori dintr-o colecţie dem culori. Configuraţiaspaţială a şiragului este

1

2

3 4

5

6

Fiecare cerculeţ n reprezintă poziţia n a unei mărgele ı̂n şirag. Câte şiraguridiferite de acest fel se pot alcătui?

18

Răspuns: Lema lui Burnside ne permite să răspundem la această ı̂ntrebare.

Mai ı̂ntâi determinăm operaţiile care nu modifică aranjamentul spaţial al acesteiconfiguraţii. Mulţimea acestor operaţii se numeşte grup de simetrii al configuraţiei.În acest exemplu, grupul de simetrii G este format din operaţiile următoare:

(a) Permutarea identitate (nu mută nici o mărgea): (1)(2)(3)(4)(5)(6)

(b) Rotaţia 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) Rotaţia ı̂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

(d) Rotaţia ı̂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, dacă avem m culori disponibile numărul de şiraguri

diferite de acest fel este N =1

|G|∑π∈G

|Cπ|, unde

• |G| este numărul de permutări din G,• |Cπ| este ma unde a este numărul de cicluri al permutării π.

Pentru şiragul nostru, numărul 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

Observaţie: Pentru a aplica Lema lui Burnside, trebuie să descoperiţi toate simetriileunei configuraţii. Lema lui Burnside se poate aplica şi pentru configuraţii spaţiale.(Vezi exemplul următor.)

Ex.2. În câte feluri pot fi colorate vârfurile unui tetraedru regulat cu cel mult 3 culori?

Răspuns: Vom desena un tetraedru regulat cu vârfurile numerotate de la 1 la4, şi vom determina grupul de simetrii al configuraţiei tetraedrale:

1

23

4

20

• Cea mai evidentă simetrie este permutarea identitate, care nu schimbăpoziţia nici unui colţ: (1)(2)(3)(4)

• Apoi, putem răsuci teraedrul cu 120◦ sau cu 240◦ ı̂n jurul unei ı̂nălţimi:– În jurul ı̂nălţimii din vârful 1: (1)(2, 3, 4), (1)(2, 4, 3)

– În jurul ı̂nălţimii din vârful 2: (2)(1, 3, 4), (2)(1, 4, 3)

– În jurul ı̂nălţimii din vârful 3: (3)(2, 3, 4), (3)(2, 4, 3)

– În jurul ı̂nălţimii din vârful 4: (4)(1, 2, 3), (4)(1, 3, 2)

• Alt tip de simetrii răsucesc tetraedrul cu 180◦ ı̂n jurul uneia din cele treiaxe care trec prin mijloacele a două 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)}

Numărul căutat este N =1

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

(81 + 99)/12 = 15.

21

Exerciţii propuse (Set 3)

1. Câte coliere diferite cu 6 mărgele de cel mult 3 culori există?

1

2

34

5

6

2. În câte feluri se pot colora muchiile unui tetraedru cu cel mult 3 culori?

1

2

3

4

5

6

3. Să se calculeze numărul de colorări diferite a configuraţiei următoare cu cel mult2 culori.

1

2

3 4

5

6

7

Pólya a descoperit şi o metodă de calcul al colorărilor diferite al unei configuraţii C,daca se precizează de câte ori se foloseşte fiecere culoare:

• La fel ca şi pentru Lema lui Burnside, mai ı̂ntâi se determină grupul de simetriiG al configurţiei C.

• Apoi se calculează inventarul de modele al configuraţiei C pentru m culori.Dacă configuraţia C are n componente care se colorează cu cel mult m culoriy1, y2, . . . , ym, atunci inventarul de modele este polinomul FG(y1, . . . , ym) cucoeficienţi ı̂ntregi şi variabilele y1, y2, . . . , yn astfel ı̂ncât

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

k1,...,km

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

k22 . . . y

kmm

unde fiecare a(k1,...,km) este numărul de colorări diferite a configuraţiei C cu

22

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 paşi:

P1. Mai ı̂ntâi se determină 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 şi 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 obţine din PG(x1, x2, . . . , xn) ı̂nlocuind

x1 cu y1 + y2 + . . .+ ymx2 cu y

21 + y

22 + . . .+ y

2m

. . .xn cu y

n1 + y

n2 + . . .+ y

nm

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

Exemplu ilustrat:

Ex.3. Două molecule sunt izomeri dacă au aceeaşi compoziţie de atomi, dar au structurispaţiale diferite. Molecula de naftalină are 10 atomi de carbon dispuşi ı̂n colţurileunei structuri dublu hexagonale, iar 8 din cei 10 atomi, situaţi la poziţiile nu-merotate ı̂n figura de mai jos, sunt legaţi la câte un atom de hidrogen:

12

34

56

78

(a) Naftolul se obţine ı̂nlocuind unul din atomii de hidrogen ai naftalinei de lapoziţiile numerotate cu un grup hidroxil (OH). Câţi izomeri de naftol există?

23

(b) Tetrametilnaftalina se obţine ı̂nlocuind patru din atomii de hidrogen ai naf-talinei de la poziţiile numerotate cu grupuri de metil (CH3). Câţi izomeride tetrametilnaftalină există?

Răspuns: Răspunsurile la ambele ı̂ntrebări pot fi găsite calculând inventarul de modeleal moleculei de naftalină, căreia i se colorează nodurile numerotate de la 1 la 8 cu douăculori: roşu (r) şi galben (g). Vom considera că poziţiile colorate cu roşu sunt cele cucarbon legat la hidrogen. Atunci

• Coeficientul lui r7g este numărul de izomeri de naftol.

• Coeficientul lui r4g4 este numărul de izomeri de tetrametilnaftalină.

Se vede uşor că 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)}

Rezultă că 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 tetrametilnaftalină.Exerciţii propuse (Set 4)

1. Câte coliere diferite cu 6 mărgele se pot forma dacă se folosesc 2 mărgele verzi,două galbene, şi două roşii?

1

2

34

5

6

2. În câte feluri se pot colora 2 muchii ale unui tetraedru cu roşu, una cu albastru,şi 3 cu galben?

24

1

2

3

4

5

6

3. Câte zaruri diferite se pot alcătui dacă i se numerotează feţele cu numere de la 1la 6?

4. Benzenul este o hidrocarbură cu 6 atomi de carbon plasaţi ı̂n vârfurile unuihexagon regulat, şi 6 atomi de hidrogen, fiecare legat la câte un atom de carbon.

1

2

34

5

6

(a) Câţi izomeri se pot obţine dacă ı̂n molecula de benzen se ı̂nlocuiesc doi atomide hidrogen cu doi atomi de clor?

(b) Câţi izomeri se pot obţine dacă ı̂n molecula de benzen se ı̂nlocuiesc doi atomide hidrogen cu doi atomi de clor şi alţi 2 atomi de hidrogen cu doi atomi debrom?

Numere Stirling

I[nk

]= numărul Stirling de cicluri: ı̂n câte feluri pot fi puse n persoane la k mese

rotunde identice astfel ı̂ncât nici o masă să nu rămână neocupată.

Exemplu:[31

]= 2 deoarece sunt 2 posibilităţi de a pune 3 persoane la o masă

rotundă:

1

2 3

posibilitatea 1ciclul (1, 3, 2)

1

3 2

posibilitatea 2ciclul (1, 2, 3)

25

I{nk

}= numărul Stirling de mulţimi: ı̂n câte feluri se poate partiţiona o mulţime

cu n elemente ı̂n k submulţimi nevide disjuncte.

Exemplu:{32

}= 3 deoarece sunt 3 posibilităţi de ı̂mpărţire ı̂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.

• Dacă 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 dacă n = 00 dacă n > 0

Dacă n ≥ 1 atunci[n1

]= 1 şi

[nn−1

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

• Dacă n ≥ 1 şi k ≥ 1 atunci[nk

]= (n− 1)

[n−1k

]+[n−1k−1

]

26

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 dacă n = 0,0 dacă n > 0.

Dacă 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

......

......

......

.... . .

Exerciţii rezolvate

1. În câte feluri se poate forma un şir de 7 caractere, dacă se folosesc doar litere dinmulţimea {a, b, c, d} şi fiecare literă trebuie să apară cel puţin o dată ı̂n şir?

27

Răspuns: Fie s un astfel de şir, şi f(x) mulţimea poziţiilor din x unde aparelitera x ∈ {a, b, c, d}. De exemplu, dacă s = aabddcb atunci f(a) = {1, 2},f(b) = {3, 7}, f(c) = {6} şi f(d) = {4, 5}. Se observă că f este o funcţiebijectivă de la mulţimea A = {a, b, c, d} la P , unde P este o partiţie a mulţimiide poziţii {1, 2, 3, 4, 5, 6, 7} ı̂n 4 grupuri astfel ı̂ncât fiecare grup să aibe cel puţinun element. Ştim că

• Numărul de astfel de partiţii P este numărul Stirling de mulţimi{74

}.

• Pentru fiecare astfel de partiţie P există 4! funcţii bijective de la A la P(deoarece A şi P sunt mulţimi cu 4 elemente.)

Conform regulii produsului, există 4! ·{74

}= 24 · 350 = 8400 astfel de funcţii f ,

deci 8400 astfel de şiruri.

2. Fie rn,k numărul de posibilităţi de a ı̂mpărţi n persoane ı̂n k grupuri disjuncte,astfel ı̂ncât fiecare grup să aibe cel puţin 2 persoane.

Folosiţi un raţionament combinatorial pentru a demonstra că, dacă n > k > 1,atunci rn,k = k · rn−1,k + (n− 1) · rn−2,k−1.Răspuns: Faptul că partea dreaptă este o sumă de 2 termeni ne sugerează săı̂ncercăm să aplicăm regula sumei. Distingem două cazuri disjuncte:

Cazul 1: Persoana n face parte dintr-un grup de 2 persoane. Acest cazpoate fi descompus ı̂n o secvenţă de 2 paşi: (1) alegem una din celelalten − 1 persoane care să stea la masă cu persoana n, apoi (2) formăm k − 1grupuri de cel puţin 2 persoane din clee n − 2 persoane rămase. 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 puţin 3 persoane.Şi acest caz poate fi descompus ı̂n o secvenţă de 2 paşi: (1) formăm kgrupuri de cel puţin 2 persoane cu primele n−1 persoane, apoi (2) adăugămpersoana 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, rezultă că

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

Exerciţii propuse (Set 5)

28

1. Folosiţi un raţionament combinatorial (regula sumei, regula produsului) pentrua găsi o fomulă simplă de calcul a numărului Stirling

[n+2n

]când n ≥ 2.

2. Folosiţi un raţionament combinatorial (regula sumei, regula produsului) pentrua găsi o fomulă simplă de calcul a numărului Stirling

{n+2n

}când n ≥ 2.

3. Fie A = {a, b, c, . . . , x, y, z} alfabetul de 26 caractere latine minuscule. Câte şiruride 50 de caractere din A se pot forma dacă fiecare literă din A trebuie să aparăcel puţin o dată?

4. Folosiţi un raţionament combinatorial pentru a demonstra că, dacă n > k > 1,atunci C(n, k) = C(n− 1, k) + C(n− 1, k − 1).

29