Gao, S. (2017). Computational Solutions to Some Challenging Number Theory and Combinatorial Problems. Unc Charlotte Electronic Theses And Dissertations.
We use computational assist approach to tackle some challenging and interesting problems in number theory and combinatorics, such as Markoff-Hurwitz equations, integer matrix enumeration, integer sequences, and self-avoiding walks. We present the background, what people did in the past, what we have obtained. In the more than 100 years since Markoff-Hurwitz Equations, they play adecisive role, have turned up in an astounding variety of different settings,from number theory to combinatorics, from classical groups and geometry to theworld of graphs and words, from discrete mathematics to scientificcomputation. We will first introduce other people's work in this area. Then wepresent algorithms for searching and generating solutions to the equation$x_{1}^{2}+x_{2}^{2}+...+x_{n}^{2}=kx_{1}x_{2}...x_{n}$. Solutions arereported for n = 2, 3,\ldots, 9. Properties of solutions are discussed. We willprove that the solutions do not exist when n=4 and k=2 or 3; n=5 and k=2 or 3.Conjectures based on computational results are discussed.The enumeration of integer-matrices has been the subject of considerable studyand it is unlikely that a simple formula exists. The number in question can berelated in various ways to the representation theory of the symmetric group orof the complex general linear group, but this does not make their computationany easier. We will discuss the following five problems: (1)\ the number of $m\times n$matrices over $\{0,1\}$ with each row summing to $s$ and each column summingto $t$; (2) the number of $(0,1)$~- matrices with restriction; (3)the number of nonnegative integer matrices of size $m\times n$with each row sum equal to $s$ and each column sum equal to $t$; (4)\ thenumber of $(-1,0,1)$~- matrices of size $n\times n$; (5) the number of nonnegative matrices with restriction. We will present manyconjectures based on our computation.For self-avoiding walks, we will present: A self-avoiding walk (SAW) is a sequence ofmoves on a lattice not visiting the same point more than once. A SAW on thesquare lattice is prudent if it never takes a step towards a vertex it hasalready visited. Prudent walks differ from most sub-classes of SAWs that havebeen counted so far in that they can wind around their starting point. Someproblems and some sequences arising from prudent walks are also discussed.