Combinatorics is the study of discrete (often finite) structures that arise not only in areas of pure mathematics, but in other areas of science, for example computer science, statistical physics and genetics. From ancient beginnings, this subject truly rose to prominence from the mid-20th century, when scientific discoveries (most notably of DNA) showed that combinatorics is key to understanding the world around us, whilst many of the great advances in computing were built on combinatorial foundations.
The combinatorics half of this module starts by looking at naïve set theory, introducing the notions of partitions, equivalence relations and the notion of countable and uncountable infinite sets. Sophisticated counting techniques are developed before an introduction to the field of graph theory, which provides a mathematical framework for the study of both real-world and virtual networks.
One of the most powerful techniques of pure mathematics is that of abstraction, which allows deep relationships between apparently unrelated areas to become apparent. Abstract algebra is a powerful example of this technique, abstracting notions of symmetry and the properties of arithmetic to reveal algebraic structures such as groups, rings and fields. Despite their very abstract nature, these ideas have significant real world applications, for example in communication theory and internet security.
Using familiar examples of the natural numbers, real numbers and polynomials as motivation, the axioms for groups, rings and fields are introduced and basic properties of these structures are explored. Elementary number theory, the Euclidean algorithm, and prime numbers are discussed.
Underlying themes throughout this module are techniques of proof and the importance of mathematical writing.
By the end of the module students should be able to:
- Perform basic set theoretic manipulations and determine the countability or uncountability of various sets.
- Apply various techniques, including the sum and product rules and the binomial theorem to count finite collections.
- Know and use the basic notions and results of graph theory.
- Prove elementary statements in basic number theory and make deductions from axioms.
- Determine the cycle type of a permutation and calculate products of permutations.
- Apply the Euclidean algorithm to both natural numbers and polynomials.
- Give non trivial examples of groups, rings and fields.