Spelling suggestions: "subject:"lattice paths"" "subject:"iattice paths""
1 |
Combinatorics of lattice pathsNcambalala, Thokozani Paxwell 01 September 2014 (has links)
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.
|
2 |
Combinatorial properties of lattice pathsDube, Nolwazi Mitchel January 2017 (has links)
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
|
3 |
Generating functions and the enumeration of lattice pathsMutengwe, Phumudzo Hector 07 August 2013 (has links)
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.
|
4 |
Counting Plane Tropical Curves via Lattice Paths in PolygonsZhang, Yingyu 12 1900 (has links)
A projective plane tropical curve is a proper immersion of a graph into the real Cartesian plane subject to some conditions such as that the images of all the edges must be lines with rational slopes. Two important combinatorial invariants of a projective plane tropical curve are its degree, d, and genus g. First, we explore Gathmann and Markwig's approach to the study of the moduli spaces of such curves and explain their proof that the number of projective plane tropical curves, counting multiplicity, passing through n = 3d + g -1 points does not depend on the choice of points, provided they are in tropical general position. This number of curves is called a Gromov-Written invariant. Second, we discuss the proof of a theorem of Mikhalkin that allows one to compute the Gromov-Written invariant by a purely combinatorial process of counting certain lattice paths.
|
5 |
On Zero avoiding Transition Probabilities of an r-node Tandem Queue - a Combinatorial ApproachBöhm, Walter, Jain, J. L., Mohanty, Sri Gopal January 1992 (has links) (PDF)
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
|
6 |
Multivariate finite operator calculus applied to counting ballot paths containing patterns [electronic resource]Unknown Date (has links)
Counting lattice paths where the number of occurrences of a given pattern is monitored requires a careful analysis of the pattern. Not the length, but the characteristics of the pattern are responsible for the difficulties in finding explicit solutions. Certain features, like overlap and difference in number of ! and " steps determine the recursion formula. In the case of ballot paths, that is paths the stay weakly above the line y = x, the solutions to the recursions are typically polynomial sequences. The objects of Finite Operator Calculus are polynomial sequences, thus the theory can be used to solve the recursions. The theory of Finite Operator Calculus is strengthened and extended to the multivariate setting in order to obtain solutions, and to prepare for future applications. / by Shaun Sullivan. / Thesis (Ph.D.)--Florida Atlantic University, 2011. / Includes bibliography. / Electronic reproduction. Boca Raton, Fla., 2011. Mode of access: World Wide Web.
|
7 |
Algorithms & experiments for the protein chain lattice fitting problemThomas, Dallas, University of Lethbridge. Faculty of Arts and Science January 2006 (has links)
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.
|
8 |
Combinatorial Interpretations Of Generalizations Of Catalan Numbers And Ballot NumbersAllen, Emily 01 May 2014 (has links)
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.
|
9 |
Lattice path counting and the theory of queuesBöhm, Walter January 2008 (has links) (PDF)
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
|
10 |
A Generalized Acceptance Urn ModelWagner, Kevin P 05 April 2010 (has links)
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.
|
Page generated in 0.1549 seconds