Funksionet gjeneratrisa

Funksionet gjeneratrisa janë seri formale potenciale koeficientët e të cilave japin informacione për vargjet a_n 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 a_n i kemi këto lloje gjeneratrisash

G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.

(funksioni gjeneratrisë i zakonshëm)

EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.

(funksioni gjeneratrisë eksponencial)

LG(a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.

(seria e Lambertit)

DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.

(seria Dirichlet)

Shembuj

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

\sum _{n\in \mathbf {N} }X^{n}={1 \over 1-X}.

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

\sum _{n\in \mathbf {N} }a^{n}X^{n}={1 \over 1-aX},

dhe në veçanti

\sum _{n\in \mathbf {N} }(-1)^{n}X^{n}={1 \over 1+X}.

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