What discrete mathematics is for

Calculus studies quantities that change smoothly: the position of a falling stone, the temperature along a rod, the area under a curve. Between any two real numbers there is another, and the central tools of calculus, limits and derivatives, depend on that density. Discrete mathematics studies objects that come in separate, countable pieces: the people at a meeting, the cities on a map, the steps of an algorithm, the bits in a message, the integers themselves. There is no number between 3 and 4 in the integers, no half of a handshake and no city halfway along an edge of a road network that is not itself a point on the map. The questions change accordingly. Instead of asking how fast something changes, we ask how many there are, whether one exists, what the best one is and how the pieces fit together.

Those questions turn out to be everywhere. Every computer is a discrete machine: it stores finitely many bits and moves through its computation one step at a time. Network routing, database design, scheduling, error-correcting codes, cryptography, search engines, genome assembly and the analysis of algorithms all rest on the mathematics in this course. So do puzzles, games and many questions in pure mathematics that have nothing to do with computers. This lesson sets out the main kinds of problem the course studies, introduces the notation we use for sums and products, and works through a first family of examples that shows the habits we want to build: experiment with small cases, guess a pattern, then prove it.

Four kinds of question

Most problems in discrete mathematics are one of four kinds, and recognizing which kind you face is often the first step to solving it.

• Existence: is there an arrangement with the required property? Can a walk cross every bridge of a town exactly once? Is there a schedule in which no student has two exams at once?

• Counting: how many arrangements are there? How many passwords of eight characters, how many ways to choose a committee, how many paths through a grid?

• Optimization: among all possible arrangements, which is best? What is the cheapest network that connects every office, or the shortest route from the warehouse to each store?

• Structure: what must every arrangement of a certain kind look like? Every tree with \(n\) vertices has exactly \(n - 1\) edges; every integer greater than 1 factors into primes in essentially one way.

The kinds often appear together. To find the cheapest network you may first need to know that one exists, then understand the structure of the cheapest ones well enough to search efficiently, and the number of candidates tells you whether checking them all one by one is even possible. A recurring theme of the course is that counting tells you when brute force is hopeless: if there are \(10^{30}\) candidates, no computer will ever check them all, and you need structure instead.

Where this course fits

MATH-260 assumes the material of MATH-100: algebra, functions, sums and a willingness to read and write short arguments. Some lessons use proof by induction and proof by contradiction. If you have taken MATH-228 Introduction to Proofs or CMPUT-272, you have seen these techniques in detail; if not, each lesson explains the arguments it uses as it goes, and the practice questions start gently. We do not repeat the formal logic, set theory and theory of relations that those courses cover. Instead we use proof as a tool for answering concrete questions about counting, recurrences, graphs and integers.

Two later courses build directly on this one. MATH-460 Combinatorics and Graph Theory develops generating functions, inclusion-exclusion, partition and scheduling problems on graphs, matchings, network flows and Ramsey theory. MATH-351 Number Theory takes the divisibility and modular arithmetic of lesson 11 much further, to quadratic reciprocity and modern cryptography. On the computing side, CMPUT-204 studies the running time of the graph algorithms we meet in lessons 9 and 10. Here we concentrate on why those algorithms are correct and what they say about the structure of graphs.

Notation for sums and products

We write long sums with the summation sign. The expression \(\sum_{k=1}^{n} a_k\) means \(a_1 + a_2 + \cdots + a_n\). The letter \(k\) is the index of summation; it is a dummy variable, so \(\sum_{k=1}^{n} k^2\) and \(\sum_{j=1}^{n} j^2\) mean the same thing. The numbers below and above the sign are the lower and upper limits. If the upper limit is smaller than the lower one the sum is empty and equals 0 by convention.

Similarly \(\prod_{k=1}^{n} a_k\) means \(a_1 a_2 \cdots a_n\), and an empty product equals 1. The most important product in the course is the factorial, \(n! = \prod_{k=1}^{n} k = 1 \cdot 2 \cdots n\), with \(0! = 1\) because an empty product is 1. Factorials grow very quickly: \(10! = 3\,628\,800\) and \(20!\) is about \(2.4 \times 10^{18}\).

Three rules let you manipulate sums. Constants factor out: \(\sum c\,a_k = c \sum a_k\). Sums split: \(\sum (a_k + b_k) = \sum a_k + \sum b_k\). And the index can be shifted: \(\sum_{k=1}^{n} a_k = \sum_{j=0}^{n-1} a_{j+1}\), substituting \(j = k - 1\). Most errors with sums come from shifting the index and forgetting to change the limits.

A first example: counting handshakes

At a meeting of \(n\) people, everyone shakes hands with everyone else exactly once. How many handshakes take place? Before reaching for a formula, try small cases. With 2 people there is 1 handshake; with 3 there are 3; with 4 there are 6; with 5 there are 10. The differences are 2, 3, 4: each new arrival shakes hands with everyone already there. So the count for \(n\) people is \(1 + 2 + \cdots + (n - 1)\).

There is a second way to count the same thing. Each of the \(n\) people shakes \(n - 1\) hands, which gives \(n(n - 1)\) hands shaken. But every handshake involves exactly two hands, so this counts each handshake twice. The number of handshakes is therefore \(n(n - 1)/2\). Putting the two counts side by side proves a famous identity:

\[ 1 + 2 + \cdots + (n - 1) = \frac{n(n - 1)}{2}, \qquad\text{or equivalently}\qquad \sum_{k=1}^{n} k = \frac{n(n + 1)}{2}. \]

This argument is called double counting: count one set in two different ways and set the answers equal. It is one of the most powerful ideas in combinatorics, and we use it many times. There is a well-known story that the young Carl Friedrich Gauss added the numbers from 1 to 100 by pairing 1 with 100, 2 with 99 and so on, getting 50 pairs that each sum to 101. The pairing argument is another proof of the same formula: write the sum forwards and backwards, add the two rows term by term and get \(n\) copies of \(n + 1\), which is twice the sum.

Patterns can lie

Experimenting with small cases is how most discoveries in discrete mathematics begin, but a pattern in small cases is evidence, not proof. A classic warning comes from a geometry puzzle. Place \(n\) points on a circle and join every pair with a straight chord, choosing the points so that no three chords meet at a single interior point. Into how many regions do the chords cut the disk? For \(n = 1, 2, 3, 4, 5\) the answers are 1, 2, 4, 8 and 16. The doubling pattern looks certain. But for \(n = 6\) the answer is 31, not 32.

The true formula, which we can prove once we have binomial coefficients in lesson 4, is \(1 + \binom{n}{2} + \binom{n}{4}\): one region to start with, one more for each chord and one more for each crossing point of two chords. It grows like \(n^4\), not like \(2^n\). The code below computes both sequences side by side.

from math import comb

print(" n   formula   doubling guess")
for n in range(1, 11):
    regions = 1 + comb(n, 2) + comb(n, 4)
    guess = 2 ** (n - 1)
    mark = "" if regions == guess else "   <- differs"
    print(f"{n:2d}  {regions:8d}  {guess:10d}{mark}")

 n   formula   doubling guess
 1         1           1
 2         2           2
 3         4           4
 4         8           8
 5        16          16
 6        31          32   <- differs
 7        57          64   <- differs
 8        99         128   <- differs
 9       163         256   <- differs
10       256         512   <- differs

The lesson is not that experiments are useless. They are indispensable for guessing what to prove. The lesson is that only a proof settles the question. Throughout the course, when we find a pattern by computer we then prove it, and when a proof is out of reach we say clearly that a statement is a conjecture.

Brute force and its limits

Computers make it easy to answer small counting questions by listing every possibility. That is a valuable check, and every lesson includes code that does it. The code below counts handshakes among \(n\) people by listing every pair and compares the result with the formula. It also counts, by brute force, the number of ways to order \(n\) people in a line and shows how quickly that number outgrows any computer.

from itertools import combinations, permutations
from math import factorial

for n in range(2, 8):
    people = range(n)
    pairs = sum(1 for _ in combinations(people, 2))
    lines = sum(1 for _ in permutations(people))
    print(f"n={n}: handshakes {pairs:3d} (formula {n*(n-1)//2:3d}), "
          f"orderings {lines:5d} (n! = {factorial(n)})")

# listing every ordering stops being possible very quickly
for n in (10, 15, 20, 25):
    seconds = factorial(n) / 1e9   # a billion orderings per second
    years = seconds / (3600 * 24 * 365)
    print(f"{n} people: {factorial(n):.3e} orderings, about {years:.3g} years to list")

n=2: handshakes   1 (formula   1), orderings     2 (n! = 2)
n=3: handshakes   3 (formula   3), orderings     6 (n! = 6)
n=4: handshakes   6 (formula   6), orderings    24 (n! = 24)
n=5: handshakes  10 (formula  10), orderings   120 (n! = 120)
n=6: handshakes  15 (formula  15), orderings   720 (n! = 720)
n=7: handshakes  21 (formula  21), orderings  5040 (n! = 5040)
10 people: 3.629e+06 orderings, about 1.15e-10 years to list
15 people: 1.308e+12 orderings, about 4.15e-05 years to list
20 people: 2.433e+18 orderings, about 77.1 years to list
25 people: 1.551e+25 orderings, about 4.92e+08 years to list

At a billion orderings per second, listing the orderings of 20 people takes about 77 years, and 25 people would take hundreds of millions of times the age of the universe. This is why discrete mathematics cares so much about counting formulas: a formula answers in an instant a question that brute force could never finish, and it tells us in advance which search problems are hopeless without a cleverer idea.

Three problems that run through the course

Three problems illustrate the territory, and we return to each later.

The bridges of Königsberg. The Prussian city of Königsberg, now Kaliningrad, was built around two islands in the river Pregel, joined to the banks and to each other by seven bridges. Residents asked whether it was possible to walk through the city crossing each bridge exactly once. In 1736 Leonhard Euler showed that it was not, and his argument is usually counted as the beginning of graph theory. Lesson 8 gives the full answer: such a walk exists exactly when the number of land masses touched by an odd number of bridges is 0 or 2. In Königsberg all four land masses touched an odd number of bridges.

Counting passwords. A website requires passwords of 8 characters drawn from the 26 lower-case letters, 26 capitals and 10 digits. How many are possible, and how many are possible if at least one digit is required? Lessons 2 and 3 answer both questions; the second needs the idea of counting the complement, which turns a messy problem into a subtraction.

Connecting offices. A company has six offices and a table of what it would cost to lay a network cable between each pair. Which links should it build so that every office can reach every other at the lowest total cost? Lesson 9 shows that the answer is always a tree, a network with no cycles, and that a simple greedy rule, always adding the cheapest link that does not create a cycle, finds the best tree.

How to read a proof in this course

Proofs in discrete mathematics are often short, but they reward slow reading. For each step, ask what it uses: a definition, an earlier result, a calculation, or one of the standard techniques. The techniques we use most are direct calculation, double counting, the pigeonhole principle of lesson 2, induction and contradiction. When a proof uses induction we name the statement \(P(n)\) being proved, check the base case and show that \(P(n)\) implies \(P(n + 1)\), or for strong induction that all of \(P(1), \dots, P(n)\) together imply \(P(n + 1)\). MATH-228 treats these techniques in depth; here we use them as tools.

Here is a short induction proof of the handshake formula, to show the pattern. Let \(P(n)\) be the statement that \(n\) people make \(n(n-1)/2\) handshakes. \(P(1)\) holds, since one person makes no handshakes and \(1 \cdot 0 / 2 = 0\). Suppose \(P(n)\) holds and a new person arrives. The new person shakes hands with each of the \(n\) people already present, so the total becomes \(n(n - 1)/2 + n = n(n + 1)/2\), which is the formula with \(n + 1\) in place of \(n\). So \(P(n + 1)\) holds, and by induction \(P(n)\) holds for all \(n \ge 1\).