Partit ii ntregi si grafuri orientate aciclice [602055]

Partit ii ^ ntregi  si grafuri orientate aciclice
Poenaru Andreea Mariana
2016

2

Cuprins
1 Introducere 5
2 Elemente de combinatoric a 7
2.1 Partit ii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Modele de combinatoric a pentru partit ii . . . . . . . . . . 7
2.1.2 Formule de recurent  a . . . . . . . . . . . . . . . . . . . . . 9
2.1.3 Identit at i multinomiale . . . . . . . . . . . . . . . . . . . 11
2.1.4 Aplicat ii . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Numerele Stirling  si Bell . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Denit ii  si notat ii . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Evalu ari . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.3 Formule de recurent  a . . . . . . . . . . . . . . . . . . . . . 21
2.2.4 Polinoame generatoare . . . . . . . . . . . . . . . . . . . . 23
2.2.5 Inversiunea Stirling . . . . . . . . . . . . . . . . . . . . . . 25
2.2.6 Aplicat iii . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Numerele lui Catalan . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.1 Denit ie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3.2 Drumuri laticiale . . . . . . . . . . . . . . . . . . . . . . . 28
3 Teoria grafurilor 37
3.1 Not iunea de graf . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Grafuri orientate . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Lant uri  si cicluri . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4 Partit ii ^ ntregi  si grafuri orientate aciclice 49
4.1 Leg atura dintre partit iile unui ^ ntreg pozitiv  si grafurile orientate
aciclice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 Diagrame binare . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3

4 CUPRINS

Capitolul 1
Introducere
Lucrarea trateaz a generarea partit iilor ^ ntregi prin structuri arborescente.
^In primul capitol am prezentat modele combinatoriale pentru partaje ind
^ nsot ite de exemple practice  si demonstrat ii ale teoremelor utiliz^ and not iunea
de partaj.
Am f acut trecrea ^ n revist a a numerelor lui Stirling, Bell  si Catalan care
joac a un rol deosebit ^ n funct iile de num arare.
Urmate apoi de formulele de recurent  a ce aprofundeaz a leg atura dintre par-
taje  si grafuri.
^In cel de al doilea capitol am facut o scurt a introducere in teoria grafu-
rilor denind not iunea de graf orientat  si neorientat cu not iunile aferente: graf
part ial, complet, bipartit, adiacent  a  si incident  a  s.a.
^In ultimul capitol am prezentat rezultatele recente ^ n stocarea partit iilor
^ ntregi cu ajutorul metodelor de parcurgere a arborilor binari.
5

6 CAPITOLUL 1. INTRODUCERE

Capitolul 2
Elemente de combinatoric a
2.1 Partit ii
2.1.1 Modele de combinatoric a pentru partit ii
FieS= [n] o mult ime cu nelemente,p2N1 si unp-vector (i1;:::;ip)2Np
0
numit tip. Scoatem ^ n evident  a c^ ateva exemple de modele combinatoriale care
conduc la ideea de partit ie ordonat a saupartaj al unei mult imi  si la num ararea
acestora pentru o mult ime xat a.
(1)Not am
P(S; (i1;:::;ip)) =f(X1;:::;Xp)j(X1;:::;Xp)2(S())p;X1[:::[Xp=S,
Xi\Xj=?pentrufi;jg2[p]:jXjj=ijpentruj2[p]g:
Exemplul 2.1. Fien= 5;p= 2;S=f1;2;3;4;5g;(i1;i2) = (2;3),
P(f1, 2, 3, 4, 5g;(2, 3))=f(12, 345),(13,245),(14, 235),(15, 234),(23,
145),(24, 135),(25, 134),(34, 125),(35, 124),(45, 123) g.
Consider amP(S; (i1;:::;ip)) ca ind mult imea p-partit iilor ordonate de tip
(i1;:::;ip)ale lui S unde o astfel de p-partit ie ordonat a o vom numi partaj.
Observat ia 2.2. Se poate folosi semnul S(i1;:::;i p)^ n loc deP(S; (i1;:::;ip)).
Not amn
i1


ip
=jP(S; (i1;:::;ip))j,(partaje de n luate c^ ate (i1;:::;ip),
sau de tip (i1;:::;ip)).
(2)n
i1


ip
= num arul permut arilor multisetului Xi1
1:::Xipp(peste mult imea
suportfX1;:::Xpg)
Exemplul 2.3. Fien= 5;p= 2;S=f1;2;3;4;5g;(i1;i2) = (2;3).(tabelul 1.1)
Pe scurt
7

8 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
(3)n
i1


ip
= num arul drumurilor laticiale din O(0;:::;0)^ nM(i1;:::;ip).
Permutarea multisetului Xi1
1:::Xippcorespunz atoare unui drum laticeal poate
interpretat a ca o codicare a acestuia (exemplul 1.4)
(4)n
i1


ip
=jfrjr: [n]![p];jr1(1)j=i1;jr1(2)j=i2;:::;
jr1(p)j=ipgj:
(5)(variant a a modelului 2)
n
i1


ip
=jfxjx= (x1;:::;xn)2[p]n,
num arul coordonatelor egal cu jesteijpentruj2[p]g:j
(6)n
i1


ip
= coecientul monomului Xi1
1


Xippdin dezvoltarea poli-
nomului (X1+:::+Xp)n.
Avem prin urmare identitatea multinomial a a lui Newton
(X1+:::+Xp)n=X
i1+:::+ip=n
i1;:::;i p2N0n
i1


ip
Xi1
1


Xip
p
MonomulXi1
1


Xippse interpreteaz a ca multiset  si se consider a permut arile

2.1. PARTIT  II 9
sale pe mult imea parantezelor.
(7)n
i1


ip
= num arul distribut iilor a n bile diferite (de n tipuri) ^ n p
cutiiX1;:::;Xp, astfel ^ nc^ at ^ n cutia Xjs a e distribuite ijbile,j2[p]. Ordinea
^ n care bilele sunt distribuite nu conteaz a .
(8)
n
i1


ip
= num arul distribut iilor a n bile – din care i1de tip
X1;:::;ipde tipXP,i1+:::+ip=n- ^ n n cutii de c^ ate una ^ n cutie.
Exemplul 2.4. Exemplu pentru modelul (3)
Modul ^ n care a fost denitn
i1


ip
are semnicat ie combinatorial a
numai pentru n2N0;p2N1 si pentru parametrii i1;:::;ipgenerat i de
urm atoarele condit ii:
i1+:::+ip=n sii1;::::;ip2N0 (1)
 si se nume ste generatorul de tipuri pentru p-partajele lui [n] .
^In cazul ^ n care una din aceste condit ii nu este satisf acut a , lu am prin
convent ie
n
i1


ip
= 0:
Observat ia 2.5. Pentrun2N0;p= 2;i1;i22N0 sii1+i2=navem
jP(S; (i1;i2))j=jS(i1)j
deoarece avem biject ia f:P(S; (i1;i2))!S(i1)deni a astfel (X1;X2)!X1.
Deci,n
i1i2
=n
i1
 si , astfel, not iunea de partaj extinde pe aceea de
combinare.
2.1.2 Formule de recurent  a
Teorema 2.6. Relat ia lui Pascal de recurent  a aditiv a
n
i1


ip
=
n1
(i11)i2i3


ip
+
n1
i1(i21)i3


ip
+
n1
i1i2(i31)i4


ip
+:::+
n1
i1i2


(ip1)
:

10 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
Demonstrat ie. PentruS= [n];t= (i1;:::;ip)2Np
0 six2Sxat, avem
aplic^ and principiul partit iei, cu notat iile din modelul 1:
jP(S;t)j=jP(S;t;x2X1)j+jP(S;t;x2X2)j+:::+jP(S;t;x2Xp)j;
chiar relat ia de demonstrat.
Teorema 2.7. Pentrun2N0 si un vector (i1;:::;ip)2Np
0generat de (1.1)
avemn
i1


ip
=n!
i1!


ip!
Demonstrat ia 1. Consider am modelul (7). Fie pcutiiX1;X2;:::;Xp sinbile
diferite numerotate 1, 2, 3,…, n. Consider am c a ^ n cutia Xisuntilocuri, 1
ip, dispuse ca ^ n diagrama:
Figura 1.3
Avem:
(1) Celepcutii aunlocuri (i1+:::+ip=n) ^ n total.
(2) Num arul distribut iilor celor nbile diferite pe cele nlocuri esten!.
(3) O distribut ie pe celenlocuri induce o unic a distribut ie ^ n cele pcutii.
(4) Pe mult imeaS([n]) a celorn! distribut ii denim relat ia
000:()0 si00induc o aceea si distribut ie ^ n cele pcutii.
undeeste o relat ie de echivalent  a.
Not am ^clasa de echivalent  a a unei distribut ii .
(5)j^j=i1!


ip!;82S([n])
Pentru o distribut ie 2 S([n]), prin permutarea bilelor corespunz atoare
aceleia si cutii, obt inem o distribut ie 0echivalent a ( 0)  si orice distribut ie
echivalent a cu poate  obt inut a astfel. Rezult a (5).
(6) A sadar avem
n
i1


ip
=jS([n])=j=n!
i1!


ip!

2.1. PARTIT  II 11
Demonstrat ia 2. Consider am modelul (1). Num arul jP([n]; (i1;:::;ip))jalp-
partajelor ( X1;:::;Xp) care satisfac condit iile
X1[:::[Xp=S= [n];
Xi\Xj=?;1i<jp;
jXjj=ij;1jp
este egal cu num arul i1-p art ilorX1S^ nmult it cu num arul i2-p art ilorX2
SX1^ nmult it cu num arul i3-p art ilorX3SX1X2^ nmult it cu … num arul
ip-p art ilorXpSX1X2:::Xp1:Obt inem
jP([n]; (i1;:::;ip))j=
n
i1
ni1
i2
ni1i2
i3
ni1i2i3
i4



ni1i2:::ip1
ip
=n!
i1!(ni1)!
(ni1)!
i2!(ni1i2)!


(ni1i2:::ip1)!
ip!(ni1i2:::ip1ip)!=n!
i1!


ip!
Demonstrat ia 3. (Varianta formalizat a a demonstrat iei 1) Pe mult imea per-
mut arilor mult imii [ n] ,S([n]) =fj: [n]![n];o biject iegdenim relat ia
00:() f0(1);:::;0(i1)g=f00(1);:::;0(i1)g si
f0(i1+ 1);:::;0(i1+i2)g=f00(i1+ 1);:::;0(i1+i2)g si




f0(i1+:::+ip1+ 1);:::;0(n)g=f00(i1+:::+ip1+ 1);
:::;00(n)g:
undeeste o relat ie de echivalent  a. Not am cu ^ clasa de echivalent  a a unei
permut ari2S([n]). Avemjj=i1!


ip!;82S([n]). Obt inem
n
i1


ip
=jS([n])=j=n!
i1!


ip!:
2.1.3 Identit at i multinomiale
Teorema 2.8. Pentrun2N0 sip2N0avem :
(a) Identitatea multinomial a a lui Newton
(x1+:::+xn)p=X
i1+:::+in=p
i1;:::;i n2N0p
i1


in
xi1
1


xin
n
(b) Identitatea multinomial a a lui Vandermonde
(x1+:::+xn)p=X
i1+:::+in=p
i1;:::;i n2N0
p
i1


in
xi1
1


xin
n

12 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
(c) Identitatea multinomial a a lui N orlund
(x1+:::+xn)p=X
i1+:::+in=p
i1;:::;i n2N0p
i1


in
xi1
1


xin
n
Demonstrat ia 1 (a). Avem
(x1+:::+xn)p= (x1+:::+xn)
(x1+:::+xn)
:::
(x1+:::+xn)| {z }
p paranteze
Un monom oarecare din dezvoltarea pprodusului are forma xi1
1xi2
2


xinn, unde
exponent ii i1;:::;inverc a relat iile (1.1). Coecientul unui astfel de monom
xi1
1xi2
2


xinneste egal cu num arul de moduri de a selecta i1paranteze din cele
p, din care alegem x1, ^ mult it cu num arul de moduri de a selecta i2paranteze
din restul de pi1din care alegem x2, ^ nmult it cu num arul de moduri de a
selectai3paranteze din restul de pi1i2din care alegem x3etc.
Obt inem c a acest coecient este egal cu
p
i1pi1
i2pi1i2
i3



pi1i2:::in1
in
=p!
i1!(pi1)!
(pi1)!
i2!(pi1i2)!


(pi1i2:::in1)!
in!(pi1i2:::in1in)!=p!
i1!


in!
=p
i1


in
;
deoarecepi1i2:::in= 0. Identitatea este demonstrat a.
Demonstrat ia 2 (a). (Utilizeaz a not iunea de partaj  si argumentul polinomial.)
FieSo mult ime nit a  si X1;:::;Xnon-partit ie a sa S=X1_[:::_[Xn:Not am
xj=jXjj;1jn. Num arul p-cuvintelor peste Seste egal cujSpj= (x1+
:::+xn)p:Pentru un cuv^ ant oarecare c=c1c2


cp2Sp= (X1_[X2_[:::_[Xn)p
mult imileI1;:::;Inale indicilor pozit iilor literelor din X1;:::;Xn^ nc, respectiv,
induc unn-partaj al lui [ p]I1_[I2_[:::_[In= [p] de tip (i1;i2;:::;in) undeij=j
Ijj;1jn(gura 1.4)
Relat iilei1+:::+in=p sii1;:::;in2N0sunt generate de tipurile n-
partajelor lui [ p]. Num arul n-partajelor ( I1;I2;:::;In) ale lui [p] de tip (i1;:::;in)
este egal cup
i1


in
. Num arulp-cuvintelor din Sp^ n caren-partajul lui [ p]

2.1. PARTIT  II 13
indus de pozit iile literelor din X1;:::;Xn, respectiv, este de tip ( i1;:::;in), este
egal cuxi1
1


xinn. A sadar avem c a, egalitatea (a) este valabil a 8×1;:::;xn2N:
Rezult a , cu argumentul polinomial, c a (a) este adev arat a ca identitate polino-
mial a.
Demonstrat ia 3 (a). ( Variant a ^ n termeni de funct ii a demonstrat iei 2 (a).) Fie
So mult ime nit a  si X1;:::;Xnon-partit ie a sa S=X1_[


_[Xn:
Not amxj=jXjj;1jn:Avem urm atoarea partit ie a mult imii
funct iilorS[p]=ffjf: [p]!Sg
ffjf: [p]!X1_[


_[Xng
_[
i1+:::+in=p
i1;:::;i n2N0_[
I1_[:::_[In=[p]
(I1;:::;I n) de tip (i1;:::;i n)ffjf: [p]!X1[


[Xn;
f1(X1) =I1;:::;f1(Xn) =Ing:
Avem
jffjf: [p]!X1_[


_[Xngj= (x1+


+xn)p
jf(I1;:::;In)jI1_[


_[In= [p];(I1;:::;In) de tip (i1;:::;in)gj=p
i1


in
jffjf: [p]!X1_[


_[Xn;f1(X1) =I1;:::;f1(Xn) =Ingj=xjI1j
1


xjInn:
Prin urmare egalitatea (a) este valabil a 8×1;:::;xn2N:Rezult a, cu argu-
mentul polinomial , c a (a) este adev arat a ca identitatea polinomial a.
Demonstrat ia 1 (b). FieSo mult ime nit a  si X1;:::;Xnon-partit ie a sa S=
X1_[


_[Xn. Not amxj=jXjj;1jn. Num arul p-partit iilor lui Seste
egal cu
jS(p)j=x1+:::+xn
p
:
Cardinaliii1;:::;inai ,,urmelor" X\X1;:::;X\Xn, respectiv, ale unei p-p art i
X2S(p)^ n celen-p art iX1;:::;Xnsunt generat i de relat iile i1+:::+in=p
,i1;:::;in2N0:Pentru un astfel de n-vector (i1;:::;in)2Nn
0xat, num arul
p-part ilorX2S(p)cu propietateajX\Xjj=ij;1jn, este egal cux1
i1



xn
in
:Rezult a
x1+:::+xn
p
=X
i1+:::+in=p
i1;:::;i n2N0x1
i1



xn
in
;
sau

14 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
(x1+:::+xn)p
p!=X
i1+:::+in=p
i1;:::;i n2N0xi1
1
i1!


xin
n
in!;
sau
(x1+:::+xn)p=X
i1+:::+in=p
i1;:::;i n2N0p!
i1!


in!xi1
1


xin
n:
Rezult a c a egalitatea (b) este valabil a pentru 8×1;:::;xn2N. Deci, cu
argumentul polinomial, (b) este adevarat a ca identitatea polinomial a.
Demonstrat ia 2 (b). (^Inrudit a cu demonstrat ia 3 (a)) Fie So mult ime nit a  si
X1;:::;Xnon-partit ie a sa S=X1_[


_[Xn. Not amxj=jXjj;1jn.
Avem urm atoarea partit ie a mult imii funct iilor injective ~S(p)=ffjf: [p]!
S;finjectiv ag
ffjf: [p]!X1_[


_[Xn;finjectiv ag=
_[
i1+:::+in=p
i1;:::;i n2N0_[
I1_[:::_[In=[p]
(I1;:::;I n) de tip (i1;:::;i n)ffjf: [p]!X1[


[Xn;finjectiv a
f1(X1) =I1;:::;f1(Xn) =Ing:
Avem
jffjf: [p]!X1_[


_[Xn;finjectiv agj= (x1+


+xn)p
jf(I1;:::;In)jI1_[


_[In= [p];(I1;:::;In) de tip (i1;:::;in)gj=
p
i1


in
jffjf: [p]!X1_[


_[Xn;finjectiv a;f1(X1) =I1;:::;f1(Xn) =Ingj
=xi1
1


xin
n:
A sadar, egalitatea (b) este valabil a 8×1;:::;xn2N. Deci, cu argumentul
polinomial, (b) este adevarat a ca identitatea polinomial a.
Demonstrat ia 1 (c). (^Inrudit a cu demonstrat ia 2 (b).) Fie So mult ime nit a
 siX1;:::;Xnon-partit ie a sa S=X1_[


_[Xn. Not amxj=jXjj;1jn.
Num arulp-multip art ilor este egal cu
jShpij=x1+:::+xn
p
:

2.1. PARTIT  II 15
Op-multiparte X2Shpiinduce oi1-multiparte peste X1, oi2-multiparte
pesteX2, …, oin-multiparte peste Xn, unde (i1;:::;in) veric a relat iile i1+:::+
in=p sii1;:::;in2N0. Pentru un astfel de n-vector (i1;:::;in)2Nn
0xat,
num arulp-multip art ilor X2Shpieste egal cu
x1
i1



xn
in
:Rezult a
x1+:::+xn
p
=X
i1+:::+in=p
i1;:::;i n2N0x1
i1



xn
in
;
sau
(x1+:::+xn)p
p!=X
i1+:::+in=p
i1;:::;i n2N0xi1
1
i1!


xinn
in!;
sau
(x1+:::+xn)p=X
i1+:::+in=p
i1;:::;i n2N0p!
i1!


in!xi1
1


xin
n:
Prin urmare egalitatea (c) este valabil a 8×1;:::;xn2N:Rezult a, cu argu-
mentul polinomial , c a (c) este adev arat a ca identitatea polinomial a.
2.1.4 Aplicat ii
Teorema 2.9. Pentrux1;:::;xn2N0 sipun num ar avem
(x1+:::+xn)pxp
1+:::+xp
n(mod p)
Demonstrat ie. Av^ and ^ n vedere c a peste num ar prim, se observ a c a pentru
i1+:::+in=p;8i1;:::;in2N0avem congruent a

p
i1


in
=p!
i1!


in!
0 dac ai1;:::;in<p
1 dac a9t2[n] cuit=p(modp).
Folosind aceasta congruent  a^ n identitatea multinomial a a lui Newton, obt inem
propietatea din enunt 
(x1+:::+xn)p=X
i1+:::+in=p
i1;:::;i n2N0p
i1


in
xi1
1


xin
nxp
1+:::+xp
n(mod p)
Teorema 2.10. (Mica teorem a a lui Fermat) Pentru pnum ar prim  si n2N
avem
npn(modp).
Demonstrat ie. Consider am x1=


=xn= 1 ^ n congruent a precedent a
np= (1 +:::+ 1)|{z}
nori(1p+:::+ 1p)|{z}
norin(modp).

16 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
2.2 Numerele Stirling  si Bell
2.2.1 Denit ii  si notat ii
FieS=f1;2;:::;ngunden2N1. Pentru o partit ie a luiS si un element
x2Snot am cu ^xpartea dincare cont ine x. Analog, pentru o permutare 
al luiS si un element x2Snot am cu ^xciclulcare cont ine x, adic a
^x= [x;(x);2(x);:::;t1(x)];
undeteste num arul minim cu propietatea t(x) =x;numit ordinul luix.
Pentru o permutare a luiSnot am cuGgraful orientat denit astfel
V(G) =S;
E(G) =f(x;(x))jx2Sg:
O permutare a luiSpoate  descris a astfel :
ca o funct ie bijectiv a :S!Sprin tabelarea ei
1 2


n
(1)(2)


(n)
;
sub forma unui cuv^ ant (1)(2)


(n1)(n);
ca un produs de cicluri ^ x;
prin graful orientat G:
De exemplu, pentru S=f1;2;3;4;5;6gavem urm atoarele patru descrieri
echivalente ale unei permut ari 
=
1 2 3 4 5 6
5 3 4 2 1 6
= 534216
= [6][1;5][2;3;4]
G:

2.2. NUMERELE STIRLING S I BELL 17
Se observ a c a produsul ciclurilor disjuncte este comutativ. ^In cazul exemplului
precedent avem
= [6] [1,5] [2, 3, 4] =[6] [2, 3, 4][1, 5]
= [1, 5] [6] [2, 3, 4] = [1, 5] [2, 3, 4] [6]
= [2, 3, 4] [6] [1, 5] = [2, 3, 4] [1, 5] [6]
Totodat a, se observ a c a un k-ciclu (adic a un ciclu cu kelemente) poate
citit ^ ncep^ and cu oricare din elementele sale, ^ n kmoduri. Astfel, pentru ci-
clurile permut arii din exemplul anterior avem
[1;5] = [5;1]
[2;3;4] = [3;4;2] = [4;2;3]
Opartit ie^ n p art i nevide a mult imii S, spunem c a este de tip 1i12i2


nin
dac acont ine
i1p art i de cardinal 1 ;
i2p art i de cardinal 2 ;
i3p art i de cardinal 3 ;




inp art i de cardinal n.
Analog, o permutare a mult imii S(gura 1.9) spunem c a este de tip
1i12i2


nindac acont ine
i11-cicluri (bucle) ;
i22-cicluri ;
i33-cicluri ;




inn-cicluri.

18 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
Not am cuP(S; 1i12i2


nin) mult imea partit iilor lui Sde tip 1i12i2


nin
 si cuS(S; 1i12i2


nin) mult imea permut arilor lui Sde tip 1i12i2


nin:
P(S; 1i12i2


nin) :=fjeste o partit ie a lui Sde tip 1i12i2


ning;
S(S; 1i12i2


nin) :=fjeste o permutare a lui Sde tip 1i12i2


ning:
Numerelei1;i2;:::;incare sunt prezente ^ n descrierea tipului unei partit ii
neordonate sau a unei permut ari a luiSsunt caracterizate complet de
satisfacerea urm atoarelor relat ii :
i1;i2;:::;in2N0;1i1+ 2i2+:::+nin=n: (2)
Not am cuPk(S) mult imea k-partit iilor lui S^ n p art i nevide (adic a a partit iilor
cuk-p art i nevide)  si cu Sk(S) mult imea k-permut arilor lui S(adic a a per-
mut arilor cu k-cicluri), unde k2N0
Pk(S) :=fjeste ok-partit ie a lui S^ n p art i nevideg;
Sk(S) :=fjeste ok-permutare a lui Sg;
iar cuP(S) mult imea partit iilor lui S^ n p art i nevide  si cu S(S) mult imea
permut arilor lui S
P(S) :=fjeste o partit ie a lui S^ n p art i nevideg;
S(S) :=fjeste o permutare a lui Sg:
Not am pentru k2N0cus(n;k) := (1)n+kjSk([n])j si numims(n;k)
num arul lui Stirling de spet a I , iar cuS(n;k) :=jPk([n])j si numimS(n;k)
num arul lui Stirling de spet a a II-a . Avems(n;0) =S(n;0) = 0;n2N1 si
facem convent ia s(0;0) =S(0;0) = 1. De asemenea, not am cu B(n) :=jP([n])j
 siB(0) := 1, unde n2N1 si numimB(n)num arul lui Bell .
2.2.2 Evalu ari
Propozit ia 2.11. Fien2N1 sii1;:::;in2N0nnumere naturale care sat-
isfac relat iile (2).
(a) Num arul partit iilor neordonate ale mult imii [n]de tip 1i12i2


nineste
P([n]; 1i12i2


nin) =n!
(1!)i1(2!)i2


(n!)ini1!i2!


in!:

2.2. NUMERELE STIRLING S I BELL 19
(b) Num arul permut arilor mult imii [n]de tip 1i12i2


nineste
S([n]; 1i12i2


nin) =n!
1i12i2


nini1!i2!


in!:
Demonstrat ie. (a) FieGgraful bipartit (permut ari-partit ii de tip 1i12i2


nin)
denit astfel
V(G) =S([n])_[P([n]; 1i12i2


nin);
E(G) =ff;gj2S([n]);=ff(1)g;f(2)g;:::;f(i1)g;f(i1+ 1);
(i1+ 2)g;
f(i1+ 3);(i1+ 4)g;f(i1+ 5);(i1+ 6)g;:::;
f(i1+ 2i21);(i1+ 2i2)g;
f(i1+ 2i2+ 1);(i1+ 2i1+ 2);(i1+ 2i2+ 3)g;:::;
f(i1+ 2i2+ 3i32);(i1+ 2i2+ 3i31);
(i1+ 2i2+ 3i3)g;:::g
^In grafulGo permutare =(1)


(n) este adiacent a partit iei cont inut a
din aceasta astfel: primele i1elemente din cuv^ antul (1)


(n) sunt 1-p art ile
lui, urm atoarele i2perechi de elemente succesive din cuv^ antul (1)


(n)
sunt 2-p art ile lui , etc.
Astfel,82S([n]) avemdG() = 1:
^In grafulGo partit ie este adiacent a permut arilor =(1)


(n) obt inute
din aceasta astfel: se ordoneaz a p art ile lui ^ n ordinea cresc atoare a cardi-
nalilor, se permut a ^ n toate modurile posibile elementele ec arei p art i, se per-
mut a p art ile de acela si cardinal ^ ntre ele. Cuv^ antul obt inut de ecare dat a
prin ignorarea parantezelor acolad a este o permutare =(1)


(n). Astfel,
pentru orice partit ie neordonat a din mult imeaP([n]; 1i12i2


nin) avem
dG() = (1!)i1(2!)i2


(n!)ini1!i2!


in!:
Avem
jE(G)j=X
2S([n])dG() =X
2S([n])1 =jS([n])j=n!;
jE(G)j=P
2P([n];1i12i2


nin)dG()
=jP([n]; 1i12i2


ninj(1!)i1(2!)i2


(n!)ini1!i2!


in!:
Rezult a (a).
(b) FieGgraful bipartit (permut ari-permut ari de tip 1i12i2


nin) denit
astfel
V(G) =S([n])_[S([n]; 1i12i2


nin);
E(G) =ff;0gj2S([n]);0= [(1)][(2)]


[(i1)][(i1+ 1);(i1+ 2)]

[(i1+ 3);(i1+ 4)][(i1+ 5);(i1+ 6)]



[(i1+ 2i21);(i1+ 2i2)]

[(i1+ 2i2+ 1);(i1+ 2i2+ 2);(i1+ 2i2+ 3)]



[(i1+ 2i2+ 3i32);(i1+ 2i2+ 3i31);
(i1+ 2i2+ 3i3)]


g

20 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
^In grafulGo permutare 2S([n]) este adiacent a unei permut ari 0din
mult imeaS([n]; 1i12i2


nin), obt inut a din aceasta astfel: primele i1elemente
din cuv^ antul (1)


(n) sunt 1-ciclurile lui 0, urm atoarele i2perechi de ele-
mente succesive din cuv^ antul (1)


(n) sunt 2-ciclurile lui 0, urm atoarele i3
triplete de elemente succesive din cuv^ antul (1)


(n) sunt 3-ciclurile lui 0,
etc.
Astfel,82S([n]) avemdG() = 1:
^In grafulGo permutare 02S([n]; 1i12i2


nin) este adiacent a permut arilor
=(1)


(n) obt inute din aceasta astfel: se scrie 0ca produs de cicluri
ordonate cresc ator dupa cardinali, se permut a circular elementele ec arui ciclu,
se permut a ciclurile de acela si cardinal ^ ntre ele. Cuv^ antul obt inut de ecare
dat a prin ignorarea parantezelor p atrate este o permutare =(1)


(n):
Astfel, pentru orice permutare 02S([n]; 1i12i2


nin) avem
dG(0) = 1i12i2


nini1!i2!


in!:
(Se observ a c a ^ n demonstrat ie permut arile 2S([n]) au fost descrise sub
form a de cuvinte (1)


(n), iar permut arile 02S([n]; 1i12i2


nin) au fost
descrise sub form a de produs de cicluri.)
Avem
jE(G)j=X
2S([n])dG() =X
2S([n])1 =jS([n])j=n!;
jE(G)j=X
02S([n];1i12i2


nin)dG(0)
jS([n]; 1i12i2


ninj1i12i2


nini1!i2!


in!:
Rezult a (b).
Teorema 2.12. Fien2N1 sik2 f1;2;:::;ng. Urm atoarele relat ii sunt
adev arate :
(a)S(n;k) =X
i1;:::;i n2N0
i1+:::+in=k
1i1+:::+nin=nn!
(1!)i1(2!)i2


(n!)ini1!i2!


in!:
(b)js(n;k)j=X
i1;:::;i n2N0
i1+:::+in=k
1i1+:::+nin=nn!
1i12i2


nini1!i2!


in!:
Demonstrat ie. Teorema este o consecint  a imediat a a denit iilor numerelor lui
Stirling  si a propozit iei 1.11.
Teorema 2.13. Pentrun2N1 sik2f1;2;:::;ngavem
S(n;k) =1
k!jFs([n];[k])j
= (1)k1
k!k
0
0nk
1
1n+k
2
2n

2.2. NUMERELE STIRLING S I BELL 21
+


+ (1)kk
k
kn
;
undejF(n;k)jeste num arul funct iilor surjective denite pe o mult ime cu
nelemente cu valori ^ ntr-o mult ime cu kelemente.
Demonstrat ie. FieF([n];[k]) =ffjf: [n]![k];f([n]) = [k]g:Consider am
graful bipartit G(funct ii-surjective k-partit ii ^ n p art i nevide) denit astfel
V(G) =Fs([n];[k])_[Pk([n]);
E(G) =fff;gjf2Fs([n];[k]);=ff1(1);f1(2);:::;f1(k)gg:
AvemdG(f) = 1;8f2Fs([n];[k])  sidG() =k!;82P([n]):
Obt inem
jE(G)j=X
f2Fs([n];[k])dG(f) =X
f2Fs([n];[k])1 =jFs([n];[k])j:
jE(G)j=X
2P([n])dG() =X
2P([n])k! =k!jP([n])j=k!S(n;k):
Rezult a formula din enunt  (b).
2.2.3 Formule de recurent  a
Teorema 2.14. Pentru orice n;k2N1avem
S(n+1;k) =
n
0
S(0;k1)+
n
1
S(1;k1)+


+
n
n
S(n;k1):
Observat ia 2.15. DeoareceS(j;k1) = 0 pentru 0j < k1, suma din
membrul drept se face propiu zis numai pentru termenii S(j;k1)cuk1
jn
Demonstrat ie 1. Fie un element xat x2[n+ 1]. Pentru o partit ie 2Pk([n+
1]) not am ^ xacea parte din care cont ine x. Evidentj^xj nk+ 2,
82Pk([n+ 1]) deoarece oricare dintre celelalte ( k1) p art i din cont ine cel
put in un element. Partit ion am mult imea partit iilor lui [ n+ 1] dup a cardinalul
p art ii care cont ine x si astfel avem
jPk([n+ 1])j=jPk([n+ 1];j^xj= 1)j+jPk([n+ 1];j^xj= 2)j+


+
jPk([n+ 1];j^xj=nk+ 2)j:

22 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
DarjPk([n+ 1])j=S(n+ 1;k)  sijPk([n+ 1];j^xj=i+ 1)j=n
i
S(ni;k1) =n
ni
S(ni;k1);8i2f0;1;2;:::;nk+1g:
Rezult a
S(n+ 1;k) =nk+1X
i=0n
ni
S(ni;k1) =nX
j=k1n
j
S(j;k1)
=Pn
j=0n
j
S(j;k1);
ceea ce trebuia demonstrat.
Demonstrat ia 2. Fiex2[n+ 1] un element xat. Not am cu P+
n+1(x) mult imea
p art ilor lui [ n+ 1] care cont in x(ltrul generat de fxg).
Consider am graful bipartit G(k-partit ii – ltrul generat de fxg) denit astfel
V(G) =Pk([n+ 1]) _[P+
n+1(x);
E(G) =ff;Tgj2Pk([n+ 1]);T2P+
n+1(x);T2g:
Pentru ok-partit ie oarecare 2Pk([n+1]) avemdG() = 1. Pentru o parte
oarecareT2P+
n+1(x) care cont ine elementul xavem
dG(T) =
S(jTj;k1) pentru k1jTjn
0 ^ n rest,
unde am notat T= [n+ 1]T:Obt inem
jE(G)j=X
2Pk([n+1])dG() =X
2Pk([n+1])1 =S(n+ 1;k):
jE(G)j=X
T2P+
n+1(x)dG(T) =nX
j=k1X
x2T[n+1]
jTj=jS(j;k)
=nX
j=k1n
j
S(j;k1) =nX
j=0n
j
S(j;k1):
Rezult a formula din enunt .
Teorema 2.16. Pentru8n2N0avem
B(n+ 1) =n
0
B(0) +n
1
B(1) +


+n
n
B(n);
undeB(n)este num arul lui Bell.
Demonstrat ia 1. Fie un element xat x2[n+1]. Partit ion am mult imea partit iilor
lui [n+ 1] dupa cardinalul p art ii care cont ine x si astfel avem
jP([n+ 1])j=jP([n+ 1];j^xj= 1)j+jP([n+ 1];j^xj= 2)j
+jP([n+ 1];j^xj= 3)j+:::+jP([n+ 1];j^xj=n+ 1)j:
Dar
jP([n+ 1])j=B(n+ 1)

2.2. NUMERELE STIRLING S I BELL 23
 si
jP([n+ 1];j^xj=i+ 1)j=
n
i
B(ni) =
n
ni
B(ni)
pentrui2f0;1;2;:::;ng. Rezult a
B(n+ 1) =nX
i=0n
ni
B(ni) =nX
j=0n
j
B(j);
ceea ce trebuia demonstrat.
Demonstrat ia 2. Fiex2[n+ 1] un element xat. Not am cu P+
n+1(x) mult imea
p art ilor lui [ n+ 1] care cont in elementul x(ltrul generat de fxg). Consider am
graful bipartit G(partit ii-ltrul generat de fxg) denit astfel
V(G) =P([n+ 1]) _[P+
n+1(x);
E(G) =ff;Sgj2P([n+ 1]);S2P+
n+1(x);S2g:
Pentru o partit ie oarecare 2P([n+ 1]) avem dG() = 1. Pentru o parte
oarecareS2P+
n+1(x) care cont ine elementul xavemdG(S) =B(jSj), unde am
notat S= [n+ 1]S:Obt inem
jE(G)j=X
2P([n+1])dG() =X
2P([n+1])1 =B(n+ 1);
jE(G)j=X
S2P+
n+1(x)dG(S) =nX
j=0X
x2S[n+1]
jSj=jB(j) =X
j=0n
j
B(j)
Rezult a formula din enunt .
2.2.4 Polinoame generatoare
Teorema 2.17. Pentru orice n2N1avem
js(n;1)jx1+js(n;2)jx2+


+js(n;n)jxn=xn:
Demonstrat ie. Vom demonstra ca egalitatea de mai sus este adev arat a 8x2N1
 si, conform argumentului polinomial, demonstrat ia va  ^ ncheiat a.
Consider am x2N1 si graful bipartit G(permut ari-color ari) denit astfel
V(G) =S([n])[F([n];[x]);
E(G) =ff;cgj2S([n]);c2F([n];[x]); ceste constant a pe elementele
ciclurilor lui g
undeF([n];[x]) =fcjc: [n]![x]g:

24 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
Pentru o permutare oarecare 2S([n]) cukcicluri gradul ei ^ n Geste
egal cu num arul funct iilor denite pe mult imea ciclurilor cu valori ^ n [ x], deci
dG() =xk. Pentru o colorare oarecare c2F([n];[x]) gradul ei ^ n Geste egal
cudG(c) =jc1(1)j!


jc1(x)j!:Avem
jE(G)j=X
2S([n])dG() =nX
k=1X
2S([n])xk=nX
k=1js(n;k)jxk;
jE(G)j=X
c2F([n];[x])dG(c) =X
j1+:::+jx=n
j1;:::;j x2N0X
c2F([n];[x])
jc1(1)j!


jc1(x)j!
=(j1;:::;j x)j1!


jx!
=X
j1+:::+jx=n
j1;:::;j x2N0n
j1!


jx!
j1!


jx! =n!hx
ni=xn:
Rezult a identitatea din enunt .
Observat ia 2.18. Datorit a faptului c a s(0;0) = 1;s(n;0) = 0;8n2N1 si
coecientul monomului xidin polinomul xneste egal cu (1)i+ncoecientul
monomului xidin polinomul xn, teorema 2.17 se poate enunt a  si astfel:
Pentru orice n2N0avem
s(n;0)x0+s(n;1)x1+s(n;2)x2+:::+s(n;n)xn=xn:
Teorema 2.19. Pentru8n2N1avem
S(n;1)x1+S(n;2)x2+


+S(n;n)xn=xn:
Demonstrat ie. Vom demonstra c a egalitatea din enunt  este adev arat a pentru
8x2N1 si, conform argumentului polinomial, demonstrat ia va  ^ ncheiat a.
Consider am x2N1 si graful bipartit G(partit ii-color ari) denit astfel
V(G) =P([n])[F([n];[x]);
E(G) =ff;cgj2P([n]);c2F([n];[x]);mult imea preimaginilor
fc1(1);:::;c1(x)ginduce ^ n [n] partit iag:
undeF([n];[x]) =fcjc: [n]![x]g:

2.2. NUMERELE STIRLING S I BELL 25
Pentru o partit ie oarecare ^ n k-p art i nevide 2P([n]) gradul ei ^ n Geste
egal cu num arul funct iilor injective denite pe mult imea p art ilor cu valori ^ n
[x], decidG() =xk. Pentru o colorare oarecare c2F([n];[x]) gradul ei ^ n G
este 1,dG(c) = 1. Avem
jE(G)j=X
2P([n])dG() =nX
k=1X
2Pk([n])xk=nX
k=1S(n;k)xk
jE(G)j=X
c2F([n];[x])dG(c) =X
c2F([n];[x])1 =xn:
Rezult a identitatea din enunt .
Observat ia 2.20. DeoareceS(0;0) = 1;S(n;0) = 0;8n2N1teorema 1.22 se
poate enunt a  si astfel:
Pentru orice n2N0avem
S(n;0)x0+S(n;1)x1+S(n;2)x2+


+S(n;n)xn=xn:
2.2.5 Inversiunea Stirling
Denim matriciile asociate numerelor Stirling de spet a I sn= (s(l;c))0l;cn si
de spet a a doua Sn= (S(l;c))0l;cn, adic a
sn=0
BBBBBBBBBB@s(0;0) 0 0


0


0
s(1;0)s(1;1) 0


0


0
s(2;0)s(2;1)s(2;2)


0


0
………………
s(l;0)s(l;1)s(l;2)


s(l;l)


0
………………
s(n;0)s(n;1)s(n;2)


s(n;l)


s(n;n)1
CCCCCCCCCCA
Sn=0
BBBBBBBBBB@S(0;0) 0 0


0


0
S(1;0)S(1;1) 0


0


0
S(2;0)S(2;1)S(2;2)


0


0
………………
S(l;0)S(l;1)S(l;2)


S(l;l)


0
………………
S(n;0)S(n;1)S(n;2)


S(n;l)


S(n;n)1
CCCCCCCCCCA

26 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
Teorema 2.21. Pentru orice n2N0matricele Stirling sunt inverse una
celeilalte
sn
Sn=In+1;
undeIn+1este matricea unitate cu n+ 1linii  sin+ 1coloane.
Demonstrat ie. Relat iile din observat iile 1.21  si 1.23
mX
i=0s(m;i)xi=xm simX
i=0S(m;i)xi=xm;
unde am t inut cont c a s(m;0) =S(m;0) = 0;pentrum2N1 sis(0;0) =
S(0;0) = 1;scrise pentru m2f0;1;2;:::;ngse transpun ^ n limbaj matriceal
astfel
sn
(x0x1x2


xn)t= (x0x1x2


xn)t
 si
Sn
(x0x1x2


xn)t=sn
Rezult as1
n=Sn:
Teorema 2.22. (Inversiune Stirling) Fie dou a  siruri de numere u0;u1;


;un



 siv0;v1;


;vn;


. Urm atoarele armat ii sunt echivalente:
(a)vn=s(n;0)u0+s(n;1)u1+


+s(n;n)un;8n2N0;
(a)un=S(n;0)v0+S(n;1)v1+


+S(n;n)vn;8n2N0;
2.2.6 Aplicat iii
Teorema 2.23. (Identitatea Cauchy) Pentru orice n2N0avem urm atoarea
relat ie
X
1k1+:::+nkn=n
k1;:::;k n2N01
1k1


nknk1!


kn!= 1:
Demonstrat ie. Avem
jS([n])j=X
1k1+:::+nkn=n
k1;:::;k n2N0jS([n]; 1k1


nkn)j
sau
n! =X
1k1+:::+nkn=n
k1;:::;k n2N0n!
1k1


nknk1!


kn!;
^Imp art ind prin n!, va rezulta identitatea Cauchy.

2.3. NUMERELE LUI CATALAN 27
Teorema 2.24. Pentru orice n2N1avem urm atoarele egalit at i:
(a)X
1i1+:::+nin=n
i1;:::;i n2N0xi1+i2+


+in
(1!)i1(2!)i2


(n!)ini1!


in!=xn
n!;
(b)X
1i1+:::+nin=n
i1;:::;i n2N0xi1+i2+


+in
1i12i2


nini1!


in!=xn
n!:
Demonstrat ie. (a)
X
1i1+:::+nin=n
i1;:::;i n2N0xi1+i2+


+in
(1!)i1(2!)i2


(n!)ini1!


in!
=1
n!nX
k=1X
i1+:::+in=k
1i1+:::+nin=n
i1;:::;i n2N0xn!
(1!)i1(2!)i2


(n!)ini1!


in!
xk
=1
n!nX
k=1S(n;k)xk=xn
n!:
(b)
X
1i1+:::+nin=n
i1;:::;i n2N0xi1+i2+


+in
1i12i2


nini1!


in!
=1
n!nX
k=1X
i1+:::+in=k
1i1+:::+nin=n
i1;:::;i n2N0n!
1i12i2


nini1!


in!
xk
=1
n!nX
k=1js(n;k)jxk=xn
n!:
Observat ia 2.25. ^In relat ia (b), dac a x= 1se obt ine identitatea Cauchy.
2.3 Numerele lui Catalan
2.3.1 Denit ie
Fie o operat ie binar a notat a multiplicativ pe o mult ime X, care nu este asocia-
tiv a. Atunci valoarea produsului x1x2


xnpentrux1;x2;:::;xn2X, depinde
de dispunerea parantezelor. De exemplu, pentru n= 3, exist a dou a posibilit at i
de dispunere a parantezelor:
(x1x2)x3 six1(x2x3):

28 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
^In produsul cu n= 4 factori avem 5 posibilit at i de a dispune parantezele:
((x1x2)x3)x4;(x1(x2x3))x4;(x1x2)(x3x4);x1(x2(x3x4));x1((x2x3)x4):
Not am num arul posibilit at ilor de a dispune parantezele ^ ntr-un produs cu n
factori cuE(n). Atunci  sirul ( E(n))nveric a recurent a
E(n) =n1X
k=1E(k)E(nk);E(1) =E(2) = 1
Denit ia 2.26. NumereleE(n)se numesc numerele lui Catalan.
2.3.2 Drumuri laticiale
Undrum laticial Peste o secvent  a de perechi de numere ^ ntregi
P= [(x0;y0);(x1;y1);


(xn;yn)];n2N1;
cu propietatea c a 8i2f1;2;


;ngavem
xi+1=xi+ 1  siyi+1=yisauxi+1=xi siyi+1=yi+ 1
Fiea;b2N0. Not am cu p(a;b) := num arul drumurilor laticiale din A(0;0)
laB(a;b).
p(a;b) =a+b
a
:
Evidentp(a;b) =p(b;a):
Teorema 2.27. Pentrua;m;n;k2N0;0an1;avem:
(a)p(n;k) =kX
i=0p(a;i)p(na1;ki);
(b)m+ 1
n+ 1
=mn+aX
t=at
amt
na
:
Demonstrat ie. (a)

2.3. NUMERELE LUI CATALAN 29
Pentrui2f10;1;2;


;kgnot amMi(a;i)  siNi(a+ 1;i). Avem
p(n;k) = num arul A;B-drumurilor laticiale
=kX
i=0[num arulA;Mi-drumurilor laticiale]

[num arulNi;B-drumurilor laticiale]
=kX
i=0p(a;i)p(na1;ki)
(b) Transpus a ^ n termeni de combin ari, relat ia (a) devine
n+k
n
=kX
i=0a+i
an+kai1
na1
:
Pentrun+ 1 ^ n locul lui n;mn^ n locul lui k;t^ n locul lui a+iobt inem
relat ia (b).
Teorema 2.28. Pentrun2N0avem:
(a)p(n;n) =nX
i=0p2(i;ni);
(b)
2n
n
=nX
i=0
n
i2
:
Demonstrat ie. (a) (gura 1.17) Pentru i2f0;1;2;


;ngnot amMi(i;ni):
Avem
p(n;n) = num arul A;B-drumurilor laticiale

30 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
=nX
i=0[num arulA;Mi-drumurilor laticiale]

[num arulNi;B-drumurilor laticiale]
=nX
i=0p(i;ni)p(ni;i) =nX
i=0p2(i;ni):
(b) Transpunem ^ n termeni combinatoriali relat ia (a)  si obt inem relat ia (b).
Drumuri laticiale cu restrict ii
Pentrua;b2N0denim num arul p1(a;b) astfel:
(1) Dac aa= 0  sib= 0, atunci p1(a;b) := 1:
Teorema 2.29. Pentrun2N0avem
(a)p1(n;n) =[n=2]X
j=0p2
1(j;nj);
(b)Tn+1=[n=2]X
j=0(n2j+ 1)2
(nj+ 1)2n
j2
:

2.3. NUMERELE LUI CATALAN 31
Demonstrat ie.
Pentrui2f[n=2];[n=2] + 1;


;ngnot am cuMi(i;ni). Avem
p1(n;n) = num arul A;B-drumurilor laticiale de sub dreapta ( y=x)
=nX
i=[n=2][num arulA;Mi-drumurilor laticiale de sub dreapta ( y=x)]

[num arulMi;B-drumurilor laticiale de sub dreapta ( y=x)]
=nX
i=[n=2]p2
1(i;ni)
=[n=2]X
j=0p2
1(j;nj):
(b) Evaluarea este transpunerea relat iei (a) ^ n termeni de combin ari.
Aplicat ie
Problema votului . Se cunoa ste c a ^ n urma votului xaleg atori au votat
candidatulX,yaleg atori au votat candidatul Y six>y . Atunci, probabilitatea
ca ^ n orice moment al votului candidatul Xs a  obt inut un num ar strict mai
mare de voturi de c^ at Yestexy
x+y:
Demonstrat ie. Pe axa absciselor, reprezent am voturile acordate lui X, iar pe
axa ordonatelor voturile acordate lui Y. Unui scrutin cu rezultatul ( x;y) i se
asociaz a ^ n mod unic un A(0;0);B(x;y)-drum laticeal  si reciproc.

32 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
Fie punctul C(1;0). Avem:
(a) num arul A;B-drumurilor laticiale este egal cu
x+y
x
;
(b) num arul A;B-drumurilor laticiale care sunt strict sub dreapta ( y=x)
este egal cu num arul de C;B-drumurilor laticeale care sunt sub dreapta ( y=
x1),  si este egal cu
p1(x1;y) =xy
x+yx+y
x
:
Rezult a propietatea din enunt .
Modele combinatoriale pentru num arul lui Catalan
Prezent am c^ ateva exemple de modele combinatoriale care conduc la num arul
lui Catalan Tn, unden2N
Prin denit ie T1= 1:
(1)Tn+1=jfXjX2[2n](n);jX\[j]jj=2;8j2[2n]gj=num arul ^ n n-
p art ilor ale lui [2n]ale c aror urme X\[j]^ n orice segment [j];j2[2n], sunt
majoritare (jX\[j]jj=2):
(2)Tn+1=jffjf: [n]![2n]; fstrict cresc atoare ;jf1([j])jj=2;8j2
[2n]gj
(3)Tn+1=jfrjr: [2n]!f0;1g;P
i2[2n]r(i) =n;jr1(1)\[j]jj=2;8j2
[2n]gj
(4)Tn+1=jfxjx= (x1;:::;x 2n)2f0;1g2n;x1+


+xjj=2;8j2[2n];x1+



+x2n=ngj
(5)Tn+1=p1(n;n)reprezint a num arul drumurilor laticiale din punctul A(0;0)
^ n punctul B(n;n)ale c aror puncte (x;y)veric ayx(adic a ^ n regiunea din
cadranul 1 m arginit a de axa absciselor  si prima bisectoare acestea sunt situate,
0yx).

2.3. NUMERELE LUI CATALAN 33
(6)Tn+1este num arul parantez arilor produsului x1x2


xn+1pentrun0
(num arul de moduri de a separa prin paranteze produsul x1x2


xn+1pentru
a-l efectua).
(7)Tn+1constituie num arul triangulat iilor unui poligon convex cu n+ 2
v^ arfuri (n1):
Formule de recurent  a
Teorema 2.30. Pentru orice num ar natural navem urm atoarea recurent  a
Tn+1=T1Tn+T2Tn1+


+Tn1T2+TnT1: (5)
Demonstrat ie.
Pentrui2f1;2;:::;ngnot am primul punct de la A(0;0) spreBal unui
drum laticial situat pe dreapta AB si diferit de AcuMi(i;i); acest punct poate
 chiarB. Not am de asemenea M0
i(i;i1)  siA0(1;0):Avem
Tn+1=p1(n;n) = num arul A;B-drumurilor laticiale de sub dreapta ( y=x)
=nX
i=1[num arulA0;M0
i-drumurilor laticiale de sub dreapta ( y=x1)]

[num arulMi;B-drumurilor laticiale de sub dreapta ( y=x)]
=nX
i=1p1(i1;i1)p1(ni;ni) =nX
i=1TiTni+1
Teorema 2.31. Pentru orice num ar natural n2N1avem:
2(n1)
n1
T1+2(n2)
n2
T2+


+2
1
Tn1+0
0
Tn=1
22n
n
:(6)

34 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
Demonstrat ie.
FieA0(1;0)A00(0;1);B(n;n):Pentru unA;B-drum laticial  si i2f1;2;:::;ng
not am:
Mi(i;i) = primul punct de la AspreBsituat pe dreapta ABdiferit deA;
M0
i(i;i1) = primul punct de la A0spreB0situat pe dreapta A0B0diferit
deA0;
M00
i(i1;i) = primul punct de la A00spreB00situat pe dreapta A00B00diferit
deA00.
Avem
p(n;n) =2n
n
– num arul de A;B-drumurilor laticiale
=nX
i=1[num arulA0;M0
i-drumurilor laticiale de sub dreapta ( y=x1)]
+ [num arul A00;M00
i-drumurilor laticiale de deasupra dreaptei ( y=x+ 1)]

(num arulMi;B-drumurilor laticiale )
=nX
i=12p1(i1;i1)p(ni;ni) = 2nX
i=12(ni)
ni
Ti
Teorema 2.32. Pentrun2N1avem
1
22n
n
=nTnT1+ (n1)Tn1T2+:::+ 2T2Tn1+ 1T1Tn: (7)
Demonstrat ie.
Se t ine cont ^ n relat ia precedent a c a2(ni)
ni
= (ni+1)Tni+1pentru
i2f1;2;:::;ng:
Observat ia 2.33. Din relat iile de recurent  a (5), (6), ^ mpreun a cu T1= 1,
rezult a prin induct ie expresia
Tn+1=1
n+12n
n
: (8)

2.3. NUMERELE LUI CATALAN 35
^Intr-adev ar relat ia (8) se veric a pentru n= 0
T1=1
0 + 12
0
0
= 1
S a presupunem c a
Ti+1=1
i+12i
i
(9)
pentrui2f0;1;2;:::;n1g si s a demonstr am (8). Atunci relat ia (6) se
scrie
1
22n
n
=nTnT1+ (n1)Tn1T2+


+ 2T2Tn1+ 1T1Tn:
Invers am ordinea termenilor din membrul drept ^ n egalitatea (7)  si o adun am
cu ea ^ ns a si  si obt inem
2n
n
= (n+ 1)[T1Tn+T2Tn1+


+T2Tn1+T1Tn]:
T  inem cont de relat ia (5)  si obt inem2n
n
= (n+1)Tn+1;de unde rezult a
(8).
Teorema 2.34. Fie  sirul numerelor Catalan (Tn)n1, denit prin relat iile T1=
1,Tn+1= [T1Tn+T2Tn1+


+Tn1T2+TnT1;n1; si funct ia generatoare
asociat a
f(x) =T1x+T2x2+T3x3+


+Tnxn+


:
Urm atoarele armat ii sunt adev arate:
(a)f2(x) =f(x)x;
(b)x=f(x)f2(x) sif0(x) =1
12f(x);
(c)f(x)(f0(x)1) = 2(xf0(x)f(x));
(d)Tn+1=1
n1(2T2Tn+ 3T3Tn1+


+nTnT2);n2
(e)Tn+1=n+2
2(n1)(T2Tn+T3Tn1+


+Tn1T3+TnT2);n2;
(f)Tn+1=2(2n1)
n+1Tn;n1;
(g)Tn+1=1
n+12n
n
;n1;
unde cuf0am notat derivata funct iei f.
Demonstrat ie.
f2(x) = (T1x+T2x2+


+Tn1xn1+


)

(T1x+T2x2+


+Tn1xn1+


)
=x2T2
1+x3(T1T2+T2T1)
+


+xn(T1Tn1+T2Tn2+


+Tn2T2+Tn1T1) +



=x2T2+x3T3+


+xnTn+



=f(x)x:
(b) Evident, consecint a lui (a).
(c) T  inem cont de relat iile x=f(x)(1f(x))  sif0(x) =1
2f(x) si evalu am
cei doi membri ai relat iei din enunt 

36 CAPITOLUL 2. ELEMENTE DE COMBINATORIC A
St =f(x)(f0(x)1) =f(x)(1
12f(x)1) =2f2(x)
12f(x);
Dr = 2(xf0(x)f(x)) = 2(f(x)(1f(x))1
2f(x)f(x))
= 2f(x)f2(x)f(x)+2f2(x)
12f(x)=2f2(x)
12f(x):
Rezult a c a cei doi membri sunt egali.
(d) Utiliz am relat ia
f(x)(f0(x)1) = 2(xf0(x)f(x)) (10)
Avem
f(x)(f0(x)1) = (T1x1+T2x2+T3x3+


)
(2T2x1+ 3T3x2+ 4T4x3+


)
= 2T2T1x2+ (2T2T2+ 3T3T1)x3+ (2T2T3+ 3T3T2+ 4T4T1)x4
+ (2T2T4+ 3T3T3+ 4T4T2+ 5T5T1)x5
+


+ (2T2Tn+ 3T3Tn1+ 4T4Tn2+


+nTnT2
+ (n+ 1)Tn+1T1)xn+1+



2(xf0(x)f(x)) = 2[(1 T1x1+ 2T2x2+ 3T3x3+


)
(T1x1+T2x2+T3x3+


)]
= 2(T2x2+ 2T3x3+ 3T4x4+


+nTn+1xn+1+


):
Dezvolt am ^ n serie de puteri utiliz^ and formula generalizat a a binomului lui
Newton
f(x) =1
21
2(14x)1=2=1
21
2X
k0(1)k1
2
k
4kxk=1
2X
k1(1)k(1
2)k
k!4kxk:
Egal am coecient ii lui xn+1din ambii membri
Tn+1=1
2(1)n+1(1
2)n+1
(n+ 1)!4n+1:
Avem succesiv
Tn+1=1
2(1)n+11
2(1
21)(1
22)


(1
2n)
n!(n+1)
2n+12n+1
=1
2(1)n1
2n+1
1(1)(3)(5)


((2n1))
n!(n+1)
2n+12n+1
=1
2(1)n(1)n1
3
5


(2n1)n!
(n!)2(n+1)
2n
2
=1
3
5


(2n1)
2
4


2n
(n!)(n+1)=1
n+1
2n!
(n!)2=1
n+12n
n
:

Capitolul 3
Teoria grafurilor
3.1 Not iunea de graf
Fie X o mult ime nevid a  si nit a  si P2(X) =f(x;y)jx;y2Xg. Dac a x6= y
atunci perecheafx;ygeste indentic a cu perechea fy;xg. De asemenea ,fx;xg
este un element al mult imii P2(X):
FieEo mult ime nevid a a mult imii P2(X).E=fe1;e2;:::;epg.
Prin denit ie, un graf G este o pereche ordonat a de mult imi G= (X;E ),
undeXeste mult imea v^ arfurilor iar Emult imea muchiilor.
Elementele x2Xsunt denumite v^ arfuri (noduri) ale grafului G iar perechile
de v^ arfuri din mult imea Esunt denumite muchii . Nodurile x siyale unei
muchiie=fx;ygdenesc extremit at ile muchiei. Dac a dou a muchii au acelea si
extremit at i se numesc paralele . O muchie cu extremit at ile identice este o bucl a .
Un graf care nu are muchii paralele  si nici bucle este un graf simplu .^In multe
aplicat ii grafurile corespunz atoare sunt simple. Num arul elementelor mult imii
X, notatjXj, este ordinul grafului Giar num arul elementelor mult imii E, notat
jEj,dimensiunea grafului G. Dac ajXj=n sijEj=matunci graful G= (X;E )
este un (n;m) – graf. Dac a ordinul grafului este nit atunci graful G= (X;E )
este un graf nit.
Reprezentarea grac a . Elementele esent iale ale unui graf – nodurile  si
muchiile – se pot vizualiza printr-un desen ^ n care nodurile se reprezint a ca
un cerc ^ n interiorul c aruia se specic a num arul v^ arfului sau prin puncte iar
muchiile prin linii (drepte sau curbe) care unesc punctele corespunz atoarea ex-
tremit at ilor. Distribut ia nodurilor ^ n plan este convent ional a, urm arindu-se
doar buna vizualizarea a desenului, lungimea muchiilor  si unghiurile dintre ele
neav^ and nicio semnicat ie practic a.
Un graf G este numit graf etichetat (sau graf numerotat ) dac a celor nnoduri
ale sale li s-au asociat ^ n mod bijectiv netichete distincte dou a c^ ate dou a.
Mult imea nodurilor poate  indenticat a cu mult imea etichetelor.
Pentru evitarea confuziilor vom nota, ^ n continuare, o muchie ce une ste
nodurile cu etichetele x siyprin [x;y] av^ and semnicat ia unui segment (din
geometrie). Muchia [ x;y] este indentic a cu [ y;x].
Exemplu . FieG= (X;E ) un graf cu X=fx1;x2;x3;x4;x5g siE=fe1;e2;
e3;e4g. Mult imea Xeste reprezentat a prin cinci puncte^ n plan, corespunz atoare
v^ arfurilorx1;x2;x3;x4;x5^ ncadrate ^ n cercuri. Fiec arei muchii i se asociaz a o
37

38 CAPITOLUL 3. TEORIA GRAFURILOR
pereche de noduri: e1= [x1;x2],e2= [x1;x3],e3= [x3;x4],e4= [x4;x4]. Muchi-
ile sunt trasate prin segmente de dreapt a ( sau printr-o curb a ^ n cazul unei bu-
cle).
Figura 1.1
Graful din gura 1.1 este un graf etichetat; nodurile sunt notate prin etichete
x1;x2;x3;x4;x5. EvidentGeste un (5, 4) – graf. Nodul x5este un nod izolat
neind legat de celelalte noduri prin nici o muchie. Muchia [ x4;x4] este o bucl a
 si este reprezentat a printr-o curb a.
Adiacent  a  si incident  a. FieG= (X;E ) un graf  si xi;xj2X. V^ arfurile
xi;xjsunt adiacente dac a exist a o muchie e= [xi;xj] care le une ste. Fiecare
extremitate a unei muchii este considerat a incident a cu muchia respectiv a. Dou a
muchiie1 sie2ale grafului sunt muchii adiacente dac a sunt incidente ^ n acela si
nod.
Gradul unui nod . Se nume ste grad al unui v^ arf x2Xnum arul de muchii
incidente cu nodul x. Gradul v^ arfului xse noteaz a d(x). Un nod izolat are
gradul 0. Relativ la gura 1.1 gradele nodurilor sunt: d(x1) = 2;d(x2) = 1,
d(x3) = 2;d(x4) = 2;d(x5) = 0. Dac ajXj=n sijEj=matunci pentru orice
(m;n) – graf se veric a relat ia:nP
i=1d(xi) = 2
m. Aceast a relat ie rezult a din
faptul c a ecare muchie este incident a ^ n dou a noduri.
Graf part ial. Un grafG= (X;E) este un graf part ia l al unui graf
G=(X;E ) dac aEE. GrafulGse obt ine din graful Gprin eliminarea a
cel put in unei muchii. Graful din gura 1.2b este un graf part ial al grafului de
referint  a din gura 1.2a.
Figura 1.2
Subgraf. Un grafH= (X0;F) este un subgraf al grafului G= (X;E )
dac aX0XiarFeste mult imea tuturor muchiilor din Ecu propietatea c a au
ambele extremit at i ^ n X0. Subgraful Hse obt ine din graful Gprin eliminarea

3.1. NOT  IUNEA DE GRAF 39
a cel put in un nod, ^ mpreun a cu toate muchiile incidente ^ n nodurile eliminate.
Graful din gura 1.2c este un subgraf al grafului din gura 1.2a.
Figura 1.2
FieG= (X;E )  siAXo submult ime de noduri a lui X. Dac aE(A)
este mult imea tuturor muchiilor din Ecare au ambele extremit at i ^ n Aatunci
G(A) = (A;E(A))subgraf indus ^ n grafulGde submult imea de noduri A.
Graf complet. GrafulG= (X;E ) este complet dac a ^ ntre orice dou a
v^ arfurix1;x22Xexist a o muchie [ x1;x2]2E. Un graf complet cu n noduri se
noteaz aGn.^In gura 1.3 sunt reprezentate cinci grafuri complete.
Figura 1.3
Graf bipartit . Un graf este bipartit dac a mult imea nodurilor sale este
partit ionat a ^ n dou a submult imi disjuncte X1 siX2(X1[X2=X;X 1\X2=?)
astfel ^ nc^ at orice muchie e= [a;b] are extremitatea a^ nX1 si extremitatea b
^ nX2. Un graf bipartit se noteaz a ( X1[X2;E).^Intr-un graf bipartit, dou a
noduri din aceea si submult ime X1sauX2nu pot  adiacente.
Figura 1.4
^In gura 1.4 sunt reprezentate grafuri bipartite.

40 CAPITOLUL 3. TEORIA GRAFURILOR
Un graf bipartit G= (X1[X2;E) este complet dac a pentru orice v^ arf
x12X1 si orice nod x22X2exist a o muchie [ x1;x2]. Graful din gura 1.4a nu
este complet dar graful din gura 1.4b este complet.
Dac a exist a partit ie de ksubmult imi ale lui X(X=kS
i=1Xi siXi\Xj=?
8i6=j) , iar mult imea muchiilor Econt ine numai muchii cu extremit at ile ^ n
submult imi diferite atunci graful G= (X;E ) este un graf k=partit. ^In cazul
particulark= 2 rezult a graful bipartit.
3.2 Grafuri orientate
FieXo mult ime nit a nevid a  si produsul cartezian:
XX=f(x1;x2)=x1;x22Xg:
Dac ax16=x2atunci perechea ( x1;x2) difer a de perechea ( x2;x1).Prin
scrierea (x1;x2), produsul cartezian XXdene ste un sens de orientare intre
elementelex1;x22Xde lax1lax2.
FieUo submult ime nevid a a produsului cartezian XX. PerecheaG=(X;U )
este, prin denit ie, graf orientat saudigraf . Dat a ind asem anarea cu not iunea
de graf introdus a in subcapitolul 2.1, grafurile orientate vor prelua multe din
notat iile  si not iunile generale. Xeste o mult ime ale c arei elemente se numesc
noduri sauv^ arfuri iarUeste o mult ime ale c arei elemente se numesc arce. Fiind
dat arculu= (x1;x2), se numesc extremit at i ale sale nodurile x1 six2, undex1
se nume ste extremitate init ial a  six2este numit extremitate nal a . Arculueste
orientat de la nodul x1la nodulx2. Dac a acesta are forma ( x1;x1) atunci este
un arc- bucl a .
Prin urm atorul exemplu vom pune ^ n evident  a un graf orientat:
"Pentru realizarea unei lucr ari de investit ii sunt necesare o serie de activit at i
distincte: alegerea amplasamentului, ^ ntocmirea proiectului, avizarea acestuia,
aprobarea lui, contractarea utilajului tehnologic, organizarea  santierului  s.a..
^In majoritate, aceste activit at i sunt condit ionate ^ ntre ele  si execut ia ec arei
activit at i nu poate  ^ nceput a ^ nainte de terminarea altor activit at i. ^In acel si
timp sunt activit at i care se execut a ^ n paralel. Pentru conceperea grafului core-
spunz ator proiectului de investit ii se stabilesc pentru ^ nceput condit ion arile ne-
mijlocite ^ ntre activit at i. Nodurile grafului coincid cu evenimentele ^ n care se
termin a unele activit at i  si pot^ ncepe alte activit at i. Activit at ile proiectului sunt
reprezentate prin muchiile grafului. Orice activitate trebuie executat a p^ an a la
cap at ca s a poat a ^ ncepe o alta pe care ea o condit ioneaz a nemijlocit. Asemenea
grafuri sunt orientate."
Dac a un graf orientat G= (X;U ) arejXj=n sijUj=matunci graful Geste
un (n;m) -graf orientat , num arulnind ordinul grafuluiG, iarmdimensiunea
grafuluiG.
Dou a arce av^ and acelea si extremit at i sunt paralele . Un graf orientat care nu
are nici bucle nici arce paralele se nume ste graf simplu .^In aceast a lucrare vom
analiza numai grafuri orientate simple.
Reprezentare grac a. Un graf orientat G=(X;U ) se reprezint a geometric
printr-o gur a ^ n plan. Nodurile xi2Xse vizualizeaz a prin puncte ^ n plan
^ ncadrate ^ n cercuri iar arcele u= (xi;xj)2Uprin s aget i orientate cu sensul
de laxilaxj.

3.2. GRAFURI ORIENTATE 41
Exemplu. Fie X=fx1;x2;x3;x4g siU=fu1;u2;u3;u4;u5gundeu1=
(x1;x2) ,u2= (x1;x3),u3= (x1;x4),u4= (x3;x4),u5= (x3;x3). Arcul
u5= (x3;x3) este o bucl a.
Reprezentarea grac a a grafului G= (X;U ) dat prin lista de noduri G si
lista de arce Ueste cea din gura 1.5.
Figura 1.5
Gradul unui nod . FieG= (X;U ) un graf orientat si xun nod de al s au.
Aceste are dou a caracteristici:
{ gradul de intrare d(x) ca ind num arul arcelor de forma u= (z;x),u2U,
care au extremitatea nal a ^ n x.
{ gradul de ie sire d+(x) ca ind num arul arcelor de forma u= (x;z),u2U,
care au extremitatea init ial a ^ n x.
Dac ajVj=n sijUj=matunci pentru orice ( n;m) – graf orientat avem
relat ia:
nP
i=1d(xi) =nP
i=1d+(xi) =m.
Pentru graful din gura 1.5 avem: d(x1) = 0,d+(x1) = 3,d(x2) = 1,
d+(x2) = 1,d(x3) = 2 ,d+(x3) = 1,d(x4) = 4 ,d+(x4) = 0.
Dac ad(x)= 0 nodul xeste nod de intrare ^ n graf, iar dac a d+(x) = 0
nodulxeste nod de ie sire din graf. ^In graful din gura 1.5 nod de intrare este
nodulx1, iar nod de ie sire este nodul x4.
Gradul unui nod x2X, notat cud(x), ^ n cazul grafurilor orientate, este dat
de relat ia:
d(x) =d(x) +d+(x)
Adiacent  a  si incident  a . Dac a ^ ntr-un graf exist a arcul u= (x;y) de lax
laysauu= (y;x) de laylaxspunem despre nodurile x siyc a sunt adiacente .
Dou a arce sunt adiacente dac a au ^ n comun o extremitate.
Dac a except am arcele -bucl a, arcele care converg ^ ntr-un nod xde forma
(z;x) sunt arce incidente spre interior , iar arcele care ies din nodul xde forma

42 CAPITOLUL 3. TEORIA GRAFURILOR
(x;z) sunt arce incidente spre exterior . Buclele pot  considerate ca arce ce fac
parte din ambele categorii.
FieAX. Toate arcele u2U,u= (xi;xj) cuxi=2A sixj2Asunt arce
incidente spre interior ^ nA si mult imea lor se noteaz a cu !(A):
!(A) =fu= (xi;xj);u2U=xi=2A;xj2Ag:
Toate arcele u2U,u= (xi;xj) cuxi2A;xj=2Asunt arce incidente spre
exterior ^ n A  si mult imea lor se noteaz a cu !+(A):
!+(A) =fu= (xi;xj);u2U=xi2A;xj=2Ag:
Mult imea arcelor incidente ^ n A^ ntr-un graf Geste dat a de:
!(A) =!(A)[!+(A)
iarj!(A)jse nume ste gradul submult imii A^ n raport cu graful G.
Dac aA=fx1;x4g^ n graful din gura 1.5 atunci:
!(A) =f(x2;x4);(x3;x4)g,
!+(A) =f(x1;x2);(x1;x3)g,
!(A) =f(x2;x4);(x3;x4);(x1;x2);(x1;x3)g
iar gradul submult imii Aestej!(A)j= 5.
Graf part ial . FieG= (X;U ) un graf orientat. Se nume ste graf part ial ,
al grafului G, graful orientat G= (X;U) undeUU. Un graf part ial se
obt ine din graful Gprin suprimarea a cel put in un arc din U. Prin suprimarea
arcelor (x3;x2)  si (x2;x4) din graful de referint  a din gura 1.6 se obt ine graful
part ial din gura 1.6 b).
Subgraf . FieYX siVUmult imea tuturor arcelor din Ucare au am-
bele extrimit at i^ n submult imea Y. GrafulH= (Y;V) este un subgraf al grafului
G.^In acest caz subgraful Heste un graf indus sau generat de mult imea Yde
noduri. Un subgraf se obt ine din graful Gprin suprimarea nodurilor care nu
sunt cont inute ^ n Y si a arcelor corespunz atoare lor. Prin suprimarea nodului
x4 si a arcelor ( x2;x4);(x3;x4);(x4;x1) din graful din gura 1.6 a) se obt ine
subgraful din gura 1.6 c).
Figura 1.6
Grafuri simetrice  si antisimetrice . Un graf orientat G= (X;U ) este
simetric dac a pentru oricare dou a noduri xi sixjdin (xi;xj)2U)(xj;xi)2
U. Prin urmare, ^ ntr-un graf simtetric ^ ntre dou a noduri vor exista dou a arce
de sens contrar sau nici unul. ^In gura 1.7 a) este reprezentat un graf simetric.

3.2. GRAFURI ORIENTATE 43
Un graf orientat Geste antisimetric dac a pentru oricare dou a noduri xi si
xjdin (xi;xj)2U)(xj;xi)=2U.^Intr-un graf antisimetric ^ ntre dou a noduri
exist a cel mult un arc. ^In gura 1.7 b) este reprezentat un graf antisimetric.
Figura 1.7
Graf complet . Un graf orientat Geste complet dac a pentru oricare dou a
nodurixi sixjdin (xi;xj)=2U)(xj;xi)2U.^Intr-un graf complet ^ ntre
oricare dou a noduri exist a cel put in un arc. ^In gura 1.8 este reprezentat un
graf complet. Graful din gura 1.7 b) nu este complet pentru c a nu exist a arce
^ ntre nodurile x1 sx4saux3 six4.
Figura 1.8
Graf transpus . GrafulGT=(X;UT) este graf transpus grafuluiG= (X;U )
dac a arcele din UTse obt in din arcele Uprin inversarea sensului de orientare,
prin urmare din ( xi;xj)2U)(xj;xi)2UT. Operat ia de transpunere este
involutiv a: ( GT)T=G. Transpunerea unui graf are sens numai dac a este ori-
entat. Graful transpus grafului din gura 1.8 este cel din gura 1.9.

44 CAPITOLUL 3. TEORIA GRAFURILOR
Figura 1.9
Graf complementar . Un grafGC=(X;UC) este complementar grafului
G= (X;U ) dac aU[UC=XX siU\U=?. Mult imea arcelor UCeste
complementara mult imii arcelor Ufat  a de produsul cartezian XX. Operat ia
de complementaritate este involutiv a, ( GC)C=G.
Graf total . Un grafG= (X;U ) cuU=XXeste un graf total (plin) ,
^ n acest caz, graful complementar este GC= (X;?) care este un graf cu toate
nodurile izolate.
Orientare  si neorientare ^ n graf
FieG= (X;E ) un graf. O muchie a unui graf este orientat a dac a s-a denit
un sens de parcurgere a ei care face ca una din extremit at i s a e cea init ial a
iar cealalt a cea nal a. Graful G= (X;E ) este orientat (part ial orientat) dac a
o parte din muchii sau toate au fost orientate. O muchie orientat a se va numi
arc.
^In unele aplicat ii se consider a grafuri orientate, ca de exemplu ^ n teoria
drumului critic. ^In alte aplicat ii trebuie s a orient am muchiile unui graf neori-
entat (probleme de
ux), iar ^ n teoria ret elelor de transport nu este esent ial a
orientarea arcelor.
^In orice graf neorientat prin specicarea unui sens de parcurgere pe toate
muchiile sale (respectiv doar pe o parte a lor) se poate induce un graf orientat
sau part ial orientat. Datorit a faptului ca o muchie nu poate i o orientat a
dec^ at ^ n dou a moduri, ^ n cazul unui graf Gcummuchii, num arul de orient ari
posibile ale tuturor muchiilor este 2m. Pentru a specica orientarea pe o muchie
[xi;xj] atunci aceasta este echivalent a cu dou a arce ( xi;xj)  si (xj;xi) sau numai
prin unul singur.Reciproc, orice graf orientat poate  considerat neorientat prin
ignorarea orient arilor pe arce.
^In gura 1.10 a) se prezint a un graf neorientat, iar in gura 1.10 b) un graf
orientat obt inut ca una din cele 26= 64 modalit at i de orientare a muchiilor sale.

3.3. LANT  URI S I CICLURI 45
Figura 1.10
Conceptul de orientare satisface cerint ele unei relat ii de ordine ^ n X. O
relat ie de ordine se poate ^ nt^ alni doar ^ ntr-un graf orientat, ^ ntruc^ at ordinea
presupune antisimetria. Tranzit iile din care se compune o relat ie de ordine
denesc o ordine ^ ntre nodurile mult imii X.^In cazul unui graf simetric cele
dou a leg aturi pe care le cere simetria se g asesc ^ ntre dou a noduri distincte ale
grafului,gurate prin dou a arce de sens invers. Fiecare din aceste arce este
transpusul celuilalt arc. De multe ori, ^ n practic a, conceputul de orientare pe
arce ^  si pierde semnicat ia  si relat ia nu este distinct a de transpusa ei.
Cele dou a concepte se sprijin a, ^ n practic a, unul pe altul. De la un graf
neorientat se poate trece la omologul s a orientat c^ and se abordeaz a o problem a
ce impune orientarea  si invers dac a nu se precizeaz a orientarea.
3.3 Lant uri  si cicluri
FieG= (X;E ) un graf neorientat  si nodurile s sit,s2X;t2X:Unlant^ ntre
dou a noduri s sitale grafului Geste o mult ime ordonat a de noduri notat a:
L= [s;xi1;xi2;:::;xip;t];
cu propietatea c a [ s;xi1];[xi1;xi2];:::;[xip;t]2Esunt muchii ale grafului. Se
nume ste lant  o succesiune de arce, notat a L= [u1;u2;:::;up] cu propietatea c a,
ecare muchie, except^ and-o pe prima  si pe ultima, are o extremitate comun a
cu muchia precendent a  si cealalt a extremitate ^ n comun cu muchia urm atoare.
Altfel spus un lant  poate  denit prin succesiunea muchiilor adiacente care-l
formeaz a.
Noduriles sitsunt extremit at ile lant ului . De asemenea,^ n a doua reprezentare,
u1 siupsunt extremit at ile lant ului.
Num arul de muchii din care se compune un lant  reprezint a lungimea aces-
tuia. O muchie este un lant  de lungime 1. Un lant  de lungime 2 este format din
dou a muchii adiacente.

46 CAPITOLUL 3. TEORIA GRAFURILOR
Figura 1.11
^In gura 1.11, L1= [x2;x4] este un lant  de lungime 1. Lant ul L2=[x1;x2;x4,
x5;x6] este un lant  ^ ntre nodurile x1 sx6de lungime 4.
Un lant  este simplu saucompus , dac a parcurge muchiile sale o singur a dat a
sau de mai multe ori. Dac a trece o singur a dat a prin ecare din nodurile sale
atunci se nume ste elementar .
^In graful din gura 1.11, lant ul L3=[x1;x2;x5;x4;x6] este simplu  si elemen-
tar,^ n timp ce lant ul L4= [x1;x2;x5;x3;x2;x4] este compus  si nu este elementar.
Se nume ste lant  hemiltonian , un lant  care trece prin toate nodurile grafului.
Spre exemplu, ^ n gura 1.11, L5= [x1;x2;x3;x5;x4;x6] este un lant  hamilto-
nian. Un lant  simplu care parcurge odat a  si numai odat a toate muchiile grafului
este un lant  eulerian .
Un lant  este ciclu dac a extremit at ile sale coincid. Un ciclu este un lant  care
^ ncepe  si se termin a ^ n acela si nod. Un ciclu poate  simplu sau nu dup a cum
muchiile sale sunt sau nu utilizate ecare c^ ate o singur a dat a. De asemenea,
un ciclu poate  elementar sau nu dup a cum trece o singur a dat a sau nu prin
ecare din nodurile sale. Un lant  hamiltonian ^ n care extremit at ile coincid este
unciclu hamiltonian .
^In graful din gura 1.11, L6= [x2;x4;x6;x5;x2] formeaz a un ciclu iar lant ul
L7= [x1;x2;x4;x6;x5;x3;x1] este un ciclu hamiltonian.
Dac a un ciclu are un num ar par de muchii, ciclu este par  si ^ n caz contrar
ciclul este impar. Ciclul L6este par.
Teorema 3.1. (Konig) Un graf neorientat G= (X;E )este bipartit dac a  si
numai dac a nu cont ine cicluri impare.
Graful din gura 1.11 nu este bipartit deoarece cont ine ciclul L8=[x3;x2;
x5;x3] care este impar.
Grafuri conexe. GrafulG= (X;E ) se nume ste conex dac a pentru oricare
dou a noduri xi;xj2X;xi6=xjexist a un lant  cu extremit at ile xi sxj. Graful
din gura 1.11 este conex.
Propietatea "exist a un lant  cu extremit at ile xi sixjsauxi=xj"este o
relat ie de echivalent  a care ^ mparte graful G^ n clase de echivalent  a numite com-
ponente conexe . O component a conex a a unui graf Geste un subgraf maximal
de sine st at ator al lui G, el nef ac^ and parte dintr-un alt subgraf conex al grafului
G. S a consider am un nod xi2X^ n grafulG= (X;E ). Componenta conex a
relativ a laxise poate evident ia printr-o mult ime C(xi) format a din xi si din
toate nodurile legate prin lant uri de xi:

3.3. LANT  URI S I CICLURI 47
C(xi) =fxig[fxj2X/ exist a un lant  ^ ntre xi sixjg.
O component a conex a C(xi) este nevid a deoarece exist a cel put in xi2C(xi):
Fie dou a componente conexe ale grafului G,C(xi)  siC(xk). Dac aC(xi)\
C(xk)6=?exist a un nod xlastfel caxl2C(xi)  sixl2C(xk)^InC(xi) exist a
un lant  ^ ntre xi sixl si corespunz ator ^ n C(xk) exist a un lant  ^ ntre xk sixl,
deci, prin concatenare, exist a un lant  ^ ntre xi sixk. Prin urmare, xk2C(xi).
Aceasta contrazice ipoteza c a cele dou a componente conexe sunt diferite. Deci,
dou a componente diferite sunt disjuncte, ( C(xi)\C(xk) =?):
Evident,C(xi)X siS
xi2XC(xi)X. DarS
xi2XC(xi) cont ine toate
elementele mult imii X, deci,XS
xi2XC(xi).^In concluzie, din aceste dou a
relat iiX=S
xi2XC(xi). Aceast a armat ie justic a urm atoarea teorem a:
Teorema 3.2. Mult imea tuturor componentelor conexe distincte ale unui graf
Gformeaz a o partit ie a acestuia.
Conform aceste teoreme, un graf este conex dac a  si numai dac a are o singur a
component a conex a.
Graful av^ and o singur a component a conex a, orice nod al s au poate  unit
printr-un lant  cu orice alt nod, ceea ce inseamn a c a graful este conex. Dac a
ar exista cel put in dou a componente conexe, atunci nu s-ar putea uni un nod
dintr-o component a cu un nod din cealalt a component a, deci graful nu ar
conex.

48 CAPITOLUL 3. TEORIA GRAFURILOR

Capitolul 4
Partit ii ^ ntregi  si grafuri
orientate aciclice
4.1 Leg atura dintre partit iile unui^ ntreg pozitiv
 si grafurile orientate aciclice
Orice num ar ^ ntreg pozitiv npoate  descompus ^ ntr-o sum a de unul sau mai
multe numere ^ ntregi pozitive i,
n=1+2+:::+k:
Dac a ordinea numerelor ^ ntregi inu este important a, aceast a reprezentare
se nume ste partit ie a num arului ^ ntreg n, altfel, se nume ste compunere. C^ and
12:::k,
avem o compunere ascenden a . Num arul partit iilor lui neste dat de p(n),funct ia
lui Euler pentru partit ii (vezi [6]). S irul
fp(n)gn0=f1;1;2;3;5;7;11;15;22;30;42;56;77;101;135;176;:::g
este bine cunoscut ^ n literatur a [10,  sirul A000041].Pentru mai multe detalii
referitoare la p(n) se poate consulta [6].
Primii algoritmi pentru generarea partit iilor ^ ntregi au fost descoperit i de
c atre R. J. Boscovich ^ n anul 1747  si K. F. Hindenburg ^ n anul 1778, a se
vedea Dickson [8, pag. 101106]. ^In anul 2005, Lin[12] a propus patru structuri
de date pentru memorarea partit iilor ^ ntregi: dou a structuri liniare (direct a  si
multiplicativ a), o structur a arborescent a  si o structur a de tip diagram a.
Utilizarea structurilor arborescente pentru stocarea partit iilor ^ ntregi nu este
o idee chiar at^ at de recent a. Fenner  si Loizou [9] au introdus arborii binari
pentru reprezentarea partit iilor ^ ntregi ^ n 1979  si apoi s-au ocupat de generarea
partit iilor ^ ntregi cu ajutorul metodelor de parcurgere a arborilor binari, a se
vedea Fenner  si Loizou[10][11] .
Ideea utiliz arii structurilor arborescente pentru stocarea partit iilor unui num ar
^ ntreg se bazeaz a pe faptul c a dou a partit ii ale aceluia si num ar pot avea mai
multe p art i comune. De exemplu, compunerile ascendente
[1, 1, 1, 1, 1, 1]  si [1, 1, 1, 1, 2]
49

50CAPITOLUL 4. PARTIT  II ^INTREGI S I GRAFURI ORIENTATE ACICLICE
au patru p art i comune. ^In aceast a situat ie, o secvent  a de arce dintr-un arbore
poate stoca aceste p art i comune.
Lin[12] a creat structura arborescent a pentru stocarea partit iilor ^ ntregi con-
form urm atoarei reguli: r ad acina arborelui este etichetat a cu (1 ;n)  si (x0;y0) este
un descendent direct al nodului ( x;y) dac a  si numai dac a
x02fx;x+ 1;:::;y
2
;yg siy0=yx0;
unde [x] este notat ia uzual a pentru partea ^ ntreag a a lui x. Dac a x' = y
atunci (x0;y0) = (y;0) este un nod terminal. Este clar c a orice nod terminal
este de forma ( x;0);0< xn. Lin[12] a demonstrat c a [ x1;x2;:::;xk] este o
compunere ascendent a lui ndac a  si numai dac a
(x0;y0);(x1;y1);:::;(xk;yk)
este un drum care leag a r ad acina ( x0;y0) de nodul terminal ( xk;yk). Apoi,
baz andu-se pe acest fapt, a ar atat c a num arul total de noduri necesar pentru
a stoca partit iile lui neste 2p(n), iar num arul nodurilor terminale este p(n).^In
continuare, vom utiliza pentru aceast a structur a arborescent a denumirea de
arbore Lin.
Arborele Lin care stocheaz a toate partit iile num arului 6 este prezentat ^ n
Figura 1. Cum poate  utilizat acest arbore pentru a genera toate partit iile
num arului 6? Pornind de la r ad acin a, vom parcurge arborele ^ n ad^ ancime  si,
c^ and ajungem la un nod terminal, list am drumul parcurs. De exemplu,drumul
(1;6)(1;5)(1;4)(1;3)(1;2)(2;0)
leag a r ad acina arborelui de nodul terminal (2, 0). Dac a elimin am din acest
drum prima pereche  si p astr am din ecare pereche r amas a numai prima valoare,obt inem
compunerea ascendent a [1, 1, 1, 1, 2].
^In arborele Lin, descendent ii direct i ai nodului (1, n) sunt noduri de forma
(k;nk). Din regula de construire a arborilor Lin deducem c a tot i descendent ii
direct i ai nodului ( k;nk), 2kn
2
, , sunt descendent i direct i ai nodului
(1;nk). Aceast a observat ie i-a permis lui Lin[12] s a transforme acest arbore
i ntr-un graf orientat aciclic, prin eliminarea descendent ilor nodului ( k;nk) din
arbore  si crearea leg aturilor corespunz atoare^ ntre nodul ( k;nk)  si descendent ii
direct i ai nodului (1 ;nk). Structura de date astfel obt inut a este denumit a
de c atre Lin[12] diagrama partit iilor unui num ar ^ ntreg. Vom utiliza pentru
acest tip de diagram a denumirea de diagram a Lin. ^In Figura 2 este prezentat a
diagrama Lin obt inut a prin transformarea arborelui Lin din Figura 1.

4.2. DIAGRAME BINARE 51
FIGURE 1. Arborele Lin pentru num arul 6
FIGURE 2. Diagrama Lin pentru num arul 6
Este clar c a diagrama Lin este o reprezentare concis a a arborelui Lin. Din
acest motiv vom p astra pentru nodul (1, n) denumirea de nod r ad acin a, iar
pentru nodurile (k, 0), k = 1, 2, . . . , n, denumirea de noduri terminale.
De fapt, nodul r ad acin a este singurul nod din diagrama Lin care are gradul
intern zero, iar nodurile terminale sunt singurele noduri din diagrama Lin care
au gradul extern zero. Este evident c a, ^ n diagrama Lin a num arului n, exist a
p(n) drumuri ^ ntre r ad acin a  si cele n noduri terminale  si ecare dintre aceste
drumuri reprezint a o partit ie a lui n.
Lin[12] a demonstrat urm atoarea teorem a:
Teorema 4.1. Num arul nodurilor din diagrama Lin a num arului ^ ntreg pozitiv
n este egal cuh
n2
4i
+n+ 1.
Pentru a avea o imagine  si mai clar a asupra dimensiunii diagramelor Lin,
am stabilit ^ n (vezi [14] ) formula pentru num arul arcelor din diagrama Lin.
Teorema 4.2. Num arul arcelor din diagrama Lin a num arului ^ ntreg pozitiv n
este egal cu1
36n3+7
24n2+5
12n+ 1
:
4.2 Diagrame binare
Un arbore orientat este denit formal ca o mult imeAde unul sau mai multe
noduri, astfel ^ nc^ at exist a ^ n Aun nod special numit r ad acina arborelui  si cele-
lalte noduri din Asunt repartizate ^ n m0 mult imi disjuncte A1;:::;Am,
ecare mult ime ind la r^ andul ei un arbore orientat . ArboriiA1;:::;Amse
numesc subarborii r ad acinii. Dac a ordinea relativ a a subarborilor A1;:::;Am
este important a spunem c a arborele orientat este un arbore ordonat . Un ar-
bore ordonat ^ n care ecare nod are cel mult doi subarbori se nume ste arbore
binar . Arborii binari ^ n care ecare nod neterminal are exact doi subarbori
se nume ste arbore binar strict . Dac a ^ ntr-un arbore orientat  stim care dintre
noduri este r ad acin a atunci sensurile arcelor sunt complet determinate  si nu mai
este necesar a reprezentarea lor.

52CAPITOLUL 4. PARTIT  II ^INTREGI S I GRAFURI ORIENTATE ACICLICE
Este bine cunoscut faptul c a orice arbore ordonat poate  convertit ^ ntr-un
arbore binar schimb^ and leg aturile dintre noduri: primul descendent al unui nod
Adevine descendent st^ ang al nodului A, iar urm atorul frate al nodului Adevine
descendent drept al nodului A. Aplic^ and aceast a transformare asupra arborilor
Lin se obt ine un arbore binar. Elimin^ and apoi r ad acina acestui arbore binar,
obt inem un arbore binar strict care memoreaz a toate partit iile num arului ^ ntreg
n.^In Figura 3 este prezentat arborele binar strict obt inut ^ n urma transform arii
arborelui Lin din Figura 1.
Pentru a genera compunerile ascendente, parcurgem ^ n ad^ ancime arborele
binar strict pentru stocarea partit iilor. C^ and ajungem la un nod terminal, list am
din drumul care leag a r ad acina de acest nod terminal numai nodurile care sunt
succedate de descendentul st^ ang. De exemplu,
(1, 5)(1, 4)(1, 3)(2, 2)(2, 0)
este un drum care leag a nodul r ad acin a (1, 5) de nodul terminal (2, 0). Din
acest drum nodul (1, 3) este eliminat la listare deoarece este urmat de nodul
(2, 2) care este descendent drept. P astr^ and din ecare pereche r amas a numai
prima valoare, obt inem compunerea ascendent a [1, 1, 2, 2]. Pe de alt a parte,
observ am c a mai exist a dou a drumuri care leag a nodul r ad acin a (1, 5) de alte
dou a noduri terminale etichetate (2, 0):
(1, 5)(1, 4)(1, 3)(1, 2)(1, 1)(2, 0)  si (1, 5)(2, 4)(2, 2)(2, 0).
FIGURE 3. Arborele binar strict pentru stocarea partit iilor num arului 6
Aceste drumuri reprezint a compunerile ascendente
[1, 1, 1, 1, 2]  si [2, 2, 2].
Arborele binar strict pentru stocarea partit iilor num arului ^ ntreg n poate
construit dup a urm atoarea regul a: r ad acina arborelui este etichetat a cu (1,n-1),
nodul (xs;ys) este un descendent st^ ang al nodului (x, y) dac a  si numai dac a
xs=(
x; dac a 2xy
ym; altfel siys=yxs;

4.2. DIAGRAME BINARE 53
iar nodul (xd;yd) este un descendent drept al nodului (x, y) dac a  si numai dac a
xd=(
x+ 1;dac a 2 +xy
x+y;altfel siyd=x+yxd;
Arborii binar strict i pentru stocarea partit iilor ^ ntregi au fost derivat i din
arborii Lin  si sunt diferit i de arborii binari introdu si de Fenner  si Loizou. Avan-
tajele utiliz arii structurilor arborescente binare sunt bine cunoscute  si ^ n acest
caz au fost concretizate ^ n [13] prin obt inerea celui mai rapid algoritm pentru
generarea partit iilor ^ ntregi.
^In Figura 3 observ am c a subarborele st^ ang al nodului (2, 4) este identic cu
subarborele drept al nodului (1, 3). Aceast a redundant  a a informat iilor este
conrmat a de urm atoarea teorem a prezentat a ^ n [14].
Teorema 4.3. Fie (x, y) un nod intern din arborele binar strict pentru stocarea
partit iilor unui num ar ^ ntreg, astfel ^ nc^ at x>1. Dac a 2xy, atunci subarborele
st^ ang al nodului (x, y) este identic cu subarborele drept al nodului (x – 1, y – x
+ 1). Dac a 2x > y , atunci subarborele st^ ang al nodului (x, y) este identic cu
subarborele drept al nodului (y
2
, y -y
2
).
Conform acestei teoreme,^ n orice arbore binar strict pentru stocarea partit iilor
^ ntregi, subarborele st^ ang al oric arui nod intern (x, y) cu x >1 este identic cu
subarborele drept al unui nod (x', y'). Pentru orice nod intern (x, y) cu x>1,
elimin am subarborele s au st^ ang  si introducem un arc de la nodul (x, y) la de-
scendentul drept al nodului (x', y'). Astfel, obt inem un graf orientat aciclic care
a fost denumit diagrama binar a a partit iilor ^ ntregi. ^In Figura 4 este prezentat a
diagrama binar a obt inut a prin transformarea arborelui binar strict din Figura
3.
Dou a rezultate care caracterizeaz a dimensiunea diagramelor binare au fost
prezentate ^ n [14].
Teorema 4.4. Num arul nodurilor diagramei binare a partit iilor ^ ntregului
pozitiv n este egal cuh
n2
4i
+n.
Teorema 4.5. Num arul arcelor diagramei binare a partit iilor ^ ntregului pozitiv
n este egal cuh
n2
2i
.
FIGURE 4. Diagrama binar a strict pentru stocarea partit iilor num arului 6

54CAPITOLUL 4. PARTIT  II ^INTREGI S I GRAFURI ORIENTATE ACICLICE
Compar^ and Teoremele 1  si 4, nu putem spune c a diagramele binare sunt mai
eciente ^ n stocarea partit iilor ^ ntregi dec^ at diagramele Lin. Ceea ce difer a este
num arul arcelor care este considerabil mai mic ^ n cazul diagramelor binare. ^In
plus, nodurile diagramei binare a partit iilor ^ ntregului pozitiv n pot  rearanjate
^ ntr-un tablou bidimensional cun
2
+1 llinii  si n coloane, denumit tabloul com-
punerilor ascendente[14] . ^In acest tablou, ecare nod ocup a o celul a conform
urm atoarei reguli: celula indexat a ( i;j) este ocupat a de nodul (x, y) dac a  si
numai dac a
i=(x
2
+ 1;dac ay= 0;
x; altfel si j = x+ y. (5)
Este clar c a exist a celule ^ n tablou care nu sunt ocupate. Utiliz^ and Teorema
4 deducem c a num arul celulelor neocupate este un p atrat perfect,n
22( sirul
A007894 ^ n [15]) . De exemplu, conform (5), nodurile diagramei binare din
Figura 4 sunt rearanjate ^ n Figura 5.
Not am cu S(i;j)  siD(i;j) pozit iile succesorilor direct i ai nodului de pe
pozit ia (i;j) din tabloul compunerilor ascendente. T  in^ and cont de (5), deducem
c a
Si;j=(
(i;ji); pentru 3ij;
(ji
2
+ 1;ji);pentru 2ij <3i
Di;j= (i+ 1;j) , pentru 2 ij:
FIGURE 5. Tabloul compunerilor ascendente ale num arului 6
Astfel, tabloul compunerilor ascendente pentru num arul ^ ntreg pozitiv n
poate  reprezentat concis de urm atoarea matrice
 = (i;j)i=1;:::;[n=2]+1;j=1;:::;n
denit a astfel:
i;j=8
><
>:i;dac a 2ij;
j;dac ai=j
2
+ 1;
0;altfel:

4.2. DIAGRAME BINARE 55
^In [14], aceast a matrice a fost denumit a matricea compunerilor ascendente.
De exemplu, matricea compunerilor ascendente a num arului 6 este
0
BB@1 1 1 1 1 1
0 2 3 2 2 2
0 0 0 4 5 3
0 0 0 0 0 61
CCA.
OBSERVAT II S I CONCLUZII
Cea mai importan a parte pentru ecient a algoritmilor de generare a partit iilor
o reprezint a alegerea structurilor de date pentru stocarea partit iilor ^ ntregi.
Metoda gener arii partit iilor ^ ntregi prin parcurgerea structurilor arborescente
utilizate pentru stocarea lor a fost introdus a de c atre Fenner  si Loizou [9] [10]
[11].^In [13] Mircea Merca a adaptat algoritmul general pentru parcurgerea ^ n
inordine a arborilor binari la cazul particular al arborilor binari strict i pentru
stocarea partit iilor ^ ntregi  si a obt inut cel mai ecient algoritm pentru gener-
area acestora[13, Algorithm 6]. ^In [14], prin diagramele binare pentru stocarea
partit iilor se poate obt ine o versiune mai imbun at at it a pentru acest algoritm.
Not am cut1(n) timpul mediu de execut ie pentru [13, Algorithm 6], cu t2(n)
timpul mediu de execut ie pentru algoritmul Fenner-Loizou [9] [10]  si cu r(n)
raportul dintre t1(n)  sit2(n),
r(n) =t1(n)
t2(n):
^In Tabelul 1 sunt prezentate c^ ateva dintre valorile r(n) obt inute utiliz^ and
Visual C++ 2010 Express Edition pe un calculator cu procesor Intel Premium
Dual T3200 2.00 GHz. Pentru ecare algoritm, timpul mediu de execut ie a fost
obt inut ^ n urma efectu arii a zece teste. ^In cazuln= 130, se poate observa c a
timpul mediu de execut ie pentru [13, Algorithm 6] reprezint a 43,5% din timpul
mediu de execut ie al algoritmului Fenner-Loizou.
Pe de alt a parte, s-au descoperit noi inegalit at i prin analiza ecient ei algo-
ritmilor obt inut i ^ n [13]  s [14] pentru generarea partit iilor ^ ntregi, care implic a
funct ia partit iilor p(n) (se consider a p(n) = 0 pentru n<0). Inegalitatea
p(n)p(n1)p(n2) +p(n5)0; n> 0;
descoperit a  si demonstrat a ^ n [13], este utilizat a pentru a dovedi ecient a celui
mai rapid algoritm pentru generarea partit iilor ^ ntregi. Ulterior, aceast a ine-
galitate a fost prezentat a ^ n [7] ca un caz particular al unei familii innite de

56CAPITOLUL 4. PARTIT  II ^INTREGI S I GRAFURI ORIENTATE ACICLICE
inegalit at i. Urm atoarea inegalitate
p(n)5p(n3) + 5p(n5)0; n6= 3;
a fost descoperit a ^ n [14] pe parcursul efectu arii testelor de ecient  a a algorit-
milor propu si pentru generarea partit iilor ^ ntregi.Aceast a inegalitatea nu este
demonstrat a  si se a
 a ^ n stadiul de conjectur a. O variant a ^ mbun at at it a a aces-
tei inegalit at i este prezentat a ^ n urm atoarea conjectur a.
Conjectura 3.1 Fienun num ar ^ ntreg. Inegalitatea
p(n)5p(n3) + 5p(n5)p(n14)0
este adev arat a, dac a  si numai dac a n6= 3:
Pentru
xn=p(n)5p(n3) + 5p(n5)p(n14)
obt inemfxngn0=f1, 1, 2, -2, 0, 2, 1, 0, 2, 0, 2, 1, 2, 1, 4, 0, 4, 4, 5, 3 , 11, 7,
15, 15, 23, 27, 44, 44, 68, 84, 113, 135, 189, 223, 298, … g
 si se constat a experimental c a  sirul fxngn21este cresc ator. Se poate demon-
stra acest fapt?

Bibliograe
[1] Gh. Ciobanu ,Vasile Nica, Floare Mustat  a, Virginia M ar acin,
Dorin Mitrut , Cercet ari operat ionale. Optimiz ari ^ n ret ele – Teorie
 si aplicat ii economice – Editura Matrix Rom, Bucure sti 2002;
[2] Lect.Dr. Denis Ibadula, Grafuri  si combinatoric a, Note de curs
[3] Drago s-Radu Popescu, Combinatoric a  si teoria grafurilor, Bib-
lioteca Societ at ii de  stiint e matematice din Rom^ ania, Bucure st,i
2005;
[4] Valeriu Lupu, Grafuri orientate, http://www.seap.usv.ro/ va-
leriul/lupu/GRAFURI ORIENTATE.pdf;
[5] Valeriu Lupu, Grafuri neorientate, http://www.seap.usv.ro/ va-
leriul/lupu/GRAFURI NEORIENTATE.pdf;
[6] G.E. Andrews, The Theory of Partitions , Addison-Wesley, 1976;
[7] G. E. Andrews, M. Merca, The truncated pentagonal number the-
orem , J. Combin. Theory. Ser. A, 119(2012), 1639-1643;
[8] L. E. Dickson, History of the Theory of Numbers: Diophantine
Analysis , AMS Chelsea Publishing, 2002;
[9] T. I. Fenner, G. Loizou, A binary tree representation and related
algorithms for generating integer partitions , Comp. J., 23(1980),
332-337;
[10] T. I. Fenner, G. Loizou, An analysis of two related loop-free algo-
rtihms for generating integer partitions , Acta Inform., 16(1981),
237-252;
[11] T. I .Feneer, G. Loizou, The traversal related algorithms for gen-
erating integer partitions , SIAM J. Comput., 12(1983) , 551-564;
[12] R. B. Lin, Ecient data structures for storing the partitions of
integers , The 22nd Workshop on Combinatorics and Computation
Theory, Taiwan, 2005;
[13] M. Merca, Fast algorithm for generating ascending compositions ,
J. Math. Model. Algorithms, 11(2012), 89-104;
[14] M. Merca, Binary diagrams for storing ascending compositions ,
Comp. J.(2012), doi:10.1093/comjnl/bxs111;
57

58 BIBLIOGRAFIE
[15] N. J. A. Sloane, The One-Line Encyclopedia of Integer Sequences ,
available at http://oeis.org;