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 hA1 , . . . , Ar i unde A1 ,
. . . , Ar sunt elemente distincte dintr-o mulţime cu n elemente. Formula de calcul
n!
este P (n, r) = = n · (n − 1) · . . . · (n − r + 1)
(n − r)!
• C(n, r) este numărul de submulţimi cu r elemente al unei mulţimi cu n elemente.
n!
Formula de calcul este C(n, r) =
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 2
ori?
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 7
litere ⇒ 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 completat
7 poziţii
I 2 din 7 poziţii cu B ⇒ C(7, 2) posibilităţi, şi mai rămân de completat
5 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ăţi

I A de 2 ori, B de 3 ori ⇒ C(6, 2) · C(4, 3) · 3 posibilităţi
I A de 2 ori, B de 4 ori ⇒ C(6, 2) · C(4, 4) posibilităţi
I A de 3 ori, B de 2 ori ⇒ C(6, 3) · C(3, 2) · 3 posibilităţi
I A de 3 ori, B de 3 ori ⇒ C(6, 3) · C(3, 3) posibilităţi
I 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 unde
X ⊆ {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ărul
căutat este N1 + N2 − N3 unde
• N1 este numărul submulţimilor care conţin A; 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}, deci
N2 = 29 .
⇒ 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
√ √
1± 1 + 4 · 56 1 ± 225 1 ± 15
n= = =
2 2 2
Rezultă că n = 8 sau n = −7. Deoarece, din punct de vedere combinatorial, n
nu 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
n(n − 1)
4· = n(n − 1)(n − 2) ⇒ 2 n(n − 1) − 2 n(n − 1)(n − 2) = 0
2
⇒ 2 n(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 cu
7, adică cu 35}.

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

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

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 o

mulţ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ă şi
numai 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ă A

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

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

7. Denis are 6 mărgele roşii şi 8 mărgele verzi. În câte feluri poate ı̂nşira Denis
cele 14 mărgele pe o aţă dacă prima mărgea din şirag trebuie să fie roşie, şi este
permis 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 plasarea
urmă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 acestor
mă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 al
doilea element?

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

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

n 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 poate
deplasa 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

(0,0)
dreapta

7. La o tombolă participă 15 bărbaţi şi 10 femei şi se acordă 3 premii de 100 lei şi
2 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 sunt
câştigători?
(c) În câte feluri se pot acorda cele 5 premii dacă se ştie că nici o femeie nu a
câş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

Permutare: h1, 2, 3i h1, 3, 2i h2, 1, 3i h2, 3, 1i h3, 1, 2i h3, 2, 1i

Rang: 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 rangul

permutării hap1 , ap2 , . . . , apn i a lui A este egal cu rangul permutării hp1 , p2 , . . . , pn i
a mulţimii {1, 2, . . . , n}.

• Dacă hp1 , p2 , . . . , pn i este permutare a mulţimii {1, 2, . . . , n} atunci

ranghp1 , p2 , . . . , pn i = (p1 − 1) · (n − 1)! + ranghp2 , . . . , pn i

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

 
r
p1 = p 1 = +1
(n − 1)!

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

1. Rangul permutării h4, 1, 3, 2, 5i a mulţimii {1, 2, 3, 4, 5} este:

1 3 2 4
rangh4, 1, 3, 2, 5i = (4 − 1) · 4! + rangh1, 3, 2, 5i = 72 + rangh1, 3, 2, 4i = 72 + (1 −
2 1 3 1 2
1) · (4 − 1)! + rangh3, 2, 4i = 72 + rangh2, 1, 3i = 72 + (2 − 1) · (3 − 1)! + rangh1, 3i =
1
72 + 2 + rangh1, 2i = 74 + (1 − 1) · (2 − 1)! + rangh2i = 75 + rangh1i = 74 + 0 = 74.
1 2 3 4
2. Rangul permutării hd, b, a, ci a mulţimii A = {a, b, c, d} cu a < b < c < d este:
4 2 1 3
ranghd, b, a, ci = rangh4, 2, 1, 3i = (4−1)·(4−1)!+rangh2, 1, 3i = 18+(2−1)·(3−
1 2 1
1)!+rangh1, 3i = 18+2+rangh1, 2i = 20+(1−1)·(2−1)!+rangh2i = 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 hp1 , p2 , p3 , p4 , p5 i lui {1, 2, 3, 4, 5} astfel ı̂ncât
ranghp1 , p2 , p3 , p4 , p5 i = 73.

• q = 73
 
4!
+ 1 = 4 ⇒ p1 = 4 şi rămâne de calculat permutarea hp2 , p3 , p4 , p5 i
1 2 3 4
mulţimii {1, 2, 3, 5} cu rangul 73 − (q − 1) · 4! = 73 − 72 = 1
• q = 3!1 + 1 = 1 ⇒ p2 = 1 şi rămâne de calculat permutarea hp3 , p4 , p5 i
 
1 2 3
mulţimii {2, 3, 5} cu rangul 1 − (q − 1) · 3! = 1
• 2!1 + 1 = 1 ⇒ p3 = 2 şi rămâne de calculat permutarea hp4 , p5 i mulţimii
 
1 2
{3, 5} cu rangul 1 − (q − 1) · 2! = 1
1
• 1!1 + 1 = 2 ⇒ p4 = 5 şi rămâne de calculat permutarea hp5 i mulţimii {3}
 

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

Deci permutarea lui h1, 2, 3, 4, 5i cu rangul 73 este h4, 1, 2, 5, 3i.

Exemple de calcul al permutării care urmează după o permutare dată ı̂n ordine lexi-
cografică:
1. Ce permutare urmează după permutarea h2, 1, 3, 8, 5, 6, 9, 7, 3i ı̂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):

h2, 1, 3, 8, 5, 6, 9, 7, 3i → h2, 1, 3, 8, 5, 7, 9, 6, 3i

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

h2, 1, 3, 8, 5, 7, 9, 6, 3i → h2, 1, 3, 8, 5, 7, 3, 6, 9i

2. Ce permutare urmează după h2, 3, 1, 5, 4i ı̂n ordine lexicografică?

Răspuns: h4, 1, 3, 2, 5i

8
 3. Ce permutare urmează după h5, 4, 3, 2, 1i ı̂n ordine lexicografică?
Răspuns: nici una.

4. Ce permutare urmează după h1, 3, 2, 7, 6, 5, 4i ı̂n ordine lexicografică?

Răspuns: h1, 3, 4, 2, 5, 6, 7i.

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 } pentru

care presupunem că A1 < A2 < . . . < An , este

hAp1 , Ap2 , . . . , Apr i ı̂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

Permutare cu repetiţie: ha, ai ha, bi ha, ci hb, ai hb, bi hb, ci hc, ai hc, bi hc, ci
Rang: 0 1 2 3 4 5 6 7 8

• Rangul unei r-permutări cu repetiţie hAp1 , Ap2 , . . . , Apr i a lui A = {A1 , . . . , An }

ı̂n ordine lexicografică este valoarea lui q1 q2 . . . qr ı̂n baza n, unde qi = pi − 1
pentru toţi i.

• Permutarea cu repetiţie a mulţimii A = {A1 , . . . , An } care are rangul k este

hAq1 +1 , Aq2 +1 , . . . , Aqr +1 i unde (q1 q2 . . . qr )n este reprezentarea lui k ı̂n baza n,
folosind r cifre.

Exemple
0 1 2 3 4
1. Care este rangul 3-permutării cu repetiţie hb, a, a, di a mulţimii A = {a, b, c, d, e}
ı̂n ordine lexicografică?
Răspuns: ranghb, a, a, di = 10035 = 1 · 53 + 3 = 128.

9
 0 1 2 3 4 5
2. Care este 4-permutarea cu repetiţie a lui A = {a, b, c, d, e, f } cu rangul 53?
Răspuns: A are 6 elemente, deci trebuie să calculăm reprezentarea lui 29 ı̂n
baza 6 folosind r = 4 cifre.
53 = 1 · 62 + 2 · 6 + 5 · 1 ⇒ 53 = 01256 ⇒ 4-permutarea cu repetiţie căutată este
ha, b, c, f i.

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 rangul
binar al submulţimii respective: De exemplu, submulţimile lui A = {a, b, c} au
rangurile binare indicate ı̂n tabelul de mai jos:
şir binar
rang 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 . . . b2 b1 reprezintă submulţimea {Ai | bi = 1}.
Enumerarea submulţimilor lui A ı̂n ordine crescătoare a rangului binar se numeşte
ordonare 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ă se
calculează 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 este
010112 , deci
5 4 3 2 1 Submulţime
0 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 unor
probleme 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 putem
construi 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−3
posibilităţ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 =7
a4 = a1 + a2 + a3 = 13
a5 = a2 + a3 + a4 = 24
a6 = 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ţin
000. 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 = 2n − an unde a0 = 1, a1 = 2, a2 = 4 şi an = an−1 + an−2 + an−3
pentru 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 la
dispoziţie bancnote de 1 leu, 5 lei şi 10 lei (ordinea ı̂n care se plătesc bancnotele
nu contează). De exemplu, A12 = deoarece 12 lei pot fi achitaţi ı̂n 4 feluri:

1) 1 × 10LEI + 2 × 1LEU
2) 2 × 5LEI + 2 × 1LEU
3) 1 × 5LEI + 7 × 1LEU
4) 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 lei
{1,10}
folosind toate tipurile de bancnote din S şi doar acestea. De exemplu, An
reprezintă ı̂n câte feluri se pot achita n lei folosind cel puţin 1 bancnotă de
1 leu, cel puţin 1 bancnotă de 5 lei, şi doar bancnote de 1 leu şi de 5 lei.

13
 
1 dacă n este multiplu de k,
{k}
Este evident că An =
0 ı̂n caz contrar.
Conform regulii sumei, avem:
{1,5,10} {1,5} {1,10} {5,10} {1} {5} {10}
• An = An + An + An + A5 + An + An + An

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


S 0 dacă n < k,
An = S S−{k}
An−k + An−k dacă n ≥ k.
{1,5,10} {1,5} {1,10} {5,10} {1} {5} {10}
(b) A12 = A12 + A12 + A12 + A5 + A12 + A12 + A12 .
{5} {10}
Deoarece 12 nu este multiplu de 5 şi nici de 10, A12 = A12 = 0. Deaseme-
{1} {5,10}
nea, A12 = 1 şi A5 = 0 deoarece 5 < 10. Deci
{1,5,10} {1,5} {1,10}
A12 = A12 + A12 + A12 + 1.
{1,5,10} {1,5,10} {1,5}
A12 = A2 + A2 = 0 + 0 = 0.
{1,5} {1,5} {1} {1,5} {1,5} {1}
A12 = A7 + A7 = A7 + 1 = A2 + A2 + 1 = 0 + 1 + 1 = 2
{1,10} {1,10} {1}
A12 = A2 + A2 = 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ţă este

r2 − 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 2n :

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 · B
a2 =7 = (2 · A + B) · 22 = 8 · A + 4 · B

9 25
⇒ A = − , B = . Deci an = (−9 n/4 + 25/4) · 2n .
4 4

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) (p)
n + an

unde
(h)
• an este o soluţie a relaţiei de recurenţă omogene
(h) (h)
a(h) (h) n
n = 4 · an−1 − 4 · an−2 ⇒ an = (A · n + B) · 2 .

• Deoarece r = 2 are multiplicitatea 2 ı̂n ecuaţia caracteristică a recurenţei

omogene, iar partea neomogenă este (n2 + n + 1) · 2n , rezultă că

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

(p) (p) (p)

Din faptul că an = 4 · an−1 − 4 · an−2 + (n2 + n + 1) · 2n pentru toţi n ≥ 3 rezultă
că

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

Rezultă că
 
12 C − 1 = 0   C = 1/12
6 D − 24 C − 1 = 0 ⇒ D = 1/2
2 E − 6 D + 14 C − 1 = 0 E = 17/12
 

deci

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

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

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

an = (2 n + 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
⇒ A = 1, B = −2 ⇒ an = (−5)n − 2.
−7 = a1 = 5 A + B

Exerciţii propuse (Set 2)

1. Un şir de litere din mulţimea {a, b, c, d} este acceptabil dacă nu conţine subşirul
aa. 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 o
formulă de calcul pentru xn .

4. Un şir de cifre zecimale este special dacă are un număr par de zerouri. Fie Sn
numă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 π = hp1 , p2 , . . . , pn i 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 = π . . ◦ π}; π 0 = h1, 2, . . . , ni).
| ◦ .{z
n ori

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

1 2 n
↓ ↓ ... ↓
π = hp1 p2 . . . pn i

• 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 simetrii

al unor configuraţii de interes (vezi Teoria lui Pólya).

Exemple

1. Fie π = h7, 6, 5, 1, 3, 2, 4i.

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

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

1 2 3 4 5 6 7
↓ ↓ ↓ ↓ ↓ ↓ ↓
Răspuns: Ştim că π = h7 6 5 1 3 2 4i

(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
 1 2 3 4 5 6 7
↓ ↓ ↓ ↓ ↓ ↓ ↓
2
(b) π = π ◦ π = h4 2 3 7 5 6 1i

1 2 3 4 5 6 7
↑ ↑ ↑ ↑ ↑ ↑ ↑
π −1 = h7 6 5 1 3 2 4i = h4, 6, 5, 7, 3, 2, 1i

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) π = h10, 2, 7, 9, 5, 1, 6, 12, 4, 3, 8, 11i

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 de m culori. Configuraţia

spaţială a şiragului este

1 5
3 4
2 6

Fiecare cerculeţ n reprezintă poziţia n a unei mărgele ı̂n şirag. Câte şiraguri
diferite 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 acestei
configuraţ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 5 6 2
3 4 ⇒ 4 3
2 6 5 1
(c) Rotaţia ı̂n jurul axei verticale de simetrie: (1, 5)(2, 6)(3, 4)
1 5 5 1
3 4 ⇒ 4 3
2 6 6 2

19
 (d) Rotaţia ı̂n jurul axei orizontale de simetrie: (1, 2)(3)(4)(5, 6)
1 5 2 6
3 4 ⇒ 3 4
2 6 1 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
1 X
diferite de acest fel este N = |Cπ |, unde
|G| π∈G

• |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

1
N = (|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) |)
4
1
m6 + m3 + m3 + m4 = (m6 + m4 + 2 m3 )/4


=
4

Observaţie: Pentru a aplica Lema lui Burnside, trebuie să descoperiţi toate simetriile
unei 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 la
4, şi vom determina grupul de simetrii al configuraţiei tetraedrale:

3
2
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 trei
axe care trec prin mijloacele a două muchii opuse:
1 2

3 4
2 ⇒ 1 (1, 2)(3, 4)

4 3
1 3

3 1
2 ⇒ 4 (1, 3)(2, 4)

4 2
1 4

3 2
2 ⇒ 3 (1, 4)(2, 3)

4 1

⇒ 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)}
1
Numărul căutat este N = (m4 + 11 m2 ) pentru m = 3, adică (34 + 11 · 32 )/12 =
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ă?

4 3

5 2

6 1

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

1 3
5
6
4 2

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

2 culori.

1 5
3 7 4
2 6

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 simetrii
G 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 culori
y1 , y2 , . . . , ym , atunci inventarul de modele este polinomul FG (y1 , . . . , ym ) cu
coeficienţi ı̂ntregi şi variabilele y1 , y2 , . . . , yn astfel ı̂ncât
X
FG (y1 , . . . , ym ) = a(k1 ,k2 ,...,km ) y1k1 y2k2 . . . ym
km

k1 ,...,km

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

22
 k1 componente colorate cu culoarea y1
k2 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 :
1 X
PG (x1 , x2 , . . . , xn ) = Mπ (x1 , x2 , . . . , xn )
|G| π∈G

unde Mπ (x1 , x2 , . . . , xn ) = xλ1 1 xλ2 2 . . . xλnn şi permutarea π are tipul

[λ1 , λ2 , . . . , λn ].
m m m
!
X X X
P2. FG (y1 , y2 , . . . , ym ) = PG yi , yi2 , . . . , yin
i=1 i=1 i=1
Altfel spus, FG (y1 , y2 , . . . , ym ) we obţine din PG (x1 , x2 , . . . , xn ) ı̂nlocuind
x1 cu y1 + y2 + . . . + ym
x2 cu y12 + y22 + . . . + ym
2

...
xn cu y1n + y2n + . . . + ymn

De multe ori, calculul inventarului de modele FG (y1 , y2 , . . . , ym ) este foarte

costisitor. 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 structuri
spaţiale diferite. Molecula de naftalină are 10 atomi de carbon dispuşi ı̂n colţurile
unei 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:

8 4
7 3
6 2
5 1

(a) Naftolul se obţine ı̂nlocuind unul din atomii de hidrogen ai naftalinei de la

poziţ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 izomeri
de tetrametilnaftalină există?

Răspuns: Răspunsurile la ambele ı̂ntrebări pot fi găsite calculând inventarul de modele

al 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 cu
carbon legat la hidrogen. Atunci

• Coeficientul lui r7 g este numărul de izomeri de naftol.

• Coeficientul lui r4 g4 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 ) = 41 (x81 + 3 · x42 ), deci

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


FG (r, g) =
4
= r8 + 2 r7 g + 10 r6 g2 + 14 r5 g3 + 22 r4 g4 + 14 r3 g5 + . . . + g8

Coeficientul lui r7 g este 2 ⇒ sunt 2 izomeri de naftol.

Coeficientul lui r4 g4 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?

4 3
5 2
6 1

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 3
5
6
4 2

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

la 6?

4. Benzenul este o hidrocarbură cu 6 atomi de carbon plasaţi ı̂n vârfurile unui

hexagon regulat, şi 6 atomi de hidrogen, fiecare legat la câte un atom de carbon.

4 3
5 2
6 1

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

Numere Stirling
n
I k
= 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 1

2 3 3 2

posibilitatea 1 posibilitatea 2
ciclul (1, 3, 2) ciclul (1, 2, 3)

25
 n
I k
= 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 2
posibilitatea 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−1 n−1

k
+ k−1
.
n


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


k
k=0 1 2 3 4 5 6 7 8 ... n!
n=0 1 1
1 1 1 1
2 1 2 1 2
3 1 3 3 1 6
4 1 4 6 4 1 24
5 1 5 10 10 5 1 120
6 1 6 15 20 15 6 1 720
7 1 7 21 35 35 21 7 1 5040
8 1 8 28 56 70 56 28 8 1 40320
.. ..
. .
n
Formule de calcul pentru k

n 1 dacă n = 0
• 0
=
0 dacă n > 0
Dacă n ≥ 1 atunci n1 = 1 şi n−1
 n 
= C(n, 2) = n(n − 1)/2

• Dacă n ≥ 1 şi k ≥ 1 atunci nk = (n − 1) n−1

    n−1
k
+ k−1

26
Triunghiul numerelor nk :
 

n
k
k=0 1 2 3 4 5 6 7 8 ... n!
n=0 1 1
1 0 1 1
2 0 1 1 2
3 0 2 3 1 6
4 0 6 11 6 1 24
5 0 24 50 35 10 1 120
6 0 120 274 225 85 15 1 720
7 0 720 1764 1624 735 175 21 1 5040
8 0 5040 13068 13132 6769 1960 322 28 1 40320
.. .. ..
. . .

Formule de calcul pentru nk




n n 1 dacă n = 0,
n
• 1
= n
= 1. 0
=
0 dacă n > 0.
Dacă n > k ≥ 1 atunci k = k · n−1
n  n−1
k
+ k−1 .

Triunghiul numerelor nk :


n
k
k=0 1 2 3 4 5 6 7 8 ...
n=0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 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 din
mulţ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 apare
litera 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ţie
bijectivă de la mulţimea A = {a, b, c, d} la P , unde P este o partiţie a mulţimii
de poziţii {1, 2, 3, 4, 5, 6, 7} ı̂n 4 grupuri astfel ı̂ncât fiecare grup să aibe cel puţin
un 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 caz

poate fi descompus ı̂n o secvenţă de 2 paşi: (1) alegem una din celelalte
n − 1 persoane care să stea la masă cu persoana n, apoi (2) formăm k − 1
grupuri de cel puţin 2 persoane din clee n − 2 persoane rămase. Conform
regulii 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 k
grupuri de cel puţin 2 persoane cu primele n − 1 persoane, apoi (2) adăugăm
persoana n la oricare din cele k grupuri formate la primul pas. Conform
regulii 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) pentru
n+2
a găsi o fomulă simplă de calcul a numărului Stirling n când n ≥ 2.

2. Folosiţi un raţionament combinatorial (regula sumei, regula

produsului) pentru
a găsi o fomulă simplă de calcul a numărului Stirling n+2
n
când n ≥ 2.

3. Fie A = {a, b, c, . . . , x, y, z} alfabetul de 26 caractere latine minuscule. Câte şiruri

de 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