Discrete Mathematics

The sum and product rules, counting one set through a bijection to another, the $2^n$ subsets of an $n$ element set, and the pigeonhole principle, which proves that something exists without finding it.

Permutations and combinations recalled from the product rule, then selections with repetition by stars and bars, words with repeated letters, and lattice paths, each counted by finding the right thing to count.

Pascal's rule, the binomial theorem and the identities of Vandermonde and the hockey stick, each proved by counting one set in two ways and setting the answers equal.

The exact correction for overlap when counting a union, proved for any number of sets by tracking how often each element is counted, and applied to onto functions, derangements and Euler's totient.

The Tower of Hanoi, bit strings with no two consecutive 1s and regions cut by lines, each counted by relating it to smaller versions of itself and then solved by unrolling or by a guess confirmed by induction.

Every linear recurrence with constant coefficients solved by one method, the characteristic equation, with distinct and repeated roots, Binet's formula for the Fibonacci numbers, and the particular solution that handles a forcing term.

A sequence stored as the coefficients of a power series, so that counting the ways to make change, solving the Fibonacci recurrence and finding the Catalan numbers all become algebra on a single function.

The division algorithm proved from well-ordering, the greatest common divisor, Euclid's algorithm run by hand and shown to be fast, and Bézout's identity recovered by running it backwards.

Euclid's lemma from Bézout's identity, the proof that every integer factors into primes in exactly one way, the sieve of Eratosthenes, and how thinly the primes are spread, measured against the prime number theorem.

Congruence as an equivalence relation whose classes can be added and multiplied, which classes have inverses and why, solving linear congruences, the Chinese remainder theorem proved by construction, and the ISBN check digit.

Fermat's little theorem and Euler's generalisation proved by one argument, huge powers reduced and computed by repeated squaring, and the RSA cryptosystem carried out in full with small primes, with the reason it is secure only while factoring is hard.

Vertices and edges, degree and the handshake lemma, isomorphism and the invariants that disprove it, connectedness as an equivalence relation, Euler's solution of the Königsberg bridges with both directions of his theorem proved, and the Hamilton question that has no such answer.

The connected graphs without cycles, characterised five equivalent ways, found inside every connected graph as spanning trees, counted by Cayley's formula $n^{n-2}$ through Prüfer's code, and, when rooted and binary, counted by the Catalan numbers.

Euler's formula $V-E+F=2$ proved by induction from a spanning tree, the edge bounds that show $K_5$ and $K_{3,3}$ cannot be drawn without crossings, colourings and the chromatic number, two colourability as the absence of odd cycles, the six colour theorem proved, and the four colour theorem's proof by computer.