Dissertations / Theses on the topic 'Lattice path'

In this paper we will show how recent advances in the combinatorics of lattice paths can be applied to solve interesting and nontrivial problems in the theory of queues. The problems we discuss range from classical ones like M^a/M^b/1 systems to open tandem systems with and without global blocking and to queueing models that are related to random walks in a quarter plane like the Flatto-Hahn model or systems with preemptive priorities. (author´s abstract)
Series: Research Report Series / Department of Statistics and Mathematics

This paper deals with the joint and conditional distributions concerning the maximum of random walk paths and the number of times this maximum is achieved. This joint distribution was studied first by Dwass [1967]. Based on his result, the correlation and some conditional moments are derived. The main contributions are however asymptotic expansions concerning the conditional distribution and conditional moments. (author's abstract)
Series: Forschungsberichte / Institut für Statistik

La combinatoire analytique étudie le comportement asymptotique des suites à travers les propriétés analytiques de leurs fonctions génératrices. Ce domaine a conduit au développement d’outils profonds et puissants avec de nombreuses applications. Au delà de la théorie univariée désormais classique, des travaux récents en combinatoire analytique en plusieurs variables (ACSV) ont montré comment calculer le comportement asymptotique d’une grande classe de fonctions différentiellement finies:les diagonales de fractions rationnelles. Cette thèse examine les méthodes de l’ACSV du point de vue du calcul formel, développe des algorithmes rigoureux et donne les premiers résultats de complexité dans ce domaine sous des hypothèses très faibles. En outre, cette thèse donne plusieurs nouvelles applications de l’ACSV à l’énumération des marches sur des réseaux restreintes à certaines régions: elle apporte la preuve de plusieurs conjectures ouvertes sur les comportements asymptotiques de telles marches,et une étude détaillée de modèles de marche sur des réseaux avec des étapes pondérées
The field of analytic combinatorics, which studies the asymptotic behaviour ofsequences through analytic properties of their generating functions, has led to thedevelopment of deep and powerful tools with applications across mathematics and thenatural sciences. In addition to the now classical univariate theory, recent work in thestudy of analytic combinatorics in several variables (ACSV) has shown how to deriveasymptotics for the coefficients of certain D-finite functions represented by diagonals ofmultivariate rational functions. This thesis examines the methods of ACSV from acomputer algebra viewpoint, developing rigorous algorithms and giving the firstcomplexity results in this area under conditions which are broadly satisfied.Furthermore, this thesis gives several new applications of ACSV to the enumeration oflattice walks restricted to certain regions. In addition to proving several openconjectures on the asymptotics of such walks, a detailed study of lattice walk modelswith weighted steps is undertaken

The super Catalan numbers T(m,n) = (2m)!(2n)!=2m!n!(m+n)! are integers which generalize the Catalan numbers. Since 1874, when Eugene Catalan discovered these numbers, many mathematicians have tried to find their combinatorial interpretation. This dissertation is dedicated to this open problem. In Chapter 1 we review known results on T (m,n) and their q-analog polynomials. In Chapter 2 we give a weighted interpretation for T(m,n) in terms of 2-Motzkin paths of length m+n2 and a reformulation of this interpretation in terms of Dyck paths. We then convert our weighted interpretation into a conventional combinatorial interpretation for m = 1,2. At the beginning of Chapter 2, we prove our weighted interpretation for T(m,n) by induction. In the final section of Chapter 2 we present a constructive combinatorial proof of this result based on rooted plane trees. In Chapter 3 we introduce two q-analog super Catalan numbers. We also define the q-Ballot number and provide its combinatorial interpretation. Using our q-Ballot number, we give an identity for one of the q-analog super Catalan numbers and use it to interpret a q-analog super Catalan number in the case m= 2. In Chapter 4 we review problems left open and discuss their difficulties. This includes the unimodality of some of the q-analog polynomials and the conventional combinatorial interpretation of the super Catalan numbers and their q-analogs for higher values of m.

We consider the problem of testing whether r (>=2) samples are drawn from the same continuous distribution F(x). The test statistic we will study in some detail is defined as the maximum of the circular differences of the empirical distribution functions, a generalization of the classical 2-sample Kolmogorov-Smirnov test to r (>=2) independent samples. For the case of equal sample sizes we derive the exact null distribution by counting lattice paths confined to stay in the scaled alcove $\mathcal{A}_r$ of the affine Weyl group $A_{r-1}$. This is done using a generalization of the classical reflection principle. By a standard diffusion scaling we derive also the asymptotic distribution of the test statistic in terms of a multivariate Dirichlet series. When the sample sizes are not equal the reflection principle no longer works, but we are able to establish a weak convergence result even in this case showing that by a proper rescaling a test statistic based on a linear transformation of the circular differences of the empirical distribution functions has the same asymptotic distribution as the test statistic in the case of equal sample sizes.
Series: Research Report Series / Department of Statistics and Mathematics

In this thesis we examine methodologies for determining free energy differences (FEDs) of phases via Monte Carlo simulation. We identify and address three generic issues that arise in FED calculations; the choice of representation, the choice of estimator, and the choice of sampling strategy. In addition we discuss how the classical framework may be extended to take into account quantum effects. Key words: Phase Mapping, Phase Switch, Lattice Switch, Simulated Tempering, Multi-stage, Weighted Histogram Analysis Method, Fast Growth, Jarzynski method, Umbrella, Multicanonical, Path Integral Monte Carlo, Path Sampling, Multihamiltonian, fluctuation theorem.

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

The subject of this thesis is the study of the creation of fault lines in a random lattice, provoked by the successive failure of optimal paths. Using the recently developed Optimal Path Cracked model, we investigate how central characteristics of the successive optimal paths evolve as the lattice breaks down, and how this progression of characteristics depends on the magnitude of disorder imparted on the lattice. We then see how the OPC model, while originally proposed in the context of the shortest path problem, can be generalized to alternate optimal path problems, namely the minimax problem and the widest path problem. It is shown that for a given lattice, the minimax OPC is equal to the the backbone of the shortest OPC. The widest path OPC, although constituting a distinct object on any lattice, is shown to scale with lattice size in the same manner as the minimax OPC and the backbone of the shortest path OPC; with the fundamental process behind it being closely related to the minimax OPC process. Lastly, we explain the connection between the OPC process and a variety of other phenomena which have previously been shown to exhibit similar scaling behavior. We show how the OPC process for the widest path problem can be reduced to the shortest path problem on the dual lattice using the limit of very high disorder, the so-called ultrametric limit, and how an algorithm based on invasion percolation can be used as a quicker method of finding an OPC.

Il existe plusieurs filtrations intéressantes définies sur la sous-algèbre de Cartan d'une algèbre de Lie simple complexe issues de contextes très variés : l'une est la filtration principale qui provient du dual de Langlands, une autre provient de l'algèbre de Clifford associée à une forme bilinéaire invariante non-dégénérée, une autre encore provient de l'algèbre symétrique et la projection de Chevalley, deux autres enfin proviennent de l'algèbre enveloppante et des projections de Harish-Chandra. Il est connu que toutes ces filtrations coïncident. Ceci résulte des travaux de Rohr, Joseph et Alekseev-Moreau. La relation remarquable entre les filtrations principale et de Clifford fut essentiellement conjecturée par Kostant. L'objectif de ce mémoire de thèse est de proposer une nouvelle démonstration de l'égalité entre les filtrations symétrique et enveloppante pour une algèbre de Lie simple de type A ou C. Conjointement au résultat et Rohr et le théorème d'Alekseev-Moreau, ceci fournit une nouvelle démonstration de la conjecture de Kostant, c'est-à-dire une nouvelle démonstration du théorème de Joseph. Notre démonstration est très différentes de la sienne. Le point clé est d'utiliser une description explicite des invariants via la représentation standard, ce qui est possible en types A et C. Nous décrivons alors les images de leurs différentielles en termes d'objects combinatoires, appelés des chemins pondérés, dans le graphe cristallin de la représentation standard. Les démonstrations pour les types A et C sont assez similaires, mais ne nouveaux phénomènes apparaissent en type C, ce qui rend la démonstration nettement plus délicate dans ce cas
There are several interesting filtrations on the Cartan subalgebra of a complex simple Lie algebra coming from very different contexts: one is the principal filtration coming from the Langlands dual, one is coming from the Clifford algebra associated with a non-degenerate invariant bilinear form, one is coming from the symmetric algebra and the Chevalley projection, and two other ones are coming from the enveloping algebra and Harish-Chandra projections. It is known that all these filtrations coincide. This results from a combination of works of several authors (Rohr, Joseph, Alekseev-Moreau). The remarkable connection between the principal filtration and the Clifford filtration was essentially conjectured by Kostant. The purpose of this thesis is to establish a new correspondence between the enveloping filtration and the symmetric filtration for a simple Lie algebra of type A or C. Together with Rohr's result and Alekseev-Moreau theorem, this provides another proof of Kostant's conjecture for these types, that is, a new proof of Joseph's theorem. Our proof is very different from his approach. The starting point is to use an explicit description of invariants via the standard representation which is possible in types A and C. Then we describe the images of their differentials by the generalised Chevalley and Harish-Chandra projections in term of combinatorial objects, called weighted paths, in the crystal graph of the standard representation. The proofs for types A and C are quite similar, but there are new phenomenons in type C which makes the proof much more tricky in this case

This thesis contains four papers, where the first two are in the area of geometry of numbers, the third is about class group statistics and the fourth is about free path lengths. A general theme throughout the thesis is lattice points and convex bodies. In Paper A we give an asymptotic expression for the number of integer matrices with primitive row vectors and a given nonzero determinant, such that the Euclidean matrix norm is less than a given large number. We also investigate the density of matrices with primitive rows in the space of matrices with a given determinant, and determine its asymptotics for large determinants. In Paper B we prove a sharp bound for the remainder term of the number of lattice points inside a ball, when averaging over a compact set of (not necessarily unimodular) lattices, in dimensions two and three. We also prove that such a bound cannot hold if one averages over the space of all lattices. In Paper C, we give a conjectural asymptotic formula for the number of imaginary quadratic fields with class number h, for any odd h, and a conjectural asymptotic formula for the number of imaginary quadratic fields with class group isomorphic to G, for any finite abelian p-group G where p is an odd prime. In support of our conjectures we have computed these quantities, assuming the generalized Riemann hypothesis and with the aid of a supercomputer, for all odd h up to a million and all abelian p-groups of order up to a million, thus producing a large list of “missing class groups.” The numerical evidence matches quite well with our conjectures. In Paper D, we consider the distribution of free path lengths, or the distance between consecutive bounces of random particles in a rectangular box. If each particle travels a distance R, then, as R → ∞ the free path lengths coincides with the distribution of the length of the intersection of a random line with the box (for a natural ensemble of random lines) and we determine the mean value of the path lengths. Moreover, we give an explicit formula for the probability density function in dimension two and three. In dimension two we also consider a closely related model where each particle is allowed to bounce N times, as N → ∞, and give an explicit formula for its probability density function.

QC 20151204

This study seeks to design algorithms that may be used to determine if a given lattice is a good approximation to a given rigid protein structure. Ideal lattice models discovered using our techniques may then be used in algorithms for protein folding and inverse protein folding. In this study we develop methods based on dynamic programming and branch and bound in an effort to identify “ideal” lattice models. To further our understanding of the concepts behind the methods we have utilized a simple cubic lattice for our analysis. The algorithms may be adapted to work on any lattice. We describe two algorithms. One for aligning the protein backbone to the lattice as a walk. This algorithm runs in polynomial time. The second algorithm for aligning a protein backbone as a path to the lattice. Both the algorithms seek to minimize the CRMS deviation of the alignment. The second problem was recently shown to be NP-Complete, hence it is highly unlikely that an efficient algorithm exists. The first algorithm gives a lower bound on the optimal solution to the second problem, and can be used in a branch and bound procedure. Further, we perform an empirical evaluation of our algorithm on proteins from the Protein Data Bank (PDB).
ix, 47 leaves ; 29 cm.

Cette thèse développe des algorithmes pour les problèmes de plus court chemin sous cont-rain-tes de ressources, et les applique à l'optimisation des rotations des avions et des équipages d'une compagnie aérienne dans le cadre d'approches par génération de colonnes.Les problèmes de plus court chemin sous contraintes de ressources sont généralement résolus grâce à une énumération intelligente de tous les chemins non dominés. Les approches récentes utilisent des bornes sur les ressources des chemins pour éliminer des solutions partielles. L'efficacité de la méthode est conditionnée par la qualité des bornes utilisées. Notre principale contribution au domaine est l'introduction d'une procédure générique pour calculer des bornes qui s'applique à la plupart des problèmes de chemins sous contraintes, et en particulier les problèmes stochastiques. A cette fin, nous introduisons une généralisation du problème de plus court chemin sous contraintes dans laquelle les ressources des chemins appartiennent à un monoïde ordonné comme un treillis. La ressource d'un chemin est la somme des ressources de ses arcs, le terme somme désignant l'opérateur du monoïde. Le problème consiste à trouver parmi les chemins qui satisfont une contrainte donnée celui dont la ressource minimise une fonction de coût croissante de la ressource des chemins. Nous généralisons les algorithmes d'énumération à ce nouveau problème. La théorie des treillis nous permet de construire une procédure polynomiale pour trouver des bornes de qualité. L'efficacité pratique de la méthode est évaluée au travers d'une étude numérique détaillée sur des problèmes de chemins déterministes et stochastiques. Les procédures de calcul des bornes peuvent être interprétées comme des généralisations aux monoïdes ordonnés comme des treillis d'algorithmes de la littérature définis pour résoudre un problème de chemin pour lequel les ressources des chemins prennent leur valeur dans un semi-anneau.Nos algorithmes de chemins ont été appliqués avec succès au problème de crew pairing. Étant donné un ensemble de vols opérés par une compagnie aérienne, les problèmes d'aircraft routing et de crew pairing construisent respectivement les séquences de vols opérées par les avions et par les équipages de manière à couvrir tous les vols à moindre coût. Comme certaines séquences de vols ne peuvent être réalisées par un équipage que s'il reste dans le même avion, les deux problèmes sont liés. La pratique actuelle dans l'industrie aéronautique est de résoudre tout d'abord le problème d'aircraft routing, puis le problème de crew pairing, ce qui aboutit à une solution non-optimale. Des méthodes de résolution pour le problème intégré ont été développées ces dix dernières années. Nous proposons une méthode de résolution pour le problème intégré reposant sur deux nouveaux ingrédients : un programme linéaire en nombre entier compact pour le problème d'aircraft routing, ainsi que de nouveaux pour le problème esclave de l'approche usuelle par génération de colonnes du problème de crew pairing. Ces algorithmes pour le problème esclave sont une application de nos algorithmes pour le problème de plus court chemin sous contraintes. Nous généralisons ensuite cette approche de manière à prendre en compte des contraintes de probabilités sur la propagation du retard. Ces algorithmes permettent de résoudre quasiment à l'optimum les instances industrielles d'Air France
This thesis develops algorithms for resource constrained shortest path problems, and uses them to solve the pricing subproblems of column generation approaches to some airline operations problems.Resource constrained shortest path problems are usually solved using a smart enumeration of the non-dominated paths. Recent improvements of these enumeration algorithms rely on the use of bounds on path resources to discard partial solutions. The quality of the bounds determines the performance of the algorithm. Our main contribution to the topic is to introduce a standard procedure to generate bounds on paths resources in a general setting which covers most resource constrained shortest path problems, among which stochastic versions. In that purpose, we introduce a generalization of the resource constrained shortest path problem where the resources are taken in a lattice ordered monoid. The resource of a path is the monoid sum of the resources of its arcs. The problem consists in finding a path whose resource minimizes a non-decreasing cost function of the path resource among the paths that satisfy a given constraint. Enumeration algorithms are generalized to this framework. We use lattice theory to provide polynomial procedures to find good quality bounds. The efficiency of the approach is proved through an extensive numerical study on deterministic and stochastic path problems. Interestingly, the bounding procedures can be seen as generalizations to lattice ordered monoids of some algebraic path problem algorithms which initially work with resources in a semiring.Given a set of flight legs operated by an airline, the aircraft routing and the crew pairing problem build respectively the sequences of flight legs operated by airplanes and crews at minimum cost. As some sequences of flight legs can be operated by crews only if they stay in the same aircraft, the two problems are linked. The current practice in the industry is to solve first the aircraft routing, and then the crew pairing problem, leading to a non-optimal solution. During the last decade, solution schemes for the integrated problem have been developed. We propose a solution scheme for the integrated problem based on two new ingredients: a compact integer program approach to the aircraft routing problem, and a new algorithm for the pricing subproblem of the usual column generation approach to the crew pairing problem, which is based on our resource constrained shortest path framework. We then generalize the algorithm to take into account delay propagation through probabilistic constraints. The algorithms enable to solve to near optimality Air France industrial instances

In this paper we present a simple combinatorial approach for the derivation of zero avoiding transition probabilities in a Markovian r- node series Jackson network. The method we propose offers two advantages: first, it is conceptually simple because it is based on transition counts between the nodes and does not require a tensor representation of the network. Second, the method provides us with a very efficient technique for numerical computation of zero avoiding transition probabilities.
Series: Forschungsberichte / Institut für Statistik

The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science, biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.

An urn contains two types of balls: p "+t" balls and m "-s" balls, where t and s are positive real numbers. The balls are drawn from the urn uniformly at random without replacement until the urn is empty. Before each ball is drawn, the player decides whether to accept the ball or not. If the player opts to accept the ball, then the payoff is the weight of the ball drawn, gaining t dollars if a "+t" ball is drawn, or losing s dollars if a "-s" ball is drawn. We wish to maximize the expected gain for the player. We find that the optimal acceptance policies are similar to that of the original acceptance urn of Chen et al. with s=t=1. We show that the expected gain function also shares similar properties to those shown in that work, and note the important properties that have geometric interpretations. We then calculate the expected gain for the urns with t/s rational, using various methods, including rotation and reflection. For the case when t/s is irrational, we use rational approximation to calculate the expected gain. We then give the asymptotic value of the expected gain under various conditions. The problem of minimal gain is then considered, which is a version of the ballot problem. We then consider a Bayesian approach for the general urn, for which the number of balls n is known while the number of "+t" balls, p, is unknown. We find formulas for the expected gain for the random acceptance urn when the urns with n balls are distributed uniformly, and find the asymptotic value of the expected gain for any s and t. Finally, we discuss the probability of ruin when an optimal strategy is used for the (m,p;s,t) urn, solving the problem with s=t=1. We also show that in general, when the initial capital is large, ruin is unlikely. We then examine the same problem with the random version of the urn, solving the problem with s=t=1 and an initial prior distribution of the urns containing n balls that is uniform.

The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science, biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.

Bobbin lace is a 500-year-old art form in which threads are braided together in an alternating manner to produce a lace fabric. A key component in its construction is a small pattern, called a bobbin lace ground, that can be repeated periodically to fill a region of any size. In this thesis we present a mathematical model for bobbin lace grounds representing the structure as the pair (Δ(G), ζ (v)) where Δ(G) is a topological embedding of a 2-regular digraph, G, on a torus and ζ(v) is a mapping from the vertices of G to a set of braid words. We explore in depth the properties that Δ(G) must possess in order to produce workable lace patterns. Having developed a solid, logical foundation for bobbin lace grounds, we enumerate and exhaustively generate patterns that conform to that model. We start by specifying an equivalence relation and define what makes a pattern prime so that we can identify unique representatives. We then prove that there are an infinite number of prime workable patterns. One of the key properties identified in the model is that it must be possible to partition Δ(G) into a set of osculating circuits such that each circuit has a wrapping index of (1,0); that is, the circuit wraps once around the meridian of the torus and does not wrap around the longitude. We use this property to exhaustively generate workable patterns for increasing numbers of vertices in G by gluing together lattice paths in an osculating manner. Using a backtracking algorithm to process the lattice paths, we identify over 5 million distinct prime patterns. This is well in excess of the roughly 1,000 found in lace ground catalogues. The lattice paths used in our approach are members of a family of partially directed lattice paths that have not been previously reported. We explore these paths in detail, develop a recurrence relation and generating function for their enumeration and present a bijection between these paths and a subset of Motzkin paths. Finally, to draw out of the extremely large number of patterns some of the more aesthetically interesting cases for lacemakers to work on, we look for examples that have a high degree of symmetry. We demonstrate, by computational generation, that there are lace ground representatives from each of the 17 planar periodic symmetry groups.
Graduate
0389
0984
0405
veronikairvine@gmail.com

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

碩士
國立中興大學
電機工程學系所
102
Enumerating the total number of constrained lattice paths is a well- established subject in combinatorics and constitutes a crucial research topic in academia. Although the architecture of lattice paths is easily understood, most proposed theorems have not yet been confirmed. The number of lattice paths is identified to enable all of the obtained series to be used to represent binomial coefficients. This study entailed employing combination and algebraic methods to derive a formula from the description of occurring recursions. Section 1 introduces the research motivation as well as the basic structure of lattice paths and presents a literature review. In relevant literature, the issue of Catalan and Motzkin numbers has been raised. Various studies have proposed increasing the lattice paths in three types of fixed direction and correcting a simple formula. Section 2 describes the mathematical problems that often occur in combination: the occurrence of Catalan numbers and the difficulty in proving them based on a combination of mathematical analyses. In addition, various applications for Catalan numbers are proposed; for example, the can be employed to solve the Ballot problem. Section 3 presents an approach to increasing the fixed direction of lattice paths; in addition to the three types of fixed direction, the problem was divided into four categories, and the use of “bijection” the relationship to the latter two issues in discussions and proof. Section 4 details an extension of the problem of increasing the fixed direction of lattice paths, increasing the restriction of the ban on moving to where y l l 0, 1, 2 or less, this study analyzed l  negative integers. Based on the analysis, this paper proposes a formula to solve the problem and prove the formula. Finally, Section 5 provides the conclusion and recommendations for future research.

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.

Removing the minimum number of vertices or points from a square lattice such that no square path exists is known as the square path problem. Finding this number as the size of the lattice increases is not so trivial. Results provided by Erdos-Posa and Bienstock-Dean provides an upper bound for eliminating all cycles from a planar graph but sheds little light on the case of the square lattice. This paper provides several values for the minimum number of vertices needed to be removed such that no square path exists.

碩士
中原大學
資訊工程研究所
92
For students of computer science, programming is an indispensable knowledge and technical ability. However, during the course of learning programming, the learners are often faced with hesitations, setbacks, and frustrations. Having written a piece of code after spending a lot of time and effort, a learner may only find that there are many mistakes (bugs) in the code. Though there may be a strong desire on the part of the learner to try to correct the code, he/she may only “wonder around”, not knowing where to start and what to do. The result is often that the learner acts like a “headless fly”, trying everything everywhere. Perhaps, with good lucks, the learner can finally find a way of correctly revising the code, but only after trying many “wrong ways”. An instructor, on the other hand, often has to face many different pieces of “wrong” code, each with some kind of strange bugs in it. Though the instructor knows what are wrong with any particular piece of code, there is often a great difficulty in trying to “guide” the student (the author of the code) in correctly revising the code and learning the “correct” way of programming. This problem is further complicated by the fact that the instructor often cannot figure out why the student wrote his/her particular piece of code this way, not to mention how the instructor may be able to “correct” the student’s way of thinking. This is a further hindrance in providing appropriate assistance to the learner so that the learner can “think correctly” and write “correct code”. Because of this, we constructed a computer-assisted learning system (a CAL system, for short), and we call this system CSD (for Code Schema Development). CSD may be said to be constructivism-based. The main idea is to control the problem-solving environment and provide scaffolding for code constructions in such a way so that the leaner can (1) develop the intended code schemas and (2) correctly apply the developed code schemas in solving programming problems. A secondary goal of CSD is to raise the learner’s confidence and interests in programming. CSD tracks the learner’s actions and answers (including the intermediate answers) and records everything in a database. From the learners’ records, we seek to analyze the various “tracks of thinking”, with a goal of trying to identify the various “paths” of code evolution, showing how the learners progress from the initial erroneous code to the final correct code. In related previous research works, the main focus was on the identification of error patterns in the learners’ code, and researchers were not concerned with how the learners made revisions in order to obtain the “right” code. In this research, we propose a way of describing how a learner “evolves” from one error pattern to another in producing his/her final answer (the correct code). In doing so, we also try to analyze what the learner may be thinking when he/she wrote the (erroneous) code.