Applied Combinatorics (Keller and Trotter)

This book arose from our feeling that a text that met our approach to Applied Combinatorics was not available. Because of the diverse set of instructors assigned to the course, the standard text was one that covered every topic imaginable (and then some), but provided little depth. We’ve taken a different approach, attacking the central subjects of the course description to provide exposure, but taking the time to go into greater depth in select areas to give the students a better feel for how combinatorics works. We have also included some results and topics that are not found in other texts at this level but help reveal the nature of combinatorics to students.

There are three principal themes to our course: Discrete Structures Graphs, digraphs, networks, designs, posets, strings, patterns, distributions, coverings, and partitions. Enumeration Permutations, combinations, inclusion/exclusion, generating functions, recurrence relations, and Pólya counting. Algorithms and Sorting, eulerian circuits, hamiltonian cycles, planarity testing, graph coloring, spanning trees, shortest paths, network flows, Optimization bipartite matchings, and chain partitions. To illustrate the accessible, concrete nature of combinatorics and to motivate topics that we will study, this preliminary chapter provides a first look at combinatorial problems, choosing examples from enumeration, graph theory, number theory, and optimization. The discussion is very informal—but this should serve to explain why we have to be more precise at later stages. We ask lots of questions, but at this stage, you’ll only be able to answer a few. Later, you’ll be able to answer many more … but as promised earlier, most likely you’ll never be able to answer them all. And if we’re wrong in making that statement, then you’re certain to become very famous. Also, you’ll get an A++ in the course and maybe even a Ph.D. too.

Enumeration

Many basic problems in combinatorics involve counting the number of distributions of objects into cells—where we may or may not be able to distinguish between the objects and the same for the cells. Also, the cells may be arranged in patterns. Here are concrete examples.

Combinatorics and Number Theory

Broadly, number theory concerns itself with the properties of the positive integers. G.H. Hardy was a brilliant British mathematician who lived through both World Wars and conducted a large deal of number-theoretic research. He was also a pacifist who was happy that, from his perspective, his research was not “useful”. He wrote in his 1940 essay A Mathematician’s Apology “[n]o one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone will do so for many years.” Little did he know, the purest mathematical ideas of number theory would soon become indispensable for the cryptographic techniques that kept communications secure. Our subject here is not number theory, but we will see a few times where combinatorial techniques are of use in number theory.