Generointifunktioita

Generointifunktio (GF) on työkalu, jolla jono a_n voidaan tallentaa muodollisena sarjana. Tavallinen generointifunktio A(x) määritellään A(x) = sum_{n>=0} a_n x^n. Eksponentiaalinen generointifunktio A_e(x) määritellään puolestaan A_e(x) = sum_{n>=0} a_n x^n / n!. Eri yhteyksissä voidaan käyttää myös muita muunnelmia, kuten moniulotteisia tai Dirichletin generointifunktioita.

Generointifunktioiden keskeinen idea on, että sarjan avulla voidaan käsitellä jonoa algebraisesti. Tuotteen yhteydessä saatava tulos vastaa konvoluutiota: jos A(x) = sum a_n x^n ja B(x) = sum b_n x^n, niin AB(x) = sum c_n x^n, jossa c_n = sum_{k=0}^n a_k b_{n-k}. Tämä mahdollistaa rekursioiden ja rakenteiden yhdistämisen ja usein johtaa sulkeutuneisiin kaavoihin tai helpompaan laskemiseen.

Esimerkki: fibonaccin luvut F_0 = 0, F_1 = 1 täytyy. Niiden tavallinen GF on F(x) = sum_{n>=0} F_n x^n = x/(1 - x - x^2). Tämä osoittaa, miten rekursio muuttuu rationaaliseksi funktioksi.

Sovellukset kattavat lukuisia määrällisiä ongelmia: jonoja, yhdistelmien luokittelua, polkuja, puujäsenien määrää sekä rakenteiden kymmeniä erilaisia luokkia. Generointifunktioita käytetään laajalti enumeratiivisessa combinatoricsissa sekä asymptoottisessa analyysissä, missä niillä voidaan saada sekä tarkkoja että likimääräisiä tuloksia. Monimutkaisemmissa tapauksissa hyödynnetään moniulotteisia tai erilaisia generaattorimuunnoksia, kuten EGF:itä ja multivariaatteja, sekä analyyttisiä tekniikoita.