I Basic Counting (pg. 5)

1 Selections (pg. 5)

1.1-1.4 Basic counting formulas

Given a set of \(n\) objects, the number of ways of selecting \(r\) objects can be found according to the table below.

No repetitionWith repetition
Order matters (Ordered)\(\frac{n!}{(n-r)!}\)\(n^r\)
Order does not matter (Unordered)\(\binom{n}{r} = \frac{n!}{(n-r)!r!}\)\(\binom{n+r-1}{r} = \binom{n+r-1}{n-1}\)

1.4 Intuition for unordered selections with repetition

This is the balls and buckets representation. If we wish to select \(r\) objects from an \(n\)-set, we essentially want to count the number of ways we can split up the \(n\) objects (i.e. the balls) into \(r\) parts (i.e. the buckets). Say we have \(n=8\) balls and set \(r=3\). Under the original question, we ask" “how many unordered selections of 3 objects from 8 objects are there with repetition allowed?”. Under this buckets and balls framework, we ask, “how many ways can we fill 3 buckets with 8 balls, if some of those buckets can be empty?”.

(to edit)

Equivalent combinatorial counts

(to edit)

2 Combinatorial Identities (pg. 9)

Pascal’s Triangle

  • \(\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}\)
  • \(\left(x+y\right)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n}y^{n-r}\)
  • \(\sum_{r=0}^{n} \binom{n}{r} = 2^n\)
  • \(\binom{n}{r} = \sum_{i=0}^{n-1} \binom{i}{r-1}\)
    • Equivalently, can index from \(r-1\) to \(n\)
  • \(\sum_{r=0}^{n} (-1)^{r}\binom{n}{r}=0\)

3 The Principle of Inclusion and Exclusion (pg. 13)

4 Permutations and Derangements (pg. 15)

5 Classical M¨obius Inversion (pg. 17)

Upcoming

  • 6 Partially Ordered Sets (pg. 20)
  • 7 M¨obius Function for Posets (pg. 22)
  • III Counting with Groups (pg. 24)
  • 8 Symmetry Groups and Group Actions (pg. 24)
  • 9 Orbits and Stabilizers (pg. 26)
  • 10 The Counting Theorem (pg. 28)
  • IV Generating Functions and Partitions (pg. 31)
  • 11 Ordinary Generating Functions (pg. 31)
  • 12 Exponential Generating Functions (pg. 36)
  • 13 Linear Recurrence Relations (pg. 40)
  • 14 Partitions (pg. 44)
  • V Classification of surfaces (pg. 49)
  • 15 Basic concepts (pg. 49)
  • 16 The big questions (pg. 51)
  • 17 More surfaces (pg. 52)
  • 18 Invariants and Euler characteristic (pg. 54)
  • 19 Small polygonal constructions (pg. 56)
  • 20 Orientability (pg. 58)
  • 21 Operations on polygons (pg. 59)
  • 22 Word representations (pg. 61)
  • 23 Rules for words (pg. 63)
  • 24 The classification theorem (pg. 66)
  • VI Graph Theory (pg. 70)
  • 25 Introduction to Graphs (pg. 70)
  • 26 Walks in graphs (pg. 75)
  • 27 Trees (pg. 78)
  • 28 Matchings (pg. 80)
  • 29 Graph colouring (pg. 82)
  • VII Graph Algorithms (pg. 87)
  • 30 Shortest Paths (pg. 87)
  • 31 Spanning Trees (pg. 88)
  • 32 Finding patterns in strings (pg. 89)
  • 33 Algorithms for maximum matchings in bipartite graphs (pg. 90)
  • VIII Design Theory (pg. 95)
  • 34 Introduction to Combinatorial Design Theory (pg. 95)
  • 35 Latin Squares (pg. 96)
  • 36 Steiner Triple Systems (pg. 97)

Everything sourced from my discrete maths course unless stated otherwise.

Related notes: