Combinatorial methods for integer partitions

Date created: 
Integer partitions
Linear Diophantine equations
Combinatorial proofs
Generating functions
Recurrence relations
Reciprocity relations
Frobenius coin problem
Ramanujan's congruences
Berkovich and Uncu's conjectures
Jacobi symbol

Integer partitions, while simply defined, are associated with some of the most celebrated results in mathematics. Despite their simple definition, many results on integer partitions can be shockingly difficult to obtain. In this thesis, we use elementary and combinatorial methods to make progress on some fundamental problems related to linear Diophantine equations and integer partitions. We find an efficient method for finding the number of nonnegative integer solutions (x,y,z) of the equation ax+by+cz=n for given positive integers a, b, c, and n. Our formula involves summations of floor functions of fractions. To quickly evaluate these sums, we find a reciprocity relation that generalizes a well-known reciprocity relation of Gauss related to the law of quadratic reciprocity. Furthermore, we use our result for the number of solutions to a particular equation to prove that the above result of Gauss is equivalent to a well-known result of Sylvester related to the Frobenius Coin Problem. Moreover, using this equivalence and our generalization of the reciprocity relation of Gauss, we obtain a nice generalization of Sylvester's result. In a different problem, we prove four conjectures of Berkovich and Uncu regarding some inequalities about relative sizes of two closely related sets consisting of integer partitions whose parts lie in the interval {s,...,L+s}. Further restrictions are placed on the sets by specifying impermissible parts as well as a minimum part. Our methods consist of constructing injective maps between the relevant sets of partitions. We obtain a very natural combinatorial proof of Euler's recurrence for integer partitions using the principle of inclusion and exclusion. Using our approach, we are able to generalize Euler's recurrence in the sense that for sufficiently large n, we can express p(n) explicitly as an integer linear combination of p(n-k), p(n-k-1),... etc. Using such recurrences, we obtain results related to Ramanujan's congruences. For example, if p_m(n) denotes the number of partitions of n that have largest part at most m, we show that for m > 5, the numbers p_m(5n+4) are not divisible by 5 for infinitely many values of n.

Document type: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
Amarpreet Rattan
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.