Genereringsfunksjon

Genereringsfunksjon, eller genereringsfunksjon i kombinatorikk, er et verktøy som representerer en tallfølge ved hjelp av en potensrekke. Den vanligste typen er den ordinære genereringsfunksjonen (OGF): G(x) = sum_{n>=0} a_n x^n. Koeffisientene a_n gjenspeiler antallet objekter eller forekomster i posisjon n. Arbeidet kan behandles som en formell serie uten krav til konvergens, eller som en analytisk funksjon i et lite område rundt 0.

En annen vanlig type er den eksponensielle genereringsfunksjonen (EGF): E(x) = sum_{n>=0} a_n x^n / n!. EGF-er brukes når objekter vurderes med ordnede etiketteringer eller der symmetri og merkeprosesser spiller en rolle. Forskjellen mellom OGF og EGF ligger i vektingen av orden og strukturelle egenskaper.

Bruksområder for genereringsfunksjoner er brede. De brukes til å telle kombinatoriske objekter, løse rekursjoner og finne lukkede formeler for sequencelementer. Innen sannsynlighet brukes ofte sannsynlighetsgenereringsfunksjoner, som sum p_n x^n, for å beskrive utfall og karakterisere fordelinger. Algebraiske operasjoner på genereringsfunksjoner svarer ofte til kombinatoriske operasjoner: produkt representerer kombinasjoner av uavhengige strukturer, mens derivasjon ogUpdating av variabler kan endre tellingen på veldefinerte måter.

Eksempelvis oppgir den ordinære genereringsfunksjonen for Fibonacci-tallene F_0 = 0, F_1 = 1 og F_n = F_{n-1} + F_{n-2} for n ≥ 2 at F(x) = x / (1 - x - x^2). For tallfølgen der a_n = 1 for alle n, er G(x) = 1/(1 - x). Disse eksemplene viser hvordan koeffisientene i rekker gir tellende informasjon.