Rodovne funkcije

Uvod

Definicija:

Naj bo zaporedje v . Rodovna funkcija zaporedja je formalna potenčna vrsta .

Zgledi:

Definicija:

Naj bo A(z) rodovna funkcija zaporedja in B(z) rodovna funkcija zaporedja .

Potem definiramo:

• A(z) + B(z) za zaporedje
• λA(z) + μB(z) za zaporedje
• A(z)B(z) za zaporedje (konvolucija zaporedij)

Definicija:

Odvod formalne potenčne vrste je potenčna vrsta

Trditev:

Naj bo A(z) rodovna funkcija zaporedja . Vzemimo . potem je rodovna funkcija zaporedja enaka:

Zgledi:

Reševanje rekurzivnih enačb

Postopek:

1. Rekurzivno enačbo pomnožimo z zⁿ in seštejemo po vseh n. Vse vstope neznanega zaporedja izračunamo s pripadajočo rodovno funkcijo ali iz začetnih pogojev.
2. Rešimo dobljeno enačbo za rodovno funkcijo.
3. Rodovno funkcijo razvijemo v potenčno vsoto in odčitamo koeficiente.

Fibonaccijeva števila

F(z) - rodovna funkcija

F_n = F_{n − 1} + F_{n − 2}

F(z) − F₁z − F₀ = z(F(z) − F₀) + z²F(z)

F(z) − z = zF(z) + z²F(z)

...

Catalanova števila

Interpretacija 1: na koliko načinov lahko postavimo n parov oklepajev v produktu n+1 števil?

Interpretacija 2: na koliko načinov lahko trianguliramo konveksen n-kotnik (triangulacija - n-kotnik razdelimo z n - 3 diagonalami na trikotnike. Triangulacijo lahko interpetiramo tudi kot barvanje drevesa z n listi.)

Mathworld - Catalan Numbers

Štetje z rodovnimi funkcijami

- razred objektov (za vsak objekt poznamo njegovo velikost)

a_n - število objektov iz , ki so velikosti n

Naj bosta razreda objektov. Potem je:

disjunktivna unija

kartezični produkt parov , Velikost para pa je vsota velikosti posameznih elementov.

Naj bo A(z) rodovna funkcija za in B(n) rodovna funkcija za . Potem velja:

• A(z) + B(z) je rodovna funkcija za
• A(z)B(z) je rodovna funkcija za
• je rodovna funkcija za končno zaporedje iz