Combinatorics (Morris)

Combinatorics is an upper-level introductory course in enumeration, graph theory, and design theory. The text focuses on combinations and arrangements of discrete structures. There are five major branches of combinatorics that we will touch on in this course: enumeration, graph theory, Ramsey Theory, design theory, and coding theory. (The related topic of cryptography can also be studied in combinatorics, but we will not touch on it in this course.) We will focus on enumeration, graph theory, and design theory, but will briefly introduce the other two topics.

Introduction

Combinatorics is a subfield of “discrete mathematics,” so we should begin by asking what discrete mathematics means. The differences are to some extent a matter of opinion, and various mathematicians might classify specific topics differently.

“Discrete” should not be confused with “discreet,” which is a much more commonly-used word. They share the same Latin root, “discretio,” which has to do with wise discernment or separation. In the mathematical “discrete,” the emphasis is on separateness, so “discrete” is the opposite of “continuous.” If we are studying objects that can be separated and treated as a (generally countable) collection of units rather than a continuous structure, then this study falls into discrete mathematics.

In calculus, we deal with continuous functions, so calculus is not discrete mathematics. In linear algebra, our matrices often have real entries, so linear algebra also does not fall into discrete mathematics.

Textbooks on discrete mathematics often include some logic, as discrete mathematics is often used as a gateway course for upperlevel math. Elementary number theory and set theory are also sometimes covered. Algorithms are a common topic, as algorithmic techniques tend to work very well on the sorts of structures that we study in discrete mathematics.

In Combinatorics, we focus on combinations and arrangements of discrete structures. There are five major branches of combinatorics that we will touch on in this course: enumeration, graph theory, Ramsey Theory, design theory, and coding theory. (The related topic of cryptography can also be studied in combinatorics, but we will not touch on it in this course.) We will focus on enumeration, graph theory, and design theory, but will briefly introduce the other two topics.

Enumeration

Enumeration is a big fancy word for counting. If you’ve taken a course in probability and statistics, you’ve already covered some of the techniques and problems we’ll be covering in this course. When a statistician (or other mathematician) is calculating the “probability” of a particular outcome in circumstances where all outcomes are equally likely, what they usually do is enumerate all possible outcomes, and then figure out how many of these include the outcome they are looking for.