Back to UWaterloo



Study of finite or countable discrete structures

A composition of a non negative integer n is a sequence where m1, are positive integers and n = ∑

Binary Strings have some length n, and are a sequence of 0s and 1s, with 2n possibilities

Binomial Coefficients help us tackle "enumeration problems", like how many k-element subsets are there of an n-element set, which we recognize to be the nCk (combinations)

Combinatorial Proof is any proof involving some kind of counting argument

Binomial Theorem: (1+x)n = ∑ (nCk)xk

Show nCk = nC(n-k) with a combinatorial proof

Show the second conjecture is true

Prove (n+k)Cn = k∑i=0 (n+i-1)C(n-1)


Generating Series

Helps us with a very general enumeration problem

Let S be a set of objects, N = {0,1,2...}

So the generating series for S with respect to the weight functon w is:
ΦS(x) = ∑(σ in S)xw(σ)

Theorem 1.6.3
Let ΦS(x) be the generating series for a finite set and weight function w. Then

  1. ΦS(1) = |S| (follows intuitively by the fact that at 1, it is defined to be the sum of all coefficients)
  2. ΦS'(1) = sum of all weights
  3. ΦS'(x)/ΦS(x) = average weight of an element in S


S is the set of all binary strings. Then we have 2^k possible strings

Formal Power Series

Let A(x) and B(x) be two FPS

Examples applying operations:

Substitution (composition)

More Generating Series Tools

Chapter 2

Compositions of a number are basically tuples, whose elements add to to the number (natural numbers), and we say it has k parts for a k-tuple

Binary strings

The weight function for the string is the length of the string

Star Lemma states that if A is a set of binary strings and A * is unambiguous, then the generating series for A * is 1 / (1 - ΦA(x)) with respect to the weight function equal to the length. Note, the geometric series shape

b is a substring of s if s = abc

Block decomposition is breaking a string into blocks of consecutive 1's or 0's: {1}*({0}{0}*{1}{1}*)*{0}*

Chapter 3

We have rational function results, and often want to find [x^n] f(x)/g(x)

We now use recurrences to get the coefficients (example: fibonacci sequence, where the nth term is described in terms of previous terms like n-1 and n-2)

Important takeaway: for a rational function f/g, where deg(f) < deg(g), we can use partial fraction decomposition to break the rational into terms of the form c/(1-ax) or some variant.

We can also find recurrence relations for An from the generating series by taking the denominator polynomial and converting any x^i term to A_{n-i}, then solving for An.

Chapter 4

Graphs are a set of verticies and edges. Isomorphism is a relation between to graphs that describes two sets the are effectively the same.

We can represent graphs using either the adjacency matrix or the incidence matrix. Adjacency between two vertices occurs when they are joined by an edge. A vertex is incident to edges that join it to another vertex.

The adjacency matrix is defined as a p x p matrix A = [aij] where aij = 1 if vi and vj are adjacent and 0 otherwise. Notice that this is symmetric since (1,2) and (2,1) would both be marked 1 as a result of an edge.

A walk is an alternating sequence of edges and vertices. A trail has no repeated edges while a path has no repeated vertices.

Graph colouring and Bipartite graphs

Colouring is useful for register allocation.

Proof: let C2k+1 be a cycle. Assume that it is bipartite and Let (A,B) be a bipartition. Adjust notation so that v1 in A and thus v2 in B, v3 in A, ... In fact, vi in A iff i is odd. Now v2k+1 in A. But v1 and v2k+1 are edges, and both in A. This is a contradiction.

And there's some intuition that we can use (but not prove yet), that if a graph is not bipartite, then it contains some odd cycle as a subgraph. This is why 2-colourable graphs are very easy to solve, while 3-colorable or more is very difficult (there doesn't exist any proof that let's us take a shortcut).

For n ≥ 1, the n-cube is the graph whose vertices are the binary strings of length n, and two strings are adacent <=> they differ in one bit:

n-cubes from 2 to 6

Since each vertex is adjacent to anything differing by 1 bit, then each n bit can differ, so it is incident to n edges. We also have 2^n. Finally, by the handshaking lemma, we have 2^n•n/2 number of edges.

The cut induced by a set of verticies denoted by δ(X) is the set of all edges that have one end in X and the other in X'.

Hamiltonian Cycles go through all verticies of a graph.

Eulerian Circuit is a closed trail which every edge is used.

A 4-regular graph cannot have a bridge


All edges are bridges. Exactly p vertcies and p-1 edges.


planar embedding is a drawing of G on a plane such that no edges cross


Some subset of edges such that every vertex is of degree 1 or 0