Mathematics · Intermediate · 30 min · Chapter 11 of 28

Discrete mathematics

The mathematics of separate things: sets, counting, graphs, and the first careful proofs by induction.

Read first: Algebra

The idea

Discrete mathematics studies objects that come in distinct pieces: integers, sets, strings, graphs, logical statements. The operations on sets are union, intersection, and complement, and they obey laws that look exactly like the laws of logic if you read union as or, intersection as and, and complement as not. Inclusion-exclusion repairs the overcount when you add the sizes of overlapping sets.

Counting is organized division of labor. If a task splits into independent choices, multiply. If it splits into exclusive cases, add. A permutation of k items out of n is n! / (n − k)!, because order matters. A combination divides by the k! orders of the chosen items, leaving C(n, k) = n! / (k!(n − k)!). The binomial theorem says (x + y)ⁿ expands into those coefficients.

A graph G = (V, E) has a finite set of vertices and a set of edges joining pairs of them. The degree of a vertex is the number of edges that touch it. Summing degrees counts each edge twice, so the sum of degrees is 2|E|, and the number of odd-degree vertices is even. Induction is the proof technique that matches the structure of the positive integers: prove the claim at n = 1, and prove that if it holds at n then it holds at n + 1. The inductive hypothesis is a gift you are allowed to use, not a conclusion you have already fully earned.

Hold onto this

A set is determined by its elements. Order and repetition do not matter.
Combinations count unordered selections; permutations count ordered ones.
A graph is vertices joined by edges. The handshaking lemma doubles the edge count.
Induction proves a statement for every positive integer by a base step and a successor step.

Formulas

Inclusion-exclusion, two sets

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

Adding sizes double-counts the overlap. Subtract it once.

|A|: Number of elements in A

Combinations

(k n) = \frac{n !}{k ! ( n - k )!}

Ways to choose k items from n when order does not matter.

n!: n × (n − 1) × … × 1

Permutations

P (n, k) = \frac{n !}{( n - k )!}

Ways to choose k items from n when order matters.

P(n, k): n × (n − 1) × … × (n − k + 1)

Handshaking lemma

v \in V \sum de g (v) = 2∣ E ∣

The sum of all degrees is twice the number of edges.

deg(v): Number of edges incident to v

Binomial theorem

(x + y)^{n} = k = 0 \sum n (k n) x^{n - k} y^{k}

Each term picks y from k of the n factors and x from the rest.

n: A nonnegative integer

Worked examples

1. Committees versus slates

From 10 people, how many ways can you choose a committee of 3? How many ways can you assign president, secretary, and treasurer, with no person holding two offices?

Committee: order does not matter, so C(10, 3) = (10×9×8) / (3×2×1) = 720/6 = 120.
Offices: order matters, so P(10, 3) = 10 × 9 × 8 = 720.
The ratio is 3! = 6, the number of ways to rank a given trio.

120 committees, 720 slates.

2. Induction for the sum of the first n integers

Prove that 1 + 2 + … + n = n(n + 1)/2.

Base: n = 1 gives 1 = 1×2/2.
Assume the formula holds for n = m: the sum to m is m(m + 1)/2.
Sum to m + 1 is that quantity plus (m + 1) = (m + 1)(m/2 + 1) = (m + 1)(m + 2)/2.
The formula holds for m + 1. By induction it holds for every positive integer.

The closed form is n(n + 1)/2.

Try these

A graph has 6 vertices, all of degree 3. How many edges?

How many subsets does an n-element set have?

Common mistakes

Combinations and permutations answer different questions. If the seats are labeled, you wanted permutations.
The inductive step must work for an arbitrary m, not for a single example you tried.
In graphs, a loop contributes 2 to the degree in the usual convention, because it meets the vertex twice. Know which convention a text is using.