Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
On a generalisation of k-Dyck paths
Thesis (MSc)--Stellenbosch University, 2019.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2019
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613990000001024 |
|---|---|
| access_status_str | Open Access |
| author | Selkirk, Sarah Jane |
| author2 | Wagner, Stephan |
| author_browse | Selkirk, Sarah Jane Wagner, Stephan |
| author_facet | Wagner, Stephan Selkirk, Sarah Jane |
| author_sort | Selkirk, Sarah Jane |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2019. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/107091 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:44:55.028Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2019 |
| publishDateRange | 2019 |
| publishDateSort | 2019 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/107091 On a generalisation of k-Dyck paths Selkirk, Sarah Jane Wagner, Stephan Prodinger, Helmut Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Combinatorial analysis Lattice paths Combinational enumeration problems Dyck paths Catalan numbers (Mathematics) UCTD Thesis (MSc)--Stellenbosch University, 2019. 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. Masters 2019-11-18T23:02:24Z 2019-12-11T06:46:53Z 2019-11-18T23:02:24Z 2019-12-11T06:46:53Z 2019-12 Thesis http://hdl.handle.net/10019.1/107091 en_ZA Stellenbosch University vi, 87 pages application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Combinatorial analysis Lattice paths Combinational enumeration problems Dyck paths Catalan numbers (Mathematics) UCTD Selkirk, Sarah Jane On a generalisation of k-Dyck paths |
| title | On a generalisation of k-Dyck paths |
| title_full | On a generalisation of k-Dyck paths |
| title_fullStr | On a generalisation of k-Dyck paths |
| title_full_unstemmed | On a generalisation of k-Dyck paths |
| title_short | On a generalisation of k-Dyck paths |
| title_sort | on a generalisation of k dyck paths |
| topic | Combinatorial analysis Lattice paths Combinational enumeration problems Dyck paths Catalan numbers (Mathematics) UCTD |
| url | http://hdl.handle.net/10019.1/107091 |
| work_keys_str_mv | AT selkirksarahjane onageneralisationofkdyckpaths |