1 
A survey of three combinatorial problemsTissink, Henrick January 2016 (has links)
A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of requirements for the degree of Master of Science. Johannesburg, 2015. / This dissertation is based on three di erent combinatorial papers:
1. The rst paper is by Silvia Heubach and Tou k Mansour: Enumeration of 3Letter Patterns
in Compositions. Combinatorial Number Theory in Celebration of the 70th Birthday of
Ronald Graham. In: De Gruyter Proceedings in Mathematics. 243264, (2007).
2. The second paper is by Daniel J. Velleman and Gregory S. Warrington: What to expect
in a game of memory. American Mathematical Monthly, 120:787805 (2013).
3. The third paper is by Mireille BousquetM elou and Richard Brak: Exactly Solved Models
of Polyominoes and Polygons. Polygons, Polyominoes and Polycubes. In: Lecture Notes in
Physics, 775:4378, (2009). / GR 2016

2 
Enumerative methods in combinatorial analysisAbramson, Morton. January 1966 (has links)
No description available.

3 
Combinatorial displaysHajdú, Péter, 1923 January 1974 (has links)
No description available.

4 
Moments over the solution space of the travelling salesman problemSutcliffe, Paul Unknown Date (has links)
In this thesis we consider the statistical properties of the symmetric travelling salesman problem (TSP). Previous work on the statistical properties of the problem has been largely limited to the Euclidean case with vertex coordinates as random variables with known distribution embedded in Rd, and to the case of independent identically distributed random edge costs. Furthermore, this previous work did not extend to computing the moments, beyond the mean. In the work presented here we consider the more general case of problem instances specified as a set of edge costs and with no (known) embedding or coordinate system available. For an instance of the problem on n vertices with fixed edge costs we give constructive proofs that the population variance of tour costs over the solution space can be computed in O(n2), the third central moment can be computed in O(n4) and the fourth central moment can be computed in O(n6). These results provide direct methods to compute the moments about the origin and factorial moments of these orders with the corresponding computational complexity. In addition the results provide tractable methods to compute, among other statistics, the standard deviation of tour costs, the skewness of the probability distributions of tour costs over the solution space and kurtosis of this distribution. In the case of the stochastic TSP with edge costs defined as independently distributed random variables with (not necessarily identical) known mean and variance we provide a O(n4) algorithm to compute the variance of tour costs. Given a subgraph S of a tour in an n city TSP, we provide an O(n2) algorithm to compute the expected tour costs over the solution space of those tours containing S. This is useful in analysing and constructing algorithms such as Gutin's greedy expectation heuristic. We demonstrate that the probability distribution of gains over the 2opt landscape of an n city TSP can be computed in O(n4 log(n)). This result provides a tractable algorithm to compute, among other statistics the moments of gains over the landscape. The result also provides the 2opt neutrality (the number of neighbouring solutions with identical cost) of a instance. The result has natural generalisation to the 3opt landscape (at higher computational complexity). We relate the variance of tour costs over the solution space to that of the gains over the 2opt landscape of a problem, providing an O(n2) method to compute the variance of gains over the landscape. We apply our method to compute the low order moments of the distribution of tour costs to several empirical studies of the solution space. Among other results we: con¯rm the known relationship between the standard deviation of tour costs and the optimal tour cost; we show a correlation between the skewness and the optimal tour cost; we demonstrate that the moments can be used to estimate the complete probability distribution of tour costs.

5 
Moments over the solution space of the travelling salesman problemSutcliffe, Paul Unknown Date (has links)
In this thesis we consider the statistical properties of the symmetric travelling salesman problem (TSP). Previous work on the statistical properties of the problem has been largely limited to the Euclidean case with vertex coordinates as random variables with known distribution embedded in Rd, and to the case of independent identically distributed random edge costs. Furthermore, this previous work did not extend to computing the moments, beyond the mean. In the work presented here we consider the more general case of problem instances specified as a set of edge costs and with no (known) embedding or coordinate system available. For an instance of the problem on n vertices with fixed edge costs we give constructive proofs that the population variance of tour costs over the solution space can be computed in O(n2), the third central moment can be computed in O(n4) and the fourth central moment can be computed in O(n6). These results provide direct methods to compute the moments about the origin and factorial moments of these orders with the corresponding computational complexity. In addition the results provide tractable methods to compute, among other statistics, the standard deviation of tour costs, the skewness of the probability distributions of tour costs over the solution space and kurtosis of this distribution. In the case of the stochastic TSP with edge costs defined as independently distributed random variables with (not necessarily identical) known mean and variance we provide a O(n4) algorithm to compute the variance of tour costs. Given a subgraph S of a tour in an n city TSP, we provide an O(n2) algorithm to compute the expected tour costs over the solution space of those tours containing S. This is useful in analysing and constructing algorithms such as Gutin's greedy expectation heuristic. We demonstrate that the probability distribution of gains over the 2opt landscape of an n city TSP can be computed in O(n4 log(n)). This result provides a tractable algorithm to compute, among other statistics the moments of gains over the landscape. The result also provides the 2opt neutrality (the number of neighbouring solutions with identical cost) of a instance. The result has natural generalisation to the 3opt landscape (at higher computational complexity). We relate the variance of tour costs over the solution space to that of the gains over the 2opt landscape of a problem, providing an O(n2) method to compute the variance of gains over the landscape. We apply our method to compute the low order moments of the distribution of tour costs to several empirical studies of the solution space. Among other results we: con¯rm the known relationship between the standard deviation of tour costs and the optimal tour cost; we show a correlation between the skewness and the optimal tour cost; we demonstrate that the moments can be used to estimate the complete probability distribution of tour costs.

6 
Connections between combinatorics of permutations and algorithms and geometry /Wills, Dean Connable. January 1900 (has links)
Thesis (Ph. D.)Oregon State University, 2010. / Printout. Includes bibliographical references (leaves 113114). Also available on the World Wide Web.

7 
Simplicity in relational structures and its application to permutation classes /Brignall, Robert. January 2007 (has links)
Thesis (Ph.D.)  University of St Andrews, November 2007.

8 
Two problems in extremal set theoryBrown Kramer, Joshua. January 1900 (has links)
Thesis (Ph.D.)University of NebraskaLincoln, 2007. / Title from title screen (site viewed July 9, 2007). PDF text: 126 p. : ill. UMI publication number: AAT 3252840. Includes bibliographical references. Also available in microfilm and microfiche formats.

9 
On the Hadamard theorem and maximal determinants in combinatorial investigationsUnknown Date (has links)
The Hadamard Theorem plays a brief but important role in the study of maximal determinants in chapter II. The proof which is presented follows closely the paper by Everett and Ryser, but an attempt has been made to clarify and expand their work wherever possible. / Typescript. / "June, 1960." / "Submitted to the Graduate Council of Florida State University in partial fulfillment of the requirements for the degree of Master of Science." / Advisor: Marion F. Tinsley, Professor Directing Paper. / Includes bibliographical references (leaf 23).

10 
Combinatorial displaysHajdu, Peter, 1946 January 1974 (has links)
No description available.

Page generated in 0.1058 seconds