curs2

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


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


)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


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


( ) ++=++++==− ∑∑∑ ∞

=−

∞

=−−−

∞

=..........(( 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


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

curs2

Documents