Discrete Structures and Applications (Honours)

Enumeration and inclusion-exclusion

Counting begins with a precise equivalence rule: decide when two constructions count as the same object. Inclusion-exclusion corrects repeated counting across overlapping forbidden events. For permutations with no fixed points, let event i mean position i contains its original item. Counting permutations that satisfy selected fixed-point events and alternating signs yields the derangement formula n! times the sum from k = 0 to n of (-1)^k/k!. The formula follows the model rather than replacing it. State the universe, forbidden events, and intersection counts before simplifying the algebra.

References: Carleton Undergraduate Calendar — COMP 3805 · Keller and Trotter — Applied Combinatorics

Generating functions and recurrence relations

An ordinary generating function packages a sequence as A(x) = sum a_n x^n. Multiplication corresponds to convolution, which models splitting a total size between independent component choices. For selecting any nonnegative number of identical objects, 1 + x + x^2 + ... encodes one choice at each size. Three such factors encode ordered triples of nonnegative integers by total. A recurrence can become an algebraic equation for A(x), but initial terms must be included correctly. Formal power-series reasoning concerns coefficients and does not require treating x as a convergent numerical input.

References: Carleton Undergraduate Calendar — COMP 3805 · Keller and Trotter — Applied Combinatorics

Connectivity, Euler trails, Hamilton paths, and planarity

An Euler trail uses each edge once, while a Hamilton path visits each vertex once. These are different constraints and have different characterizations. A connected undirected graph with exactly two odd-degree vertices has an open Euler trail between them; zero odd-degree vertices permits an Euler circuit. Planarity asks whether a graph can be drawn without edge crossings. For a connected plane graph, V - E + F = 2 counts faces including the unbounded one. Edge bounds can disprove planarity under their assumptions, but satisfying a bound alone does not prove a graph planar.

References: Carleton Undergraduate Calendar — COMP 3805 · Keller and Trotter — Applied Combinatorics

Error-correcting codes and Hamming distance

A code selects permitted words from a larger space. Hamming distance counts positions where two equal-length words differ. If the minimum distance is d, up to d-1 symbol errors can be detected, and up to floor((d-1)/2) can be corrected uniquely by nearest-codeword reasoning. The correction bound follows because balls of that radius around distinct codewords do not overlap. A binary repetition code {000,111} has distance three: it can correct one flipped bit using majority decoding. Detection and correction guarantees concern a stated error model, not every imaginable channel behavior.

References: Carleton Undergraduate Calendar — COMP 3805 · University of Lethbridge — Combinatorics open textbook

Block designs and finite geometries

A block design distributes a finite point set among subsets so that specified combinations occur in controlled ways. In a balanced incomplete block design with v points, b blocks, block size k, replication r, and pair multiplicity lambda, double-counting incidences gives vr = bk and r(k-1) = lambda(v-1). These are necessary arithmetic conditions rather than automatic existence proofs. The Fano plane has seven points and seven three-point lines; each point lies on three lines and each pair determines one line. Finite geometry supplies structured incidence examples useful for combinatorial constructions.

References: Carleton Undergraduate Calendar — COMP 3805 · University of Lethbridge — Combinatorics open textbook

Symmetry, group actions, and a worked orbit count

When objects equivalent under rotation count as one, dividing by the number of rotations can fail because some objects have extra symmetry. Burnside’s lemma counts orbits by averaging the number fixed by each group element. For binary colorings of three necklace positions under rotations only, the identity fixes all 8 colorings, and each of the two nontrivial rotations fixes only the 2 constant colorings. The orbit count is (8 + 2 + 2)/3 = 4. Including reflections would change the group and requires its own fixed-point count.

References: Carleton Undergraduate Calendar — COMP 3805 · Keller and Trotter — Applied Combinatorics

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Carleton Undergraduate Calendar — COMP 3805 ↗Calendar course scope · 2026–27
• Keller and Trotter — Applied Combinatorics ↗Open author textbook · 2017 edition and corrections
• University of Lethbridge — Combinatorics open textbook ↗Open author textbook · Public reference; checked 2026-11-05