Sprehodi s kratkimi koraki v prvem kvadrantu : magistrsko delo

Kralj, Samo (author), 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.

• Language: Slovenian
• Keywords: sprehod, rodovna funkcija, algebraičnost, D-končnost
• Work type: Master's thesis/paper
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2020
• PID: 20.500.12556/RUL-121271
• COBISS.SI-ID: 32590339
• Publication date in RUL: 02.10.2020

Secondary language

• Language: English
• Title: Walks with short steps in the first quadrant

Abstract

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.

• Keywords: walk, generating function, algebraic generating functions, D-finite generating functions