On a generalisation of k-Dyck paths
Date
2019-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: (Refer to full text abstract for symbols that did not transfer correctly). We consider a family of non-negative lattice paths consisting of the step set f(1; 1); (1;k)g called k-Dyck paths, which are enumerated by the generalised Catalan numbers 1 (k+1)n+1 (k+1)n+1
n . By removing the non-negativity condition but restricting the path to stay above the line y = t we obtain a family of lattice paths called kt-Dyck paths which are enumerated by `generalised generalised Catalan numbers
t + 1 (k + 1)n + t + 1 (k + 1)n + t + 1 n : We provide proofs of the enumeration of these paths by means of a bijection, the kernel method, the cycle lemma, and the symbolic method. Analysis of parameters associated with the paths is also performed using symbolic equations
{ particularly the number of peaks, the number of valleys, and the number of returns. These kt-Dyck paths nd application in enumerating a family of walks in the quarter plane (Z 0 Z 0) with step set f(1; 1); (1;k +1); (k; 0)g. Such walks can be decomposed into ordered pairs of kt-Dyck paths and thus their enumeration can be proved via a simple bijection. Through this bijection some parameters in kt-Dyck paths are preserved. Finally, we discuss two different families of lattice paths, S-Motzkin and T-
Motzkin paths, which are related to kt-Dyck paths when k = 2 along with t = 0 and t = 1. We provide bijections between these paths and other combinatorial objects, and perform analysis of parameters in these paths.
AFRIKAANSE OPSOMMING: (Verwys na volteks opsomming vir simbole wat nie korrek oorgeskryf het nie). Ons beskou 'n familie van nie-negatiewe roosterpaaie wat bestaan uit die stap- versameling f(1; 1); (1;k)g genoem k-Dyck paaie, wat deur die veralgemeende Catalan getalle, 1 (k+1)n+1 (k+1)n+1 n , getel word. Deur die nie-negatiwiteitsvereiste te verwyder, maar die pad tot bokant die lyn y = t te beperk kry ons 'n fami- lie roosterpaaie genaamd kt-Dyck paaie wat getel word deur `veralgemeende' veralgemeende Catalan getalle t + 1 (k + 1)n + t + 1 (k + 1)n + t + 1 n : Ons lewer 'n bewys van die aftelling van hierdie paaie deur middel van 'n bijeksie, die kernmetode, die sikluslemma en die simboliese metode. Analise van parameters wat met die paaie geassosieer word, word ook uitgevoer met behulp van simboliese vergelykings { veral die aantal pieke, die aantal valleie en die aantal terugkomste. Hierdie kt-Dyck paaie vind 'n toepassing in 'n familie van wandelinge in die kwartvlak (Z 0 Z 0) met stapversameling f(1; 1); (1;k + 1); (k; 0)g. Sulke wandelinge kan ontleed word in geordende pare kt-Dyck paaie en dus kan hul aftelling deur middel van 'n eenvoudige bijeksie bewys word. Deur hierdie bijeksie word 'n paar parameters in kt-Dyck paaie bewaar. Laastens bespreek ons twee verskillende families van roosterpaaie, S-Motzkin en T-Motzkin paaie, wat verband hou met kt-Dyck paaie wanneer k = 2 saam met t = 0 en t = 1. Ons bied bijeksies tussen hierdie paaie en ander kom- binatoriese voorwerpe, en doen 'n analise van parameters op hierdie paaie.
AFRIKAANSE OPSOMMING: (Verwys na volteks opsomming vir simbole wat nie korrek oorgeskryf het nie). Ons beskou 'n familie van nie-negatiewe roosterpaaie wat bestaan uit die stap- versameling f(1; 1); (1;k)g genoem k-Dyck paaie, wat deur die veralgemeende Catalan getalle, 1 (k+1)n+1 (k+1)n+1 n , getel word. Deur die nie-negatiwiteitsvereiste te verwyder, maar die pad tot bokant die lyn y = t te beperk kry ons 'n fami- lie roosterpaaie genaamd kt-Dyck paaie wat getel word deur `veralgemeende' veralgemeende Catalan getalle t + 1 (k + 1)n + t + 1 (k + 1)n + t + 1 n : Ons lewer 'n bewys van die aftelling van hierdie paaie deur middel van 'n bijeksie, die kernmetode, die sikluslemma en die simboliese metode. Analise van parameters wat met die paaie geassosieer word, word ook uitgevoer met behulp van simboliese vergelykings { veral die aantal pieke, die aantal valleie en die aantal terugkomste. Hierdie kt-Dyck paaie vind 'n toepassing in 'n familie van wandelinge in die kwartvlak (Z 0 Z 0) met stapversameling f(1; 1); (1;k + 1); (k; 0)g. Sulke wandelinge kan ontleed word in geordende pare kt-Dyck paaie en dus kan hul aftelling deur middel van 'n eenvoudige bijeksie bewys word. Deur hierdie bijeksie word 'n paar parameters in kt-Dyck paaie bewaar. Laastens bespreek ons twee verskillende families van roosterpaaie, S-Motzkin en T-Motzkin paaie, wat verband hou met kt-Dyck paaie wanneer k = 2 saam met t = 0 en t = 1. Ons bied bijeksies tussen hierdie paaie en ander kom- binatoriese voorwerpe, en doen 'n analise van parameters op hierdie paaie.
Description
Thesis (MSc)--Stellenbosch University, 2019.
Keywords
Combinatorial analysis, Lattice paths, Combinational enumeration problems, Dyck paths, UCTD, Catalan numbers (Mathematics)