7/17/2019 Curs2
http://slidepdf.com/reader/full/curs2-568c322bed5e9 1/6
§2. Proprietăţi ale combinărilor. Funcţii generatoare. Numerele luiFibonacci
Pentru început vom prezenta o serie de proprietăţi ale combinărilor.Triunghiul lui Pascal este un tablou infinit care are elementul de pe coloana m+1 a liniein egal cu m
nC (v. fig. 3.
!u a"utorul lui se dau interpretări simple unor identităţi ce conţin combinări. #e e$emplu relaţia
aditivă a lui Pascal mn
mn
mn C C C
111 −−− += (1.2.1
este o regulă de calcul a elementelor unei linii folosind linia anterioară. %ceastă formulă rezultău&or din relaţia (1.1.'. Prezentăm o "ustificare combinatorială a acestei formule. e &tie cănumărul submulţimilor cu m elemente al unei mulţimi A cu n elemente este .m
nC )i$ăm unelement . Aa∈ )ie B o submulţime cu m elemente a lui A. #acă Ba∈ celelalte m*1 elementeale lui B se află printre celelalte n*1 elemente ale lui A deci B poate fi aleasă în 1
1−−mn
C moduri. ,ncazul c-nd Ba∉ atunci cele m elemente ale lui B pot fi alese dintre cele n*1 elemente ale lui Adiferite de a. #eci B se poate alege în m
nC 1− moduri. #eoarece aceste două cazuri dis"uncte
conţin toate submulţimile B cu m elemente rezultă formula (1.2.1.
elaţia (1.2.1 a fost dedusă folosind două moduri distincte de numărare a unor obiecte.%ceea&i metodă o vom utiliza pentru demonstrarea următoarelor două rezultate.
Teorema 1.5. Este adevărată următoarea identitate/
.2 1
1
−
=⋅=∑ n
n
i
in niC
(1.2.2
'
7/17/2019 Curs2
http://slidepdf.com/reader/full/curs2-568c322bed5e9 2/6
Demonstraţie. #in e$emplul 1.' se &tie că dacă { }++...+2+1 n A = atunci A are e$act inC
submulţimi cu i elemente. #eoarece numărul total al submulţimilor lui A este
nnn
i
inC 211(
0
=+=∑=
(1.2.3
iar
( ) 1222
1
2
1
2
1 −
⊂⊂⊂⊂⋅=⋅==+== ∑∑∑∑ nn
A B A B
A
A B
A
A B
nnn BC B BC B (1.2.
(1.2.2 rezultă din (1.2. &i faptul că e$istă inC submulţimi cu i elemente deci ∑∑
=⊂= n
i
in
A B
iC B1
.
Teorema 1.6. Fie .nk ≤ Atunci este adevărată următoarea identitate/
.11++
==∑ k
n
n
k i
k i C C
(1.2.
Demonstraţie. )ie mulţimea { }.1+...+2+1 += n A #acă 4+...+1+5 nk k i +∈ numărul submulţimilor lui A av-nd k +1 elemente iar cel mai mare element este i+1 este .k iC #eoarece oricesubmulţime a lui A are un cel mai mare element de aici rezultă că suma din st-nga egalităţii(1.2. este egală cu numărul submulţimilor lui A av-nd k +1 elemente.
6 metodă utilă de deducere a unor identităţi referitoare la combinări este cea bazată peformula binomului lui 7e8ton. 9a a fost utilizată în demonstrarea egalităţii (1.2.2. :om folosiaceastă metodă în demonstraţia teoremei ce urmează.
Teorema 1.7. Sunt adevărate următoarele afirmaţii/a O mulţime finită nevidă are acelai număr de su!mulţimi cu număr "ar i cu număr
im"ar de elemente;
! Are loc identitatea+1( nk
n
k i
k i
in
k iC C δ =−∑
=
− (1.2.<
unde ik δ este sim!olul lui #ronecker$
Demonstraţie. a )olosind formula binomului lui 7e8ton putem scrie pentru +1≥n
+1(11(0
impar1
par00
∑∑∑===
−=−=−=n
i
i
i
n
n
i
i
i
n
n
i
i
n
inC C C
unde prima sumă este egală cu numărul submulţimilor cu număr par de elemente iar cea de adoua al celor cu număr impar. #e aici deducem că cele două numere sunt egale. b =tiliz-nd din nou formula binomului lui 7e8ton avem
∑ ∑∑ ∑∑= =
−= =
−=
−=
−=−=+−=
n
k
k n
k i
k i
in
k in
i
i
k
k k i
k iin
n
i
iin
nn %C C %C C %C % %
00 00
1(1(1(11(
&i afirmaţia rezultă egal-nd coeficienţii puterilor lui k % în identitatea anterioară.
)uncţiile generatoare constituie un instrument eficient pentru numărarea unor obiecte sauclase de obiecte str-ns legate de teoria seriilor de puteri din analiza reală sau comple$ă.
>
7/17/2019 Curs2
http://slidepdf.com/reader/full/curs2-568c322bed5e9 3/6
)ie { }0≥nna un &ir de numere reale. 9lementele an vor fi de obicei numere naturale dar
definiţia este generală. Funcţia generatoare a &irului { }0≥nna este seria formală de puteri
+(0
∑∞
=
=n
nn %a % F
(1.2.'
seria numindu*se formală deoarece în general nu suntem interesaţi de convergenţa ei. 7umerelean se numesc coeficienţii funcţiei generatoare. #ouă funcţii generatoare se consideră egale dacă &inumai dacă au aceea&i coeficienţi.
Exemplul 1.9. )ie a0?1 &i a1?1. @ermenii &irului { }0≥nna definit prin relaţia de recurenţă
2+21 ≥+= −− naaa nnn (1.2.>se numesc numerele lui Fi!onacci. #in (1.2.> deducem că primele numere )ibonacci sunt/1123>13Aiar funcţia generatoare este în acest caz
....13>321( <32 +++++++= % % % % % % % F (1.2.B
Exemplul 1.10. #acă an?1 pentru orice n atunci funcţia generatoare a &irului { }0≥nna este
∑∞
=
=
0
.(n
n % % F (1.2.10
,n cazul c-nd e$istă un indice n0 astfel înc-t pentru orice 0nn > an?0 funcţia generatoaredevine
∑=
=0
0
(n
k
k k %a % F
(1.2.11
&i se nume&te "olinom generator a &irului { }0≥nna .
)ie ∑∞
==
0
(n
nn %a % F &i ∑
∞
==
0
(n
nn %! %& două funcţii generatoare a &irurilor { }
0≥nna &i
respectiv { }0≥n
n! . %tunci suma ( F +&( %? F ( %+&( % &i "rodusul ( F&( %? F ( %&($ sunt funcţiigeneratoare definite prin relaţiile/
+(((0
∑∞
=+=+
n
nnn %!a %& F
(1.2.12
+((0∑∞
=
=
n
nn %c % F&
(1.2.13
unde
.0
∑=
−=n
iinin !ac
(1.2.1
e poate arăta că mulţimea funcţiilor generatoare formează un inel relativ la operaţiile definite
prin relaţiile (1.2.12 &i (1.2.13. #ate două funcţii generatoare ( % F &i ( %& vom spune că( %& este inversa lui ( % F dacă 1(( = %& % F &i în acest caz se scrie
.(
1(( 1
% F % F %& == −
9vident că dacă ( %& este inversa lui ( % F &i ( % F este inversa lui
.( %&
B
7/17/2019 Curs2
http://slidepdf.com/reader/full/curs2-568c322bed5e9 4/6
Teorema 1.8. O funcţie generatoare ∑∞
==
0
(n
nn %a % F are o inversă dacă i numai dacă .00 ≠a
Dacă e%istă inversa unei funcţii generatoare' ea este unic determinată$
Demonstraţie$ #acă +00 =a din (1.2.1 deducem că pentru orice funcţie generatoare ( %& funcţia generatoare (( %& % F are termenul constant +00 =c deci 1(( ≠ %& % F &i astfel
( % F nu are o inversă.Presupunem atunci că .00 ≠a #in (1.2.1 rezultă că pentru orice n
0
1
a
!ac
!
n
i
inin
n
∑=
−−=
.(1.2.1
%leg-nd c0?1 &i +0=nc pentru +1≥n din (1.2.1 putem determina succesiv !n astfel înc-t
∑∞
==
0
(n
nn %! %& verifică relaţia 1(( = %& % F adică ( %& este inversa lui ( % F . =nicitatea
inversei rezultă din faptul că 1(( = %& % F implică (1.2.1 unde c0?1 &i +0=nc pentru .1≥nExemplul 1.11. !onsiderăm funcţia generatoare ( % F din e$emplul 1.10.. !onform teoremei1.> ( % F are o inversă ( %& . )olosind relaţia (1.2.1 se deduce u&or că
.1( % %& −= (1.2.1<
%stfel putem scrie formal +1
1(( 1
% %& % F
−== − relaţia av-nd sens în inelul funcţiilor
generatoare.6 funcţie generatoare ( % F se nume&te raţională dacă
+(
((
%(
% P % F =
(1.2.1'
adică +((( % P %( % F = unde ( % P &i ( %( sunt polinoame.
Teorema 1.9. Fie irul { }0≥nna dat "rin relaţia de recurenţă
+...2211 k nk nnn acacaca −−− +++= nCk (1.2.1>
unde 1≥k i ci sunt numere reale date$ Atunci funcţia generatoare a irului { }0≥nna este
raţională av)nd e%"resia
+
1
((
(
1
1
∑
∑
=
=−
−
−=
k
i
ii
k
iik
iik
%c
%S %c %S
% F (1.2.1B
unde 1+(1
0
≥= ∑−
=i %a %S
i
n
nni iar .0(0 = %S
Demonstraţie$ #acă D++1E k i∈
( ) .(( %S % F % %a % %a ik i
k n
inin
i
k n
nin −
∞
=
−−
∞
=− −== ∑∑
(1.2.20
%tunci din (1.2.1> &i (1.2.20
10
7/17/2019 Curs2
http://slidepdf.com/reader/full/curs2-568c322bed5e9 5/6
( ) ++=++++==− ∑∑∑ ∞
=−
∞
=−−−
∞
=..........(( 1111
k n
nn
k n
nk nk inin
k n
nnk %ac %acacac %a %S % F
( ) ( ) ++−++−=++ −−∞
=−
∞
=− ∑∑ ...((...((... 11 %S % F %c %S % F %c %ac %ac ik
iik
k n
nk nk
k n
nini
( ) ∑∑ = −= −
=−
k
iik
i
i
k
i
i
i
k
k %S %c % F %c %S % F %c 110 +((((
de unde rezultă (1.2.1B.
%leg-nd k ?2 în teorema 1.B se obţine rezultatul ce urmează.
orolar 1.1. Fie irul { }0≥nna dat "rin relaţia de recurenţă
2211 −− += nnn acaca (1.2.21
unde c1 i c2 sunt numere reale date$ Atunci funcţia generatoare a irului { }0≥nna este raţională
av)nd e%"resia
( ).
1( 2
21
1010
%c %c
%caaa
% F −−
−+= (1.2.22
Exerciţiul 1.1. e consideră punctele din plan ce au coordonate numere întregi (laticea !!× &itoate drumurile ce unesc astfel de puncte av-nd următoarele proprietăţi/
a un drum este de forma (ud s adică el conţine doar segmente ce urcă au direcţia spredreapta sau spre st-nga;
b un drum porne&te din origine iar lungimea lui (suma lungimilor segmentelor componente este egală cu n;
c un drum nu trece de două ori prin acela&i punct.)ie f (n numărul acestor drumuri. ă se găsească funcţia generatoare a &irului { } 0( ≥nn f unde se
consideră f (0?1.Soluţie. #in a rezultă că f (1?3. )ie .2≥n 6rice drum din cele considerate se termină cu unulsau două segmente de lungime egală cu unu de forma u dd ss ud sau us deoarece trebuieîndeplinită condiţia c. 6bservăm că e$istă f (n*1 de astfel de drumuri ce se termină cu unsegment de forma u. 6rice drum de tipul considerat de lungime n*1 se termină cu un segment deforma u d sau s &i astfel e$istă f (n*1 de drumuri considerate de lungime n care se termină cusegmente de forma ud dd sau ss. %poi se observă că e$istă f (n*2 de drumuri considerate ce setermină cu segmente de forma us. %stfel
.2(1(2( −+−= n f n f n f
%plic-nd corolarul 1.1 deducem că funcţia generatoare căutată este
.21
1(
2 % %
% % F
−−
+=
#at un &ir prin relaţia de recurenţă (1.2.1> i se ata&ează ecuaţia+...2
21
1 k k k k c %c %c % +++= −− (1.2.23
numită ecuaţia caracteristică asociată. e poate demonstra următorul rezultat important privindreprezentarea termenilor &irurilor date printr*o relaţie de recurenţă.
11
7/17/2019 Curs2
http://slidepdf.com/reader/full/curs2-568c322bed5e9 6/6
Teorema 1.10 (Fagrange. Fie irul { }0≥nna dat "rin relaţia de recurenţă (1.2.1> unde 1≥k
i ci sunt numere reale date$ Presu"unem că ecuaţia caracteristică (1.2.23 are k rădăcini
distincte .+...++ 21 k α α α Atunci e%istă numerele reale k !!! +...++ 21 astfel *nc)t "entru orice n
....2211
nk k
nnn !!!a α α α +++= (1.2.2
Exerciţiul 1.". )olosind teorema lui Fagrange să se determine forma numerelor lui )ibonacci. Soluţie. 9cuaţia caracteristică asociată relaţiei de recurenţă (1.2.> este 12 += % % cu rădăcinile
.2
31+
2
3121
+=
−= α α #in teorema lui Fagrange deducem că +2211
nnn !!a α α += unde 21+!!
sunt numere reale. #eoarece 110 == aa obţinem sistemul
+1
1
2211
21
=+=+
α α !!
!!
cu soluţiile .1
+1
12
12
12
21
α α
α
α α
α
−−
=−−
= !! #eci2
1+
2
121
+=
−= !! &i astfel numerele lui
)ibonacci sunt date de relaţia.
2
1
2
1
2
1
2
1nn
na
+⋅
++
−⋅
−= (1.2.2
12