A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Master of Science. Johannesburg, 2014. / This dissertation consists of ve chapters which deal with lattice paths such as Dyck paths, skew Dyck paths and generalized Motzkin paths. They never go below the horizontal axis. We derive the generating functions to enumerate lattice paths according to di erent parameters. These parameters include strings of length 2, 3, 4 and r for all r 2 f2; 3; 4; g, area and semi-base, area and semi-length, and semi-base and semi-perimeter. The coe cients in the series expansion of these generating functions give us the number of combinatorial objects we are interested to count. In particular 1. Chapter 1 is an introduction, here we derive some tools that we are going to use in the subsequent Chapters. We rst state the Lagrange inversion formula which is a remarkable tool widely use to extract coe cients in generating functions, then we derive some generating functions for Dyck paths, skew Dyck paths and Motzkin paths. 2. In Chapter 2 we use generating functions to count the number of occurrences of strings in a Dyck path. We rst derive generating functions for strings of length 2, 3, 4 and r for all r 2 f2; 3; 4; g, we then extract the coe cients in the generating functions to get the number of occurrences of strings in the Dyck paths of semi-length n. 3. In Chapter 3, Sections 3.1 and 3.2 we derive generating functions for the relationship between strings of lengths 2 and 3 and the relationship between strings of lengths 3 and 4 respectively. In Section 3.3 we derive generating functions for the low occurrences of the strings of lengths 2, 3 and 4 and lastly Section 3.4 deals with derivations of generating functions for the high occurrences of some strings . 4. Chapter 4, Subsection 4.1.1 deals with the derivation of the generating functions for skew paths according to semi-base and area, we then derive the generating functions according to area. In Subsection 4.1.2, we consider the same as in Section 4.1.1, but here instead of semi-base we use semi-length. The last section 4.2, we use skew paths to enumerate the number of super-diagonal bar graphs according to perimeter. 5. Chapter 5 deals with the derivation of recurrences for the moments of generalized Motzkin paths, in particular we consider those Motzkin paths that never touch the x-axis except at (0,0) and at the end of the path.

A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg in fulfillment of the requirements for the degree of Master of Science.Johannesburg, 30 May 2017. / We study a type of lattice path called a skew Dyck path which is a generalization of a Dyck path. Therefore we first introduce Dyck paths and study their enumeration according to various parameters such as number of peaks, valleys, doublerises and return steps. We study characteristics such as bijections with other combinatorial objects, involutions and statistics on skew Dyck paths. We then show enumerations of skew Dyck paths in relation to area, semi-base and semi-length. We finally introduce superdiagonal bargraphs which are associated with skew Dyck paths and enumerate them in relation to perimeter and area / GR2018

A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in ful lment of the requirements for the degree of Master of Science. Johannesburg, 2013. / Our main focus in this research is to compute formulae for the generating function of lattice paths. We will only concentrate on two types of lattice paths, Dyck paths and Motzkin paths. We investigate di erent ways to enumerate these paths according to various parameters. We start o by studying the relationship between the Catalan numbers Cn, Fine numbers Fn and the Narayana numbers vn;k together with their corresponding generating functions. It is here where we see how the the Lagrange Inversion Formula is applied to complex generating functions to simplify computations. We then study the enumeration of Dyck paths according to the semilength and parameters such as, number of peaks, height of rst peak, number of return steps, e.t.c. We also show how some of these Dyck paths are related. We then make use of Krattenhaler's bijection between 123-avoiding permutations of length n, denoted by Sn(123), and Dyck paths of semilength n. Using this bijective relationship over Sn(123) with k descents and Dyck paths of semilength n with sum of valleys and triple falls equal to k, we get recurrence relationships between ordinary Dyck paths of semilength n and primitive Dyck paths of the same length. From these relationships, we get the generating function for Dyck paths according to semilength, number of valleys and number of triple falls. We nd di erent forms of the generating function for Motzkin paths according to length and number of plateaus with one horizontal step, then extend the discussion to the case where we have more than one horizontal step. We also study Motzkin paths where the horizontal steps have di erent colours, called the k-coloured Motzkin paths and then the k-coloured Motzkin paths which don't have any of their horizontal steps lying on the x-axis, called the k-coloured c-Motzkin paths. We nd that these two types of paths have a special relationship which can be seen from their generating functions. We use this relationship to simplify our enumeration problems.

No description available.

Lau, Siu Cheong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 51-52). / Abstracts in English and Chinese. / Chapter 1 --- In search of minimal cycles --- p.9 / Chapter 1.1 --- What do we mean by cycles? --- p.9 / Chapter 1.2 --- Integral currents --- p.10 / Chapter 1.3 --- Calibration theory --- p.13 / Chapter 2 --- Motivation from the Hodge Conjecture --- p.17 / Chapter 2.1 --- Hodge theory on Riemannian manifolds --- p.17 / Chapter 2.2 --- Hodge decomposition in Kahler manifolds --- p.19 / Chapter 2.3 --- The Hodge conjecture --- p.22 / Chapter 3 --- Variation of cycles in symmetric orbit --- p.26 / Chapter 3.1 --- Variational formulae --- p.26 / Chapter 3.2 --- Stability of cycles in Sm and CPn --- p.29 / Chapter 3.3 --- Symmetric orbit in Euclidean space --- p.31 / Chapter 3.4 --- Projective spaces in simple Jordan algebra --- p.39 / Chapter 3.4.1 --- Introduction to simple Jordan algebra --- p.39 / Chapter 3.4.2 --- Projective spaces as symmetric orbits --- p.41 / Chapter 3.4.3 --- Computation of second fundamental form --- p.43 / Chapter 3.4.4 --- The main theorem --- p.45 / Chapter 3.5 --- Future directions --- p.49 / Bibliography --- p.51

No description available.

Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes. / We consider a long-studied generalization of the shortest path problem, in which not one but several short paths must be produced. The k-shortest (simple) paths problem is to list the k paths connecting a given source-destination pair in the digraph with minimum total length. This dissertation deals with k-shortest simple paths algorithms designed for nonnegative costs, undirected graphs and some implementations of them.

Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes. / We consider a long-studied generalization of the shortest path problem, in which not one but several short paths must be produced. The k-shortest (simple) paths problem is to list the k paths connecting a given source-destination pair in the digraph with minimum total length. This dissertation deals with k-shortest simple paths algorithms designed for nonnegative costs, undirected graphs and some implementations of them.

Dans les années 90 Garsia et Haiman ont introduit le $mathfrak S_n$-module des emph{harmoniques diagonales}, c'est à dire les co-invariants de l'action diagonale du groupe symétrique $mathfrak S_n$ sur les polynômes à deux ensembles de $n$ variables. Ils ont proposé la conjecture selon laquelle le caractère de Frobenius bi-gradué de leur module est $abla e_n$, où $abla$ est un opérateur sur l'anneau des fonction symétriques. En 2002, Haiman prouva cette conjecture. Quelques années plus tard, Haglund, Haiman, Loehr, Remmel et Ulyanov proposèrent une formule combinatoire pour la fonction symétrique $abla e_n$, qu'ils appelèrent la emph{conjecture shuffle}. Les objets combinatoires qui y figurent sont les chemins de Dyck étiquetés. Un raffinement emph{compositionnel} de cette formule fut ensuite proposé par Haglund, Morse et Zabrocki. C'était ce raffinement que Carlsson et Mellit réussirent enfin à montrer en 2018, établissant ainsi le emph{théorème shuffle}. La emph{conjecture Delta} est une paire de formules combinatoires pour la fonction symétrique $Delta'_{e_{n-k-1}}e_n$ en termes des chemins de Dyck étiquetés et décorés, qui généralise le théorème shuffle. Elle fut proposée par Hagund, Remmel et Wilson en 2015 est reste aujourd'hui un problème ouvert. Dans la même publication les auteurs proposèrent une formule pour $Delta_{h_m}Delta'_{e_{n-k-1}}e_n$ en termes de chemins de Dyck partiellement étiquetés et décorés, appelé emph{conjecture Delta généralisée}. Nous proposons un raffinement compositionnel de la conjecture Delta en utilisant des nouveaux opérateurs de fonctions symétriques: les opérateurs Theta. Nous généralisons les arguments combinatoires que Carlsson et Mellit utilisèrent pour la preuve du théorème shuffle au contexte de la conjecture Delta. Nous prouvons également la formule pour $Delta_{h_m} abla e_n$ en termes de chemins de Dyck partiellement étiqueté, c'est à dire le cas $k=0$ de la conjecture Delta généralisée. En 2006, Can et Loehr proposèrent la emph{conjecture carré}, exprimant la fonction symétrique $(-1)^{n-1}abla p_n$ en termes de chemins carrés étiquetés. Sergel montra que le théorème shuffle implique la conjecture carré. Nous généralisons le résultat de Sergel en montrant que une des formules de la conjecture Delta généralisée implique une formule combinatoire de la fonction $(-1)^{n-k}Delta_{h_m}Theta_kp_{n-k}$ e / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Path selection and generating tests for small delay faults is an important issue in the delay fault area. A novel technique for generating effective vectors for delay defects is the first issue that we have presented in the thesis. The test set achieves high path delay fault coverage to capture small-distributed delay defects and high transition fault coverage to capture gross delay defects. Furthermore, non-robust paths for ATPG are filtered (selected) carefully so that there is a minimum overlap with the already tested robust paths. A relationship between path delay fault model and transition fault model has been observed which helps us reduce the number of non-robust paths considered for test generation. To generate tests for robust and non-robust paths, a deterministic ATPG engine is developed. To deal with small delay faults, we have proposed a new transition fault model called As late As Possible Transition Fault (ALAPTF) Model. The model aims at detecting smaller delays, which will be missed by both the traditional transition fault model and the path delay model. The model makes sure that each transition is launched as late as possible at the fault site, accumulating the small delay defects along its way. Because some transition faults may require multiple paths to be launched, simple path-delay model will miss such faults. The algorithm proposed also detects robust and non-robust paths along with the transition faults and the execution time is linear to the circuit size. Results on ISCAS'85 and ISCAS'89 benchmark circuits shows that for all the cases, the new model is capable of detecting smaller gate delays and produces better results in case of process variations. Results also show that the filtered non-robust path set can be reduced to 40% smaller than the conventional path set without losing delay defect coverage. / Master of Science