Generointifunktioiden

Generointifunktioiden käsite viittaa tapaan tallentaa jonoa a_n koeffisientteina muodossa F(x) = sum_{n≥0} a_n x^n. Näitä funktioita voidaan tarkastella formal power series - muodossa tai analyyttisesti. Generointifunktioiden avulla voidaan jonoja käsitellä ja löytää niiden ominaisuuksia helpommin, erityisesti kombinaatorisissa ongelmissa ja rekursioiden ratkaisemisessa.

Tyypit: Tavalliset generointifunktiot (ordinary generating functions, OGF) ovat muotoa F(x) = sum_{n≥0} a_n x^n. Eksponentiaalinen generointifunktio (exponential generating function, EGF) on A(x) = sum_{n≥0} a_n x^n / n!. Todennäköisyysgenerointifunktio (probability generating function, PGF) on G(z) = sum_{n≥0} p_n z^n ja kuvaa tietyn todennäköisyysjakauman a_n. Monivariableiset generaattorit laajentavat käsitteen useisiin muuttujiin.

Operaatioita ja tuloksia: Lineaarisuus pätee, ja kahden generointifunktion tulo vastaa jonoa, jonka n:nnen termin on konvoluutio summaa a_k b_{n-k}. Derivointi tuottaa n a_n, joten F'(x) liittyy jonoihin. Substituutio vastaa rakenteiden yhdistämistä. EGFiä käytetään usein kirjattujen rakenteiden (labelled structures) käsittelyyn, kun taas OGF:t soveltuvat yleisempiin tilanteisiin.

Esimerkkejä: Catalan-luvut C_n voivat olla selitettävissä OGFin avulla, jonka sulkeva generoattori on C(x) = (1 - sqrt(1-4x))/(2x). Fibonacci-luvut F_n saavat OGF:n F(x) = x/(1 - x - x^2). PGF:t voivat auttaa jakaumien ja momenttien tutkimisessa derivaattojen avulla.

Sovellukset kattavat rekursionratkaisun, yhdyskuntien ja rakenteiden laskennan sekä analyyttisen omaisuuden tutkimisen combinatoricsissa sekä todennäköisyyksien analyysissä. Formal power series -asento korostaa algebraista käsittelyä, kun taas analyyttiset generointifunktiot avaavat konvergenssi- ja asymptottisia näkökulmia.