Combinatorics of oriented trees and tree-like structures
| dc.contributor.advisor | Wagner, Stephan | en_ZA |
| dc.contributor.author | Okoth, Isaac Owino | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Department of Mathematical Sciences. | en_ZA |
| dc.date.accessioned | 2015-05-20T09:27:58Z | |
| dc.date.available | 2015-05-20T09:27:58Z | |
| dc.date.issued | 2015-03 | en_ZA |
| dc.description | Thesis (PhD)--Stellenbosch University, 2015. | en_ZA |
| dc.description.abstract | ENGLISH ABSTRACT : In this thesis, a number of combinatorial objects are enumerated. Du and Yin as well as Shin and Zeng (by a different approach) proved an elegant formula for the number of labelled trees with respect to a given in degree sequence, where each edge is oriented from a vertex of lower label towards a vertex of higher label. We refine their result to also take the number of sources (vertices of in degree 0) or sinks (vertices of out degree 0) into account. We find formulas for the mean and variance of the number of sinks or sources in these trees. We also obtain a differential equation and a functional equation satisfied by the generating function for these trees. Analogous results for labelled trees with two marked vertices, related to functional digraphs, are also established. We extend the work to count reachable vertices, sinks and leaf sinks in these trees. Among other results, we obtain a counting formula for the number of labelled trees on n vertices in which exactly k vertices are reachable from a given vertex v and also the average number of vertices that are reachable from a specified vertex in labelled trees of order n. In this dissertation, we also enumerate certain families of set partitions and related tree-like structures. We provide a proof for a formula that counts connected cycle-free families of k set partitions of {1, . . . , n} satisfying a certain coherence condition and then establish a bijection between these families and the set of labelled free k-ary cacti with a given vertex-degree distribution. We then show that the formula also counts coloured Husimi graphs in which there are no blocks of the same colour that are incident to one another. We extend the work to count coloured oriented cacti and coloured cacti. Noncrossing trees and related tree-like structures are also considered in this thesis. Specifically, we establish formulas for locally oriented noncrossing trees with a given number of sources and sinks, and also with given indegree and outdegree sequences. The work is extended to obtain the average number of reachable vertices in these trees. We then generalise the concept of noncrossing trees to find formulas for the number of noncrossing Husimi graphs, cacti and oriented cacti. The study is further extended to find formulas for the number of bicoloured noncrossing Husimi graphs and the number of noncrossing connected cycle-free pairs of set partitions. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING : In hierdie tesis word ’n aantal kombinatoriese objekte geenumereer. Du en Yin asook Shin en Zeng (deur middel van ’n ander benadering) het ’n elegante formule vir die aantal geëtiketteerde bome met betrekking tot ’n gegewe ingangsgraadry, waar elke lyn van die nodus met die kleiner etiket na die nodus met die groter etiket toe georiënteer word. Ons verfyn hul resultaat deur ook die aantal bronne (nodusse met ingangsgraad 0) en putte (nodusse met uitgangsgraad 0) in ag te neem. Ons vind formules vir die gemiddelde en variansie van die aantal putte of bronne in hierdie bome. Ons bepaal verder ’n differensiaalvergelyking en ’n funksionaalvergelyking wat deur die voortbringende funksie van hierdie bome bevredig word. Analoë resultate vir geëtiketteerde bome met twee gemerkte nodusse (wat verwant is aan funksionele digrafieke), is ook gevind. Ons gaan verder voort deur ook bereikbare nodusse, bronne en putte in hierdie bome at te tel. Onder andere verkry ons ’n formule vir die aantal geëtiketteerde bome met n nodusse waarin presies k nodusse vanaf ’n gegewe nodus v bereikbaar is asook die gemiddelde aantal nodusse wat bereikbaar is vanaf ’n gegewe nodus. Ons enumereer in hierdie tesis verder sekere families van versamelingsverdelings en soortgelyke boom-vormige strukture. Ons gee ’n bewys vir ’n formule wat die aantal van samehangende siklus-vrye families van k versamelingsverdelings op {1, . . . , n} wat ’n sekere koherensie-vereiste bevredig, en ons beskryf ’n bijeksie tussen hierdie familie en die versameling van geëtiketteerde vrye k-êre kaktusse met ’n gegewe nodus-graad-verdeling. Ons toon ook dat hierdie formule ook gekleurde Husimi-grafieke tel waar blokke van dieselfde kleur nie insident met mekaar mag wees nie. Ons tel verder ook gekleurde georiënteerde kaktusse en gekleurde kaktusse. Nie-kruisende bome en soortgelyke boom-vormige strukture word in hierdie tesis ook beskou. On bepaal spesifiek formules vir lokaal georiënteerde nie-kruisende bome wat ’n gegewe aantal bronne en putte het asook nie-kruisende bome met gegewe ingangs- en uitgangsgraadrye. Ons gaan voort deur die gemiddelde aantal bereikbare nodusse in hierdie bome te bepaal. Ons veralgemeen dan die konsep van nie-kruisende bome en vind formules vir die aantal nie-kruisende Husimi-grafieke, kaktusse en georiënteerde kaktusse. Laastens vind ons ’n formule vir die aantaal tweegekleurde nie-kruisende Husimi-grafieke en die aantal nie-kruisende samehangende siklus-vrye pare van versamelingsverdelings. | af_ZA |
| dc.format.extent | xII, 109 pages : illustrations | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/10019.1/96860 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | en_ZA |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Labelled trees (Mathematics) | en_ZA |
| dc.subject | Enumerative combinatorics (Mathematics) | en_ZA |
| dc.subject | Poly trees (Mathematics) | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.subject | Trees (Graph theory) | en_ZA |
| dc.title | Combinatorics of oriented trees and tree-like structures | en_ZA |
| dc.type | Thesis | en_ZA |