Algebraične rodovne funkcije

OPRAVŠ, LUKA (author), Konvalinka, Matjaž (mentor)

Kadar preučujemo neko zaporedje, si pogosto pomagamo tako, da ga predstavimo z rodovno funkcijo. Rodovno funkcijo lahko potem zapišemo v kakšni enačbi, iz katere lahko izpeljemo različne lastnosti zaporedja. To nam pomaga pri računanju členov našega zaporedja in iskanju zvez, ki veljajo zanje. Veliko kombinatoričnih problemov daje preštevalno zaporedje z rodovno funkcijo, ki ustreza kakšni D-končni enačbi. Iz take enačbe lahko izpeljemo linearno rekurzivno enačbo s polinomskimi koeficienti, ki ji zadoščajo vsi dovolj pozni členi našega zaporedja. Taki rekurzivni enačbi pravimo P-rekurzija in z njo lahko člene našega zaporedja računamo zelo hitro, poleg tega pa nam pomaga bolje razumeti problem, s katerim se ukvarjamo. D-končno enačbo, ki ji ustreza rodovna funkcija našega zaporedja, je običajno težko uganiti iz samega opisa problema. Izpeljemo jo lahko iz algebraične enačbe, ki jo dobimo iz preprostih rekurzivnih zvez, ki veljajo za naše zaporedje. Začetne člene zaporedja, ki jih potrebujemo za uporabo P-rekurzije, lahko izračunamo direktno iz algebraične enačbe, s primerjavo koeficientov pri potencah x. V diplomski nalogi je predstavljen program, ki sprejme algebraično enačbo in poišče P-rekurzijo ter z njo hitro izračuna izbrano število začetnih členov katerekoli izmed rešitev dane algebraične enačbe.

• Language: Slovenian
• Keywords: kombinatorika, rodovne funkcije, algebraične rodovne funkcije, D-končne rodovne funkcije, P-rekurzija
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science ; FMF - Faculty of Mathematics and Physics
• Year: 2022
• PID: 20.500.12556/RUL-140621
• COBISS.SI-ID: 124538627
• Publication date in RUL: 16.09.2022

Secondary language

• Language: English
• Title: Algebraic generating functions

Abstract

When studying a sequence, it is often helpful to represent it with a generating function. The generating function can then be used in equations from which various properties of the sequence can be derived. From such equations we can often compute the terms of our sequence and derive relations that apply to them. Many combinatorial counting problems can be represented with a generating function that solves some D-finite equation. From such an equation, we can derive a linear recursive equation with polynomial coefficients that holds for all sufficiently late coefficients of our sequence. Such a recursive equation is called a P-recursion, and with it we can calculate the terms of our sequence quickly. It also helps us better understand our problem. It is often difficult to guess the D-finite equation from the problem description itself. We can derive it from an algebraic equation that can be obtained from simple recursive relations that hold for our sequence. The initial terms of the sequence that we need to use the P-recursion can be computed directly from the algebraic equation by comparing the coefficients at powers of x. In this diploma thesis, we present a program that accepts an algebraic equation and finds the P-recursion, and with it quickly computes the selected number of initial terms of any solution of the given algebraic equation.

• Keywords: combinatorics, generating functions, algebraic generating functions, D-finite generating functions, P-recursion