Counting lattice paths

Repozytorium Centrum Otwartej Nauki

pl | en
 
 

Pokaż uproszczony rekord

dc.contributor.advisor Szepietowski, Andrzej
dc.contributor.author Dziemiańczuk, Maciej [APD]
dc.date.accessioned 2016-10-08T00:05:44Z
dc.date.available 2016-10-08T00:05:44Z
dc.date.issued 2015-10-01
dc.identifier.uri https://depotuw.ceon.pl/handle/item/1719
dc.description.abstract A lattice path is a finite sequence of points p0,p1,...,pn in Z times Z, and a step of the path is the difference between two of its consecutive points, i.e., pi - p(i-1). In this thesis, we consider lattice paths running between two fixed points and for which the set of allowable steps contains the vertical step (0,-1) and some number (possibly infinite) of non-vertical steps (1,k), with k in Z. These paths generalize the well-studied simple directed lattice paths which are composed of only non-vertical steps.This thesis is divided into two parts.In the first part (Chapter 2), we show that certain families of paths with vertical steps can be coded by weighted simple directed lattice paths (without this vertical step). Several results for paths with vertical steps are obtained and applied to three special families of paths connected with Lukasiewicz, Raney, and Dyck paths.The second part of the thesis (Chapter 3) is devoted to the study of plane multitrees which are defined as weighted unlabeled rooted trees in which the order of sons is significant. We show that there is a one-to-one correspondence between plane multitrees and Raney lattice paths. This correspondence is the main tool to derive several combinatorial and statistical properties of plane multitrees.
dc.description.abstract Ścieżka kratowa to skończony ciąg punktów p0,p1,...,pn ze zbioru Z^2, natomiast segment ścieżki to różnica pi – p(i-1) dwóch kolejnych punktów ścieżki. W tej rozprawie badamy ścieżki pomiędzy dwoma ustalonymi punktami, dla których zbiór dozwolonych segmentów zawiera segment wertykalny (0,-1) oraz pewną przeliczalną liczbę segmentów niewertykalnych (1,k), gdzie k jest liczba całkowitą. Ścieżki te uogólniają dobrze znane z literatury tak zwane proste ścieżki skierowane (ang. simple directed lattice paths), które składają się jedynie z segmentów niewertykalnych.Niniejsza rozprawa podzielona jest na dwie części. W pierwszej części (Rozdział 2), pokazujemy, że pewne rodziny ścieżek z segmentami wertykalnymi możemy kodować za pomocą ważonych prostych ścieżek skierowanych. Zaprezentowany zostanie szereg rezultatów dla ogólnego przypadku, które zostaną następnie zastosowane dla trzech szczególnych rodzin ścieżek związanych ze ścieżkami Łukasiewicza, Raneya i Dycka.Druga część rozprawy (Rozdział 3) poświęcona jest badaniu pewnych własności multidrzew porządkowych, które definiuje się jako nieetykietowane ukorzenione drzewa, w których dodatkowo ustala się porządek synów oraz krawędziom przypisuje liczby naturalne. Zamiast zajmować się bezpośrednio tymi strukturami, pokażemy bijekcję pomiędzy drzewami porządkowymi a ścieżkami Raneya. Dzięki tej bijekcji otrzymany zostanie szereg kolejnych wyników dla multidrzew.
dc.language.iso en
dc.rights info:eu-repo/semantics/restrictedAccess
dc.subject lattice paths
dc.subject plane trees
dc.subject bijective combinatorics
dc.subject ścieżki kratowe
dc.subject drzewa porządkowe
dc.subject kombinatoryka bijektywna
dc.title Counting lattice paths
dc.title.alternative Zliczanie ścieżek kratowych
dc.type info:eu-repo/semantics/doctoralThesis
dc.contributor.department Wydział Matematyki, Informatyki i Mechaniki
dc.date.defence 2016-10-20
dc.identifier.apd 18943
dc.description.osid 249401
dc.contributor.email

Plików w tej pozycji

Ta pozycja pokazuje się w tej kolekcji(ach)

Pokaż uproszczony rekord

Szukaj w repozytorium


Szukanie zaawansowane

Przeglądaj

Moje konto

Statystyki