Sprehodi s kratkimi koraki v prvem kvadrantu : magistrsko delo

Kralj, Samo (avtor), Konvalinka, Matjaž (mentor)

V delu si pogledamo sprehode s kratkimi koraki v prvem kvadrantu. Pogledamo si, koliko različnih sprehodov glede na množico možnih korakov obstaja. Za vsako množico korakov $S$ poskusimo poiskati rodovno funkcijo v treh spremenljivkah $x$, $y$ in $t$, ki nam pove, koliko je sprehodov z $n$ koraki, ki se začnejo v točki $(0, 0)$ in končajo v točki $(i, j)$, nikoli ne zapustijo prvega kvadranta in uporabijo le korake iz množice $S$. Prav tako ugotovimo, ali je dana rodovna funkcija $D$-končna ali algebraična.

• Jezik: Slovenski jezik
• Ključne besede: sprehod, rodovna funkcija, algebraičnost, D-končnost
• Vrsta gradiva: Magistrsko delo/naloga
• Tipologija: 2.09 - Magistrsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2020
• PID: 20.500.12556/RUL-121271
• COBISS.SI-ID: 32590339
• Datum objave v RUL: 02.10.2020

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Walks with short steps in the first quadrant

Izvleček

In this thesis, we look at walks with short steps confined to the first quadrant. We take a look at how many different walks there are depending on the set of available steps. For each set of steps $S$, we try to find the generating function in three variables $x$, $y$ and $t$ which tells us how many $n$ step walks are there starting from $(0, 0)$ and ending at $(i, j)$, using only the steps from set $S$ and never leaving the first quadrant. We also determine whether a given generating function is $D$-finite or algebraic.

• Ključne besede: walk, generating function, algebraic generating functions, D-finite generating functions