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

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