Thesis (PhD)--Stellenbosch University, 2015. / 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. / 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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/96860 |
| Date | 03 1900 |
| Creators | Okoth, Isaac Owino |
| Contributors | Wagner, Stephan, Stellenbosch University. Faculty of Science. Department of Mathematical Sciences. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | xII, 109 pages : illustrations |
| Rights | Stellenbosch University |
Page generated in 0.0031 seconds