Funksionet gjeneratrisa

Funksionet gjeneratrisa janë seri formale potenciale koeficientët e të cilave japin informacione për vargjet an të indeksuara me numra natyral. Gjeneratrisat shpesh mund të shprehen me formula eksplicite, si funksione të një argumenti formal x. 

 Llojet e funksioneve gjeneratrisa 

Disa nga llojet e F.G. janë 

 Funksione gjeneratrisa të zakonshme 
 Funksione gjeneratrisa eksponenciale
 Seritë e Lambertit
 Seritë e Bellit
 Seri të Dirichlet etj

Ç'do vargu mund ti shoqërojmë një funksion gjenerues të secilit prej tipeve të përmendura më lartë se cilin lloj do t'ia shoqërojmë varet nga natyra e problemit që e shqyrtojmë dhe nga natyra e vargut që prodhon ai problem.

Për vargun an i kemi këto lloje gjeneratrisash

 (funksioni gjeneratrisë i zakonshëm) 

 (funksioni gjeneratrisë eksponencial)

 (seria e Lambertit)

 (seria Dirichlet)

 Shembuj 

Vargu konstant 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., ka gjeneratrisën

Vargu gjeometrik 1,a,a2,a3,... për ç'do konstant a e ka gjeneratrisën

dhe në veçanti

 Zbatimi 

Funksionet gjeneruese përdoren për

 Gjetjen e formulave eksplicite kur vargu është dhënë me një relacion rekurent p.sh Vargu i Fibonaccit
 Gjetjen e lidhjeve në mes vargjeve.
 Zgjidhjen e problemeve në kombinatorikën numerike.
 Gjetjen e shumave të serive të pafundme numerike etj.

 Referimet 

 Herbert S. Wilf, Generatingfunctionology (Second Edition) (1994) Academic Press. ISBN 0-12-751956-4. 

 Donald E. Knuth, The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition) Addison-Wesley. ISBN 0-201-89683-4. Section 1.2.9: Generating Functions, pp.87–96.

 Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics. A foundation for computer science (Second Edition) Addison-Wesley. ISBN 0-201-55802-5. Chapter 7: Generating Functions, pp. 320–380

 Lidhje të jashtme 

 Generating Functions, Power Indices and Coin Change 
 Generatingfunctionology PDF download page
 1031 Generating Functions

Kategoria:Kombinatorikë