Funksionet gjeneratrisa

Nga Wikipedia, enciklopedia e lirë
Shko te: navigacion, kërko

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[redakto | redakto tekstin burimor]

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

G(a_n;x)=\sum_{n=0}^{\infty}a_nx^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[redakto | redakto tekstin burimor]

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

\sum_{n\in\mathbf{N}}X^n={1\over1-X}.

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

\sum_{n\in\mathbf{N}}a^nX^n={1\over1-aX},

dhe në veçanti

\sum_{n\in\mathbf{N}}(-1)^nX^n={1\over1+X}.

Zbatimi[redakto | redakto tekstin burimor]

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.

Referencat[redakto | redakto tekstin burimor]

  • 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.

Lidhje të jashtme[redakto | redakto tekstin burimor]