Counting lattice paths

Ś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.

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.