Discrete mathematics

Contents
1. Counting problems 3
1.1. Basic results on counting sets 3
1.2. Binomial coefficients 4
2. Estimates: O, o-notation, Stirling formula, Birthday paradox and the bell curve 7
2.1. O, o-notation 7
2.2. Stirling’s formula 7
2.3. Twin paradox 7
3. Inclusion-exclusion principle 10
3.1. Inclusion-exclusion principle 10
3.2. Number of permutations without fixed points 10
3.3. Euler’s totient function 11
4. Generating functions 12
4.1. Combinatorial applications of polynomials 12
4.2. Multinomial theorem 12
4.3. Calculation with power series 12
4.4. Examples of generating functions 13
5. Generating functions. Binary trees. 14
5.1. Binary trees 14
6. Fibonacci numbers and linear recurrence relations 16
6.1. Fibonacci sequence 16
6.2. Linear recurrence relations 18
7. Möbius invertion formula 19
7.1. Identities with Euler’s totient function 20
7.2. Number of cyclic sequences 20
7.3. Partially ordered sets (or posets) 23
7.4. Hasse diagram 23
7.5. Möbius invertion for posets 23
8. Elements of graph theory 27
8.1. Definition and characterizations of trees 27
9. Equivalent definitions of a tree, number of labeled trees 28
9.1. Graph isomorphisms 28
9.2. Characterizations of trees 28
9.3. Counting labeled trees 28
9.4. Counting unlabeled trees 29
10. Kruskal’s algorithm for finding a minimal spanning tree 30
10.1. Subgraphs, induced subgraphs, and spanning trees 30
10.2. Weighted graphs 30
11. Counting spanning trees in a graph. Kirchhoff’s theorem 32
11.1. A useful fact form linear algebra 32
11.2. Laplace matrix and incidence matrix 32
11.3. Kirchhoff’s theorem 32
12. The probabilistic method. 33
12.1. Finite probability spaces 33
12.2. Applications of probabilistic method 33
1
2

13. Bipartite graphs. König-Hall theorem. Sperner theorem 35

References 36
 3

1. Counting problems
To read:
[1]: 1.2. Sets, 1.3. Number of subsets, 1.5. Sequences, 1.6. Permutations, 1.7. Number of The
Number of Ordered Subsets, 1.8. The Number of Subsets of a Given Size, 3.1. The Binomial
Theorem, 3.2. Distributing Presents, 3.5. Pascal’s Triangle, 3.6. Identities in Pascal’s Triangle.
[3], Chapters 3.1-3.3.
1.1. Basic results on counting sets.
Notation. Let A be a finite set. We denote by |A| the cardinality of A, i. e. the number of
elements in the set.
Definition 1.1. Denote by [n] the set of first n natural numbers: [n] := {1, 2, . . . n}.
Theorem 1.2. If there exists a bijection between finite sets A and B then |A| = |B|.
Theorem 1.3. (Addition rule) Let A and B be finite sets. If A∩B = ∅ then |A∪B| = |A|+|B|.
Theorem 1.4. (Product rule) Let A and B be finite sets. Then
|A × B| = |A| · |B|.
Recall the following formulas:
Proposition 1.5. The number of functions from [m] to [n] is nm . This is the number of m-letter
words in an n-letter alphabet.
Proposition 1.6. The number of permutations of a set of n elements is n!
Proof. This is likely to be familiar to you, but at any rate it follows from the multiplication rule.
Call the elements 1, . . . , n. A permutation can send 1 to any of n elements. Then 2 to any of
the n − 1 elements remaining, since 1 and 2 cannot be sent to the same. Each step leaves one
less option at the next step, for a total of
n × (n − 1) × . . . × 2 × 1
permutations. This is n! by definition (or really, if we refuse to skip steps, by induction). 
Proposition 1.7. The number of ways in which one can choose k objects out of n distinct
n!
objects, assuming the order of the elements matters, is (n−k)! .
Proof. It will dramatically speed up computations to note that
n!
= n(n − 1) . . . (n − k + 1)
(n − k)!
This should be calculated as a product of k numbers, not a ratio of two factorials. In fact, this
form also shows how to deduce the formula from the multiplication rule. One has n choices for
the first object, then n − 1 for the second, culminating in n − k + 1 for the last of the k objects.
Notice that when k = n, Propositions 1.6 and 1.7 agree. This would be clear even without
the explicit formulae: an ordered choice of all n out of the n objects is simply a way to permute
them.
Set-theoretically, n(n − 1) · · · (n − k + 1) is also the number of injective functions from [k] to
[n]. 
Proposition 1.8. The number of ways in which one can choose k objects
out of n distinct
n!
objects, assuming the order of the elements does not matter, is (n−k)!k! =: nk . This is the same
as the number of subsets of k elements of an n-element set.
4

n n!


Definition 1.9. The numbers k = (n−k)!k! are called binomial coefficients.
Proof. We already know the number of ordered subsets, by Proposition 1.7. On the other hand,
an ordered subset can be obtained in two steps: choose a subset, and then order it. Once the
choice of k elements is made, Proposition 1.6 tells us there are k! ways to do the ordering. By
the multiplication rule,  
n! n
= k!
(n − k)! k
and we complete the proof by solving for nk .



As with unordered choices, there is no need to compute all the factorials. Instead, note that
 
n n! n(n − 1) . . . (n − k + 1)
= =
k (n − k)!k! k!
If k is small, then we can afford to compute k! in the denominator. If k is large, then it is better
to exploit a basic symmetry of the binomial coefficients.
Proposition 1.10.    
n n
=
k n−k
We will be convenient for us to use the following notation:
A


Notation. Let A be a finite set and k be a nonnegative integer. Then k is the set of k-element
subsets of A. We have A = |A|



k k .

1.2. Binomial coefficients. The following is called Pascal’s triangle

Row
0


0 0 =1
1 1



1 0 =1 1 =1
2 2 2




2 0 =1 1 =2 2 =1
3 3 3 3





3 0 =1 1 =3 2 =3 3 =1
4 4 4 4 4






4 0 =1 1 =4 2 =6 3 =4 4 =1
5 5 5 5 5 5







5 0 =1 1 =5 2 = 10 3 = 10 4 =5 5 =1

Proposition 1.11. The following identities hold:

(1) nk + k+1 n
= n+1




k+1 .
(2) nk is the k-th element in the n-th line of Pascal’s triangle.

Proof. Recall that n+1

k+1 is the number of subsets of cardinality k + 1 in the set [n + 1]. Each
subset of [n + 1] either contains the element n + 1 or not. The number of elements in [n+1]


k+1
containing n + 1 is nk and the number of elements in [n+1] n




k+1 not containing n + 1 is k+1 . Now
we apply the Addition rule and finish the proof. 
 5

Proposition 1.12. The number of subsets of an n-element set is 2n , since we have

     
n n n
2n = + + ... + .
0 1 n
The number of subsets of an n-element set having odd cardinality is 2n−1 . The number of subsets
of an n-element set having even cardinality is 2n−1 .
The equalities above can be obtained using the binomial theorem.
Theorem 1.13.
      n  
n n n n X n i
(1 + x)n = + x + ... + x = x.
0 1 n i
i=0

Proof. To prove the binomial theorem, consider how to distribute the multiplication in
(1 + x)n = (1 + x)(1 + x) . . . (1 + x)
From each factor 1 + x, we can choose either the 1 or the x to form a product with the
other
terms. This product is xk provided we choose x in k out of the n factors. There are nk such
choices, and collecting terms gives the sum k nk xk as claimed.
P



Proof of Proposition 1.12. For x = 1, respectively x = −1, we obtain

      X n  
n n n n n
2 = + + ... + =
0 1 n i
i=0
      X n  
n n n n
0= − + . . . + (−1)n = (−1)i .
0 1 n i
i=0

Adding, respectively subtracting the two relations, and dividing each by two, one obtains
   
n−1 n n
2 = + + ...
0 2
   
n−1 n n
2 = + + ...
1 3
which proves the statements about the number of even/odd sets.


Proposition 1.14. Assume we have k identical objects and n different persons. Then, the
number of ways in which one can distribute this k objects among the n persons equals
   
n+k−1 n+k−1
= .
n−1 k
Equivalently, it is a number of solutions of the equation x1 + . . . + xn = k in nonnegative integers
or the number of k-multisets containing elements from [n]. If k ≥ n and
each persons receives
k−1
at least 1 object, then the number of possible ways to distribute is n−1 .
Proof. Let A be the set of all solutions of the equation
(1) x1 + . . . + xn = k, xi ∈ Z≥0 .
6

Let B be the set of all subsets of cardinality n − 1 in [k + n − 1]. We construct a bijection

ψ : A → B in the following way: a solution (x1 , . . . , xn ) is mapped to the subset
B := {x1 + 1, x1 + x2 + 2, . . . , x1 + x2 + . . . + xn−1 + n − 1}.
First, we check that B belongs to B. Indeed, the inequalities
1 ≤ x1 + 1 < x1 + x2 + 2 < · · · < x1 + x2 + . . . xn−1 + n − 1 ≤ k + n − 1
imply that the elements of B are distinct and belong to [k + n − 1].
Next, to show that ψ is a bijection we compute its inverse map. Let B be an element of B.
Suppose that
1 ≤ b1 < b2 < · · · < bn−1 ≤ k + n − 1
are the elements of B written in the increasing order. Then the preimage ψ −1 (B) is an n-tuple
of integers (x1 , . . . , xn ) defined by
x1 = b1 − 1
xi = bi − bi−1 − 1, i = 2, . . . , n − 1
xn = k + n − 1 − bn−1 .
It is easy to see from these equations that the numbers xi , i = 1, . . . n, are non-negative integers
and x1 + . . . + xn = k.
Since there is a bijection between sets A and B, their cardinalities are equal and
 
k+n−1
|A| = |B| = .
n−1

 7

2. Estimates: O, o-notation, Stirling formula, Birthday paradox and the bell

curve
To read:
[1] 2.2.4. Pigeonhole principle. 2.2.5 The Twin Paradox
[3] 3.4. Estimates: an introduction - starting from 3.4.2. - Big Oh, little oh, 3.5.5. Estimate n!
- second proof only, 3.7. Inclusion - Exclusion.

2.1. O, o-notation.
Definition 2.1. Let f, g : Z≥0 → R. We say that f is big-Oh of g and we write f (x) = O(g(x))
if there exist n0 and c constants such that for all n > n0 , we have |f (n)| < c · |g(n)|.
Definition 2.2. Let f, g : Z≥0 → R. We say that f is little-oh of g and we write f (x) = o(g(x)) if
f (n)
lim = 0.
n→∞ g(n)
Examples: n = O(n2 ) and also n = o(n2 ), n = O(2n ), n = o(2n ), sin(n) = O(1) and sin(n) is
not o(1).

2.2. Stirling’s formula.

Theorem 2.3. (Stirling’s formula)
√  n n
n! ∼ 2πn ,
e
where ∼ is used to indicate that the ratio of the two sides tends to 1 as n goes to ∞.
2.3. Twin paradox. Suppose that there are 50 students in a math class. What are the chances
that two of them share the same birthday?
Theorem 2.4. Suppose that k ≤ n are positive integers and each of k different people chooses
1 element from the set [n]. Their choices are uniformly random and independent. Then the
n!
probability P = (n−k)!nk that they have chosen k different elements can be estimated as

−k(k−1) −k(k−1)
e 2(n−k+1) ≤ P ≤ e 2n .
Proof. We will use the following inequality for ln(x).
Lemma 2.5. For x > 0,
x−1
≤ ln(x) ≤ x − 1.
x
Now we estimate
nk
       
n n n
ln = ln + ln + . . . + ln
n(n − 1) · · · (n − k + 1) n−1 n−2 n−k+1
n n n
− 1 − 1 − 1 1 2 k−1
≥ n−1n + n−2n + . . . + n−k+1
n = + + ... +
n−1 n−2 n−k+1 n n n
1 k(k − 1)
= (1 + 2 + . . . + (k − 1)) = .
n 2n
8

Also we find
nk
       
n n n
ln = ln + ln + . . . + ln
n(n − 1) · · · (n − k + 1) n−1 n−2 n−k+1
     
n n n 1 2 k−1
≤ −1 + − 1 + ... + −1 = + + ... +
n−1 n−2 n−k+1 n−1 n−2 n−k+1
1 2 k−1 1
≤ + + ... + = (1 + 2 + . . . + (k − 1))
n−k+1 n−k+1 n−k+1 n−k+1
k(k − 1)
= .
2(n − k + 1)
Applying the exponential function to both sides of our estimates we get the following:
−k(k−1) n(n − 1) · · · (n − k + 1) −k(k−1)
e 2(n−k+1) ≤ k
≤ e 2n .
n

So the answer to the question in the beginning of this paragraph is between 96.51% and
97.93%. More precisely, the probability is about 97.03%.
Now we will estimate the binomial coefficients. The binomial coefficients in the n-th row of
the Pascal’s triangle satisfy the following inequalities:
     
n n n
< < ··· <
0 1 [n/2]
and        
n n n n
> > ··· > > .
[n/2] + 1 [n/2] + 2 1 0
n


Therefore, the middle binomial coefficient [n/2] is the largest in the respective row. Stirling’s
formula implies that the largest binomial coefficient satisfies
  r
n 2 n
∼ 2 .
n/2 πn
Also we have the following formula describes how binomial coefficients decrease as we move away
from the middle of the Pascal’s triangle.
Proposition 2.6. Let m, t be positive integers and t ≤ m. Then
2m


2 /(m−t+1) m−t 2 /(m+t)
e−t ≤ 2m

≤ e−t .
m
Proof. Here we prove the lower bound. We have
2m


m (m + t)(m + t − 1) · · · (m + 1)
2m = m(m − 1) · · · (m − t + 1)
.


m−t
It will be convenient for us to estimate the logarithm of this quantity.
       
(m + t)(m + t − 1) · · · (m + 1) m+t m+t−1 m+1
ln = ln + ln + . . . + ln
m(m − 1) · · · (m − t + 1) m m−1 m−t+1
     
m+t m+t−1 m+1 t t t
≤ −1 + − 1 + ... + −1 = + + ... +
m m−1 m−t+1 m m−1 m−t+1
t t t t2
≤ + + ... + = .
m−t+1 m−t+1 m−t+1 m−t+1
 9

This finishes the proof of the first inequality. The proof of the second inequality is left to the
reader. 
10

3. Inclusion-exclusion principle
To read:
[1] 2.2.1. Induction, 2.3. Inclusion-Exclusion.
[3] 3.7. Inclusion - Exclusion, 3.8. The hat-check lady.

3.1. Inclusion-exclusion principle.

Theorem 3.1. (Inclusion-Exclusion principle). Let A1 , . . . , An be finite sets. Then, the follow-
ing holds
n
[ X X X
Ai = |Ai | − |Ai ∩Aj | + |Ai ∩Aj ∩Ak |−. . .+(−1)n−1 |A1 ∩A2 ∩· · ·∩An |.
i=1 1≤i≤n 1≤i<j≤n 1≤i<j<k≤n
Sn
Proof. Suppose that an element a ∈ i=1 Ai belongs to exactly k different sets.
How many times did we count a in the inclusion-exclusion formula
X X X
|Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − . . . ?
1≤i≤n 1≤i<j≤n 1≤i<j<k≤n
k
Element a is counted (−1)`−1


` times in the `-th sum as ` goes from 1 to n. By the binomial
theorem we have
n  
`−1 k
X
(−1) = 1.
`
`=1
Therefore, each element a is counted exactly once. This finishes the proof. 

3.2. Number of permutations without fixed points. A hat-check girl completely loses
track of which of n hats belong to which owners, and hands them back at random to their n
owners as the latter leave. What is the probability pn that nobody receives their own hat back?
This question can be reformulated in the following way: find the number of permutations
of the set {1, 2, . . . , n} without fixed points. In order to count these, we apply the inclusion-
exclusion principle. Let A be the set of all permutations and Ai be the set of permutations of
the set {1, 2, . . . , n} for which i is a fixed point. The number of permutations with no fixed
points is
[n
|A| − Ai .
i=1
We know that |A| = n!, so we need to count | ni=1 Ai |. We do this using the inclusion principle.
S
Note that Ai ∩ Aj represents the set of all permutations for which i and j are fixed points. One
can see that |Ai | = (n − 1)! for all i, while |Ai ∩ Aj | = (n − 2)!. Using the same idea, we obtain
|Ai ∩ Aj ∩ Ak | = (n − 3)! and so on. Altogether, this gives
n    
[ n n
|A| − Ai = n! − (n − 1)! + (n − 2)! − . . .
1 2
i=1
n!(n − 1)! n!(n − 2)!
= n! − + − ...
1!(n − 1)! 2!(n − 2)!
1 1 1
= n!( − + − . . .)
0! 1! 2!
≈ n! exp(−1).
 11

Thus we see that the probability pn that nobody receives their own hat back is
1 1 1 1
pn = − + − . . . + (−1)n
0! 1! 2! n!
As n goes to infinity this number converges to 1e ≈ 0.37.
3.3. Euler’s totient function. In number theory, Euler’s totient function φ(n) counts the
positive integers up to a given integer n that are relatively prime to n. For example, among the
numbers {1, 2, 3, 4, 5, 6} only 1 and 5 are coprime to 6. Therefore, we find that φ(6) = 2. If p is
a prime number then φ(p) = p − 1 and φ(pk ) = pk − pk−1 .
Proposition 3.2. Suppose that a number n has the prime factorization n = pk11 · · · pkmm . Then
by the inclusion-exclusion principle we find
X n m
X n X n Y 1
φ(n) = n − + − + . . . = n (1 − ).
pi pi pj pi pj pk pi
1≤i≤m 1≤i<j≤m 1≤i<j<k≤m i=1

Proof. Let A be the set of all numbers in [n] not coprime with n.
Let Ai be the
S set of all numbers in [n] divisible by pi .
Then A = m i=1 A i and |A i | = n
, n
pi |Ai ∩Aj | = pi pj , and so on. By the inclusion-exclusion formula
we find
φ(n) =n − |A|
X n m
X n X n Y 1
=n − + − + . . . = n (1 − ).
pi pi pj pi pj pk pi
1≤i≤m 1≤i<j≤m 1≤i<j<k≤m i=1

12

4. Generating functions
To read:
[3] Chapters 12.1, 12.2.

4.1. Combinatorial applications of polynomials.

Example. How many ways are there to pay the amount of 21 francs with 6 one-francs coins, 5
two-francs coins, and 4 five-francs coins? The requited number is in fact the number of solutions
of the equation
(2) x1 + x2 + x3 = 21,
with x1 ∈ {0, 1, 2, 3, 4, 5, 6}, x2 ∈ {0, 2, 4, 6, 10}, and x3 ∈ {0, 5, 10, 15, 20}. In order to compute
this, we associate to each variable xi a polynomial pi as follows:
p1 (x) = 1 + x + x2 + x3 + x4 + x5 + x6 ,
p2 (x) = 1 + x2 + x4 + x6 + x8 + x10 ,
p3 (x) = 1 + x5 + x10 + x15 + x20 .
The number of solutions of equation (2) above will be the cofficient of x21 in the product
p1 (x)p2 (x)p3 (x).
Exercise 1. A box contains 30 red, 40 blue, and 50 white balls; balls of the same color are
indistinguishable. How many ways are there of selecting a collection of 70 balls from the box?
4.2. Multinomial theorem.
Theorem 4.1. (Multinomial theorem). The following holds:
X k!
(x1 + x2 + . . . + xn )k = xi1 xi2 · · · xinn .
i1 ! i2 ! · · · in ! 1 2
i1 ,i2 ,...,in ≥0
i1 +i2 +...+in =k

4.3. Calculation with power series.

Definition 4.2. Let (a0 , a1 , . . .) be a sequence of real numbers. Then, its generating function
a(x) is
a(x) = a0 + a1 x + a2 x2 + . . . .
Theorem 4.3. Let a0 , a1 , . . . be a sequence of real numbers. If |ak | ≤ ck for every k, where c is
a positive real constant, then the series
a0 + a1 x + a2 x2 + . . .
is convergent for all x with |x| < 1c .

Proof. Since |ak | ≤ ck for ever k, we have

∞
X ∞
X ∞
X
k
ak x k
= |ak | |x| ≤ |cx|k .
k=0 k=0 k=0
1
Furthermore |x| < 1c , therefore |cx| < 1 for every k. Next we show 1 + x + x2 + x3 + . . . = 1−x
2 3
for x ∈ (−1, 1): Let s = 1 + x + x + x + . . . + x n−1 2 3 n
, then xs = x + x + x + . . . + r and
 13

1−xn
therefore s − xs = 1 − xn . Thus s = 1−x for x 6= 1. If |x| < 1 the series converges as n goes to
infinity. Therefore, we have
∞
2 3
X 1
1 + x + x + x + ... = xk =
for |x| < 1.
1−x
k=0
P∞ k 1 P∞ k
Since |cx| < 1, we get k=0 |cx| = 1−|cx| . We have shown that k=0 ak x is absolutely
convergent, hence it is convergent. 
4.4. Examples of generating functions. Consider the following two examples.
Example 1. Consider the sequence an = n + 1, n ∈ Z≥0 . Then the generating function is
 
2 d 2 d 1 1
A(x) = 1 + 2x + 3x + . . . = (1 + x + x + . . .) = = .
dx dx 1 − x (1 − x)2
Example 2. Consider the sequence bn = (n + 1)2 , n ∈ Z≥0 . Arguing in a similar way, one gets
d
that the generating function is B(x) = dx A(x) − A(x).
Exercise 2. What is the generating function of the sequence (a0 , a1 , . . .) with ak = 2bk/2c ?
Theorem 4.4. (Generalized binomial theorem). For every r ∈ R and every integer n ≥ 0, let
 
r r(r − 1) · · · (r − n + 1)
= .
n n!
Then, the following holds:
     
r r r r 2
(1 + x) = + x+ x + ···
0 1 2
for every x with |x| < 1.
Proof. Let f (x) = (1 + x)r , then f (n) (0) = r(r − 1)(r − 2) · · · (r − n + 1). Since nr =


r(r−1)(r−2)···(r−n+1) (n)
, we have nr = f n!(0) . For a series a(x) = a0 +a1 x+a2 x2 +. . . the element an


n!
n
is uniquely determined by an = a n!(0) . Therefore (1 + x)r = 0r + 1r x + 2r x2 + . . .
+ nr xn + . . ..

Next we have to show that the series converges for |x| < 1: The series ∞ r n
P
n=0 n x converges
if
r

n+1
n+1 x
lim r


n
< 1.
n x
n→∞

This is the case if

n+1
lim x < 1.
n→∞ n−r
which holds for |x| < 1. 
14

5. Generating functions. Binary trees.

To read: [3] Chapter 12.4.

5.1. Binary trees.

Definition 5.1. An inductive definition of a binary tree can be given as follows: a binary tree
either is empty (it has no vertex), or consists of one distinguished vertex called the root, plus
an ordered pair of binary trees called the left subtree and right subtree.
Let bn denote the number of binary trees with n vertices. Our goal is to find a formula for bn .
Example. By definition we have b0 = 1 and there is one empty tree. We have b1 = 1, b2 = 2,
b3 = 5.

Figure 1. Five different binary trees with three vertices.

The inductive definition of a binary tree implies the following recursive formula for bn :
(3) bn = b0 bn−1 + b1 bn−2 + b2 bn−3 + . . . + bn−1 b0 , n ∈ Z≥1 .
P∞
Let b(x) = n=0 bn x
n be the generating series of the sequence {bn }∞
n=0 . We find

b(x)2 = b20 + (b1 b0 + b0 b1 )x + (b2 b0 + b1 b1 + b0 b2 )x2 + . . .

The recursive relation 3 implies
1 b0 1 1
b(x)2 = b1 + b2 x + b3 x2 + . . . =
(b0 + b1 x + b2 x2 + . . .) − = b(x) − .
x x x x
Therefore, the generating function b(x) satisfies the quadratic equation
xb(x)2 − b(x) + 1.
This equation has two solutions
√ √
1 − 4x
1+ 1 − 1 − 4x
and .
2x 2x
We observe that the first solution is not bounded around x = 0 and the second solution is
smooth around x = 0 tends to 1 as x tends to 0. Consider the second solution
√
eb(x) = 1 − 1 − 4x .
2x
It has Taylor expension around x = 0
∞
X
eb(x) = ebn xn .
n=0

We have computed that eb0 = eb(0) = 1. Moreover, the function eb(x) satisfies the quadratic
equation
x eb(x)2 − eb(x) + 1
 15

and therefore the sequence {ebn }∞n=0 satisfies the recursive relation (3). Since the sequences satisfy
the same initial conditions b0 = eb0 and the same recursive relation (3) we conclude that bn = ebn
for all n ∈ Z≥0 . The generalized binomial theorem implies
∞
√
 
k 1/2
X
1 − 4x = (−4) xk .
k
k=0
−1 n+1 1/2


This implies bn = 2 (−4) n+1 .
Exercise 3. Show that  
1 2n
bn = .
n+1 n
Definition 5.2. The numbers bn are known by the name Catalan numbers.
Exercise 4. Consider an n × n chessboard:
B

A
Consider the shortest paths from the corner A to the corner B following the edges of the squares
(each of them consists of 2n edges).
(a) How many such paths are there?
(b)* Show that the number of paths that never go below the diagonal (the line AB) is exactly
bn , i.e. the Catalan number. One such path is drawn in the figure.
16

6. Fibonacci numbers and linear recurrence relations

6.1. Fibonacci sequence. The Fibonacci sequence (Fn )n≥0 is defined by the following recursive
formula:
F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2 ∀n ≥ 2.
Another way to interpret the Fibonacci sequence is the following: let Sn denote the number
of ways in which one can climb n stairs if allowed to jump one or two stairs at a time. This is the
same as to count the number of the solutions of the equation x1 + . . . + xk = n where xi ∈ {1, 2}
and the number k is not fixed. We observe that S1 = 1, S2 = 2 and Sn+2 = Sn+1 + Sn for all
n ∈ Z≥1 . Therefore, we have Sn = Fn+1 .
Identities for Fibonacci numbers. The sum of the first n numbers of the Fibonacci sequence,
is
X n
Fk = Fn+2 − 1.
k=0
Exercise 5. Prove the following identities for Fibonacci numbers:
(a) F1 + F3 + F5 . . . + F2n−1 = F2n
(b) F2n+1 = 3F2n−1 − F2n−3
(c)∗ Fa+b+1 = Fa+1 Fb+1 + Fa Fb .
Explicit formula for Fibonacci numbers. We want to find an explicit formula for the value
of the n-th Fibonacci number. We will present several possible ways to do that.
Method 1.
We will use the generating functions. Let F (x) denote the generating function of the Fibonacci
sequence (F0 , F1 , . . .) that is
F (x) = F0 + F1 x + F2 x2 + F3 x3 + . . . .
Note that the convergence radius of this series is at least 12 . Multiplying F (x) by x, respectively
x2 , we obtain that
xF (x) = F0 x + F1 x2 + F2 x3 + F3 x4 + . . .
x2 F (x) = F0 x2 + F1 x3 + F2 x4 + F3 x5 + . . . .
Recall that for every n ≥ 2, we have Fn = Fn−1 + Fn−2 and consider F (x) − xF (x) − x2 F (x).
Grouping together the coefficients of xk for every k, one obtains that
F (x) − xF (x) − x2 F (x) =
= F0 + x(F1 − F0 ) + x2 (F2 − F1 − F0 ) + x3 (F3 − F2 − F1 ) + . . . + xk (Fk − Fk−1 − Fk−2 ) + . . . .
This implies F (x) − xF (x) − x2 F (x) = x and thus
x
F (x) =
1 − x − x2
This means, the general term is
F (n) (0)
Fn =
n!
where F (0) is the value in 0√ of the n-th derivative of F (x). We factor 1 − x − x2 as −(x −
(n)

x1 )(x − x2 ), where x1,2 = −1±2 5 This means

x A B A(x − x2 ) + B(x − x1 )
F (x) = 2
= + =
1−x−x x − x1 x − x2 −(1 − x − x2 )
 17

From this we obtain that

A + B = −1 and Ax2 + Bx1 = 0.

This is a system of two equations with A and B as unknowns, so we can obtain exact values for
A and B:
x1 −x2
A= √ B= √ .
5 5
One can obtain that:
A B A 1 B 1
F (x) = + =− x − =
x − x1 x − x2 x 1 1 − x1 x2 1 − xx2
∞ ∞
A X −n n B X −n n
=− x1 x − x2 x
x1 x2
n=0 n=0
∞ ∞
1 X −n n 1 X −n n
=√ x1 x − √ x2 x .
5 n=0 5 n=0
∞
X 1
√ x−n −n

n
= 1 − x2 x .
n=0
5

This implies that the general term Fn is

√ !n √ !n !
1 1+ 5 1− 5
Fn = √ − .
5 2 2

Method 2.
We look first for a geometric series that satisfies An = An−1 + An−2 , that is An = c · αn for all
n ∈ Z≥0 . This implies that√cαn = cαn−1 + cαn−2 and thus α2 − α − 1 = 0. Solving this quadratic
equation, we get α1,2 = 1±2 5 . Next, we search for Fn in the form
√ !n √ !n
1 + 5 1 − 5
Fn = c1 α1n + c2 α2n = c1 + c2
2 2

for some c1 , c2 ∈ R. The initial conditions imply

F0 =c1 + c2 = 0
√ ! √ !
1+ 5 1− 5
F1 =c1 + c2 = 1.
2 2

Thus, the only solution is

1 −1
c1 = c2 = .
5 5
Hence we find
√ !n √ !n !
1 1+ 5 1− 5
Fn = √ − .
5 2 2
18

6.2. Linear recurrence relations. In general, to solve linear recurrence relations of the form
an+k = ck−1 an+k−1 + . . . + c0 an
we have the following recipe. Denote by λ1 , . . . λs the (possibly complex) roots of the equation
λk = ck−1 λk−1 + . . . + c0
where λi has multiplicity ki and si=1 ki = k.
P

Theorem [Link] formula for an is the solutions to the recurrence above if and only if it has
the form an = si=1 Pi (n)λni , where each Pi (n) is a polynomial of degree ki − 1 with coefficients
chosen arbitrarily. Moreover, for any set of initial values a0 , . . . , ak−1 one can find coefficients
of the polynomials Pi (n) so that the solution fits to the initial values. Note that the number of
coefficients to be determined is equal to k, the number of initial values.
 19

7. Möbius invertion formula

To read:
[5] Chapter 2.1.
Definition 7.1. Suppose that a positive integer n has the prime factorization
n = pe11 · · · perr .
We define the Möbius function µ(n) as:

1 for n = 1,

µ(n) = 0 if some ei > 1,
(−1)r if e1 = . . . = er = 1.



Lemma 7.2. For n ∈ Z≥1 we have

(
X 1 if n = 1,
µ(d) =
0 if n > 1.
d|n

Here the summation is taken over all positive divisors on n.

Proof. First consider the case n = 1. It follows immediately from the definition
X
µ(d) = µ(1) = 1.
d|1

Next, suppose that n > 1 and it has the prime decomposition n = pe11 · · · perr . Set n∗ := p1 · · · pr .
If d | n and d - n∗ then d has a prime divisor of multiplicity bigger then 1 and therefore µ(d) = 0.
Hence, we have X X
µ(d) = µ(d).
d|n d|n∗
Now we can easily compute
     
X r r r
µ(d) = 1 − + − + . . . = (1 − 1)r = 0.
∗
1 2 3
d|n

This finishes the proof. 

Theorem 7.3. (Möbius inversion formula) Let functions f, g : Z≥1 → R be such that
X
f (n) = g(d).
d|n

Then X
g(n) = µ(d) f (n/d).
d|n

Proof. We have X
f (n/d) = for all d | n.
d0 |(n/d)g(d0 )
Therefore X X X
µ(d) f (n/d) = µ(d) g(d0 ).
d|n d|n d0 |(n/d)
20

Let n = dd0 n1 . For a fixed d0 , the value of d runs over all positive divisors of n/d0 . Hence we get
X X X X
µ(d) g(d0 ) = g(d0 ) µ(d).
d|n d0 |(n/d) d0 |n d|(n/d0 )
P
We apply the previous lemma to the sum d|(n/d0 ) µ(d) and obtain
X X
g(d0 ) µ(d) = g(n).
d0 |n d|(n/d0 )

This finishes the proof. 

7.1. Identities with Euler’s totient function.
Exercise 6. Show that for all n ∈ Z≥1 we have
X
n= φ(d).
d|n

Hint: Let Φn be the set all elements in [n] coprime to n:

Φn := {m ∈ [n] | m is coprime to n}.
Show that [n] is the disjoint union of sets (n/d) · Φd where d runs over all divisors of n:
[˙
[n] = (n/d) · Φd .
d|n
P µ(d)
Exercise 7. Show that φ(n) = n d|n d .
7.2. Number of cyclic sequences.
Definition 7.4. Let A be a set. A linear sequence of length n on an A is a sequence of the form
(a1 , . . . , an ), ak ∈ A for k = 1, . . . n.
In other words, a linear sequence is a function a : [n] → A.
The number of linear sequences of length n on an alphabet of size r is rn .
Consider the following equivalence relation ∼ on the set of linear sequences:
(a1 , ..., an ) ∼ (a1 , ..., an )
and
(a1 , ..., an ) ∼ (ak , ak+1 , . . . , a1 , . . . , ak−1 ), k = 2, . . . n.
In other words, two linear sequences are equivalent if one of them can be obtained from another
by a cyclic shift.
Example. Linear sequences of length 3 on the alphabet {a, b}:
(a, a, a)
(a, a, b)
(a, b, a)
(a, b, b)
(b, a, a)
(b, a, b)
(b, b, a)
(b, b, b).
 21

Cyclic sequences of length 3 on the alphabet {a, b}:

(a, a, a)
(a, a, b) ∼ (a, b, a) ∼ (b, a, a)
(a, b, b) ∼ (b, b, a) ∼ (b, a, b)
(b, b, b).
Definition 7.5. A cyclic sequence of length n on an alphabet A is an equivalence class of linear
sequences with respect to the relation ∼.
Proposition 7.6. The number T (n, r) of cyclic sequences of of length n on an alphabet of size
r is
1X
T (n, r) = φ(n/d)rd .
n
d|n

Proof. A period of a cyclic sequence (a1 , . . . , an ) is a minimal number k ∈ {1, 2, . . . , n} such that
(a1 , . . . , an ) = (a1+k , . . . , an , a1 , . . . ak ) (equal as linear sequences). Note that the period of a
sequence is a divisor of the the sequence’s length.
Let M (d, r) be the number of cyclic sequences of of length d and period exactly d. It is easy
to see that X
rn = d M (d, r).
d|n
The Möbius inversion formula implies
X
(4) n M (n, r) = µ(n/d) rd .
d|n

We have X
T (n, r) = M (d, r).
d|n
We combine this identity with (4) and obtain
X1X 0
T (n, r) = µ(d0 /d) rd
d 0
d|n d |d
d
(here we intoduce a new summation variable d00 = 0 )
  d
X 0 X 1
= rd  0 d00
µ(d00 ) .
0 00 n
d
d |n d | d0

Now we use the identity

X 1
00 φ(n/d0 )
µ(d ) =
00 n
d00 n/d0
d | d0
and arrive at
X 0 1 φ(n/d0 )
T (n, r) = rd
d0 n/d0
d0 |n
1X 0
= φ(n/d0 ) rd .
n 0
d |n
22

This finishes the proof. 

 23

7.3. Partially ordered sets (or posets). This section is written by Dr. Matthew de Courcy-
Ireland.
Definition 7.7. A binary relation on a set A is a subset R ⊆ A × A. A relation is reflexive
provided that (x, x) ∈ R for every x ∈ A. A relation is antisymmetric provided that (a, b) ∈ R
and (b, a) ∈ R together imply a = b. A relation is transitive if (a, b) ∈ R and (b, c) ∈ R together
imply (a, c) ∈ R. A relation is reflexive if (a, a) ∈ R for all a ∈ R.
Definition 7.8. (partial order) A partial order on a set A is an antisymmetric, reflexive, and
transitive relation R ⊆ A × A. A partially ordered set, or poset for short, is a set together with
a partial order.
Example. The subsets of a given set A are partially ordered by inclusion.

1234
123 124 134 234

12 13 23 14 24 34

1 2 3 4
∅

7.4. Hasse diagram. The Hasse diagram is a useful way to draw partially ordered sets. Es-
sentially, we draw a point for each element of the poset, and a line from x to y when x < y. But
many of these lines are redundant, in view of transitivity:
x < y < z =⇒ x < z
So we need only draw a line when x < y and there is no element in between. By convention, we
draw x lower than y.
Example. Let X be the factors of 12, ordered by divisibility. The Hasse diagram is then
12
4 6
2 3
1

7.5. Möbius invertion for posets. Given a function f defined on a partially ordered set
(X, ≤), we may form the sum X
g(x) = f (y)
y≤x
assuming that f is real-valued, or at least that there is some way to add the values f (y). To
guarantee that the sum is well-defined, we assume that there are only finitely many terms y
beneath any given x. For instance, this holds if X is finite. How do we recover f from g?
24

Theorem 7.9. (Möbius inversion for posets) Given a partially ordered set X, there is a two-
variable function M : X × X → R such that
X X
g(x) = f (y) ⇐⇒ f (x) = g(y)M (y, x)
y≤x y≤x

This function M is called the Möbius function of the poset. To show it exists for any partial
order, and to compute it for specific orders, we introduce an algebraic structure that captures
the order relation.
Definition 7.10. (incidence algebra) Given a partially ordered set X, the incidence algebra
A(X) is the set of all real-valued functions f : X 2 → R satisfying f (x, y) = 0 unless x ≤ y.
More generally, for any abelian group G, we define AG (X) as the set of all G-valued functions
f : X 2 → G satisfying f (x, y) = 0 unless x ≤ y, where 0 now denotes the identity element of G.
The elements of AG (X) are called incidence functions, or G-valued incidence functions.
If G is a field, in particular for G = R, then AG (X) is a vector space over G with respect to
pointwise addition and scalar multiplication. The extra structure that makes it an “algebra” is
the following operation.
Definition 7.11. (convolution) Given f, g ∈ A(X), their convolution f ∗ g is defined by f ∗
g(x, y) = 0 unless x ≤ y, in which case
X
f ∗ g(x, y) = f (x, z)g(z, y)
x≤z≤y

The sum is well-defined assuming that there are finitely many z in between x and y, which is
certainly the case for finite posets and also holds for many natural infinite ones. By construction,
f ∗ g is again in A(X).
Definition 7.12. (locally finite) A poset X is called locally finite provided that for any elements
x, y, there are only finitely many z ∈ X in the interval x ≤ z ≤ y.
Example. The rational numbers, in their usual order, do not form a locally finite poset. The
interval 0 < z < 1 contains infinitely many elements 1/n for n = 1, 2, 3, . . .
To define convolution for G-valued functions, there must be some notion of multiplication as
well as addition. Thus the same concept applies for any ring instead of R.
Example. If X = {1, . . . , n} with the usual order 1 < . . . < n, then a two-variable function
f (x, y) is just an n × n matrix, and the incidence condition f (x, y) = 0 unless x ≤ y says that
this is a triangular matrix. Convolution is the usual notion of matrix multiplication.
In particular, the example of matrix multiplication shows that convolution is not always
commutative.
Example. (delta function) Returning to a more general poset, the analogue of the identity matrix
is (
1 if x = y
δ(x, y) =
0 if not
Clearly δ(x, y) unless x ≤ y, indeed unless x = y. Thus δ is an incidence function. For any
incidence function f ,
δ∗f =f ∗δ =f
 25

because there is one non-zero term f (x, z)δ(z, y) in the interval x ≤ z ≤ y, namely z = y. So
the sum defining f ∗ δ(x, y) is just f (x, y). Similarly, for δ ∗ f (x, y) we have only a single term
f (x, y) when z = x.
Proposition 7.13. Convolution is associative: for any incidence functions f, g, h on a (locally
finite) poset X
(f ∗ g) ∗ h = f ∗ (g ∗ h)
Sketch of proof. For any x ≤ y, both sides (f ∗ g) ∗ h(x, y) and f ∗ (g ∗ h)(x, y) are given by the
sum of f (x, z)g(z, w)h(w, y) over all z and w between x and y and satisfying z ≤ w. 
Proposition 7.14. (convolution inverses) Let X be a (locally) finite poset. An incidence func-
tion f (x, y) has an inverse g satisfying f ∗ g = δ if and only if f (x, x) 6= 0 for all x. In that
case, the inverse works on both sides: f ∗ g = g ∗ f = δ.
Proof. Suppose there is an inverse. Then, for any x,
f ∗ g(x, x) = δ(x, x) = 1
On the other hand, there is only one term f (x, x)g(x, x) in the sum over x ≤ z ≤ x defining
f ∗ g(x, x), namely z = x (a partial order is antisymmetric!). If f (x, x)g(x, x) = 1, then
f (x, x) 6= 0 or else the product would be 0.
Conversely, suppose f (x, x) 6= 0 for all x. We define g(x, y) inductively. Note that there are
only finitely many z in the interval x ≤ z ≤ y. For x = y, define g(x, x) = 1/f (x, x). Then the
required identity holds in the form g(x, x)f (x, x) = 1 = δ(x, x) because the sum over x ≤ z ≤ y
is just a single term in this case where x = y (this uses the fact that ≤ is antisymmetric to go
from x ≤ z ≤ x to z = x). If x 6= y, we assume inductively that g(x, z) has already been defined
for z < y, and then define
 
1  X
g(x, y) = − g(x, z)f (z, y)
f (y, y)
x≤z<y

By construction, g ∗ f (x, y) = 0 = δ(x, y) since multiplying through gives the missing term
g(x, y)f (y, y) corresponding to z = y in the sum. One can construct g 0 satisfying f ∗ g 0 = δ
by a similar induction, and it must be that g = g 0 because ∗ is associative. Indeed, start from
f ∗ g 0 = δ and multiply on the left by g. We obtain g ∗ (f ∗ g 0 ) = g ∗ δ = g because δ is the
neutral element. But by associativity, the other side is
g ∗ (f ∗ g 0 ) = (g ∗ f ) ∗ g 0 = δ ∗ g 0 = g 0
appealing once again to the neutrality of δ. It follows that g = g 0 . 
Definition 7.15. The zeta function of a poset is defined by
(
1 if x ≤ y
Z(x, y) =
0 if not
Since Z(x, x) = 1 6= 0 for every x, the Proposition 7.14 implies that there is an incidence function
M satisfying
M ∗Z =Z ∗M =δ
This M is called the Möbius function of the poset. From the construction of inverses, we have
M (x, x) = 1 for every x and, for x < y,
X
M (x, y) = − M (x, z)
x≤z<y
26

Now we can prove Theorem 7.9. The required function M is exactly the Möbius function of
the poset. Recall what we have to show:
X X
g(x) = f (y) ⇐⇒ f (x) = g(y)M (y, x)
y≤x y≤x

Define a new poset X0 by adding a new element less than everything in X. In other words, let
−∞ be anything not already in X and extend the order by −∞ < x for all x ∈ X. For any
function f on X, there is a corresponding incidence function f 0 on X 0 defined by
f 0 (−∞, x) = f (x), f 0 (x, y) = 0 for all x, y ∈ X
The zeta and Möbius functions of X 0 extend those of X by
Z(−∞, y) = 1 for all y ∈ X 0
so we use the same symbols Z and M rather than Z 0 and M 0 .
Because Z and M are convolution inverses,
g 0 = f 0 ∗ Z ⇐⇒ f 0 = g 0 ∗ M
In particular, evaluated at the pair (−∞, x), the quantity on the left is
X X
g(x) = g 0 (−∞, x) = f 0 (−∞, y)Z(y, x) = f (x)
−∞≤y≤x y≤x
while the quantity on the right is
X X
f (x) = f 0 (−∞, x) = g 0 (−∞, y)M (y, x) = g(y)M (y, x)
−∞≤y≤x y≤x
We obtain Theorem 7.9 as originally stated. 
Exercise 8. The set Z≥0 is partially ordered by the usual ≤ relation. Compute the Möbius
function of this poset.
 27

8. Elements of graph theory

To read:
[1] 8.1. How to Define Trees?,
[3] 4.1. The notion of a graph; isomorphism - only the definition of graphs, 4.3.1. Sum of the
degrees, 4.3.2. Handshakes lemma, 5.1.

8.1. Definition and characterizations of trees.

Definition 8.1. A graph G is an ordered pair (V, E), where V is a set of elements called vertices
and E is a set of 2-element subsets of V called edges.
Definition 8.2. Let G = (V, E) be a graph. We call a sequence of distinct vertices v0 , . . . , vr a
path if {vi , vi+1 } is an edge of G, for every 0 ≤ i ≤ r − 1.
Definition 8.3. We say that a graph G = (V, E) is connected if for every two vertices u, v ∈ V
there exists a path in G between u and v.
Definition 8.4. For every vertex of a graph, we define its degree as the number of edges adjacent
to it.
Definition 8.5. A cycle in a graph G = (V, E) is a sequence of distinct vertices v1 , . . . , vr ∈ V
with r ≥ 3 such that {vi , vi+1 } ∈ E for all i from 1 to r − 1 and moreover {vr , v1 } ∈ E.
Definition 8.6. A tree is a connected graph without cycles.
Definition 8.7. A vertex of degree one in a tree is called a leaf.
Lemma 8.8. Every tree on n ≥ 2 vertices has at least two leaves.
Proof. Let S be the set of all the paths in the tree T . We know that every path on r vertices
contains exactly r − 1 edges. Consider now a path v1 , . . . , vl of maximum length. One can
always find a path of maximum length since every path in the tree can contain at most n
vertices (otherwise it will be self-intersecting, that is it will contain a cycle, which is impossible
since in a tree we cannot have cycles). We prove that both v1 and vl (the endpoints of the
path) are leafs. Assume at least one of them is not, say v1 . That means that, there is at least
another edge apart from {v1 , v2 } incident to v1 . Observe that u cannot coincide with any of the
vertices of the path v1 , . . . , vl (otherwise it will close a cycle). Therefore, we can add u to the
path without forming any cycle. But this is a contradiction to the maximality of the length of
the path v1 , . . . , vl . Thus, both v1 and vl must be leaves. 
Theorem 8.9. Every tree on n vertices has exactly n − 1 edges.
28

9. Equivalent definitions of a tree, number of labeled trees

To read:
[1] 8.3. How to Count trees? 8.4. How to Store trees?
[3] 4.1 The notion of a graph; isomorphism 5.1 Definition and characterizations of trees 8.1. The
number of spanning trees, 8.4. A proof using the Prüfer codes.

9.1. Graph isomorphisms.

Definition 9.1. Two graphs G = (V, E) and G0 = (V 0 , E 0 ) are called isomorphic if a bijection
f : V → V 0 exists such that {x, y} ∈ E if and only if {f (x), f (y)} ∈ E 0 holds for all x, y ∈ V ,
x 6= y. Such an f is called an isomorphism of the graphs G and G0 . The fact that G and G0 are
isomorphic is written G ∼ = G0 .
9.2. Characterizations of trees.
Theorem 9.2. The following five properties are equivalent:
(1) T is a tree.
(2) T is maximally acyclic, that is, it is acyclic, but if we add any edge to T , then it will
contain a cycle.
(3) Any two vertices in T are connected by a unique path.
(4) T has one edge less than the number of vertices and it is connected.
(5) T has one edge less than the number of vertices and it is acyclic.
9.3. Counting labeled trees. In what follows, we will present a result due to Cayley. Before
stating the theorem, we need the following lemma:
Lemma 9.3. Let T be a tree on n labeled vertices and let d1 , . . . , dn be the degrees of the vertices.
Then
Xn
di = 2|E(T )| = 2(n − 1)
i=1
where by E(T ) denotes the edge set of the tree.
Now we can state Cayley’s theorem.
Theorem 9.4. (Cayley). The number of trees on n labeled vertices is nn−2 .
We give two proofs to this theorem. The first one, due to Prüfer, is algorithmic.
Proof 1 of Cayley’s theorem. We give now the proof, due to Prüfer. Denote the vertices by
{1, 2, . . . , n}. We will define a one-to-one correspondence between the set of all trees on n la-
beled vertices and the set of all sequences of length n − 2 consisting of numbers in {1, 2, . . . , n}.
Since the cardinality of the latter is nn−2 , we obtain the desired result. The following algorithm
takes a tree as input, and yields a sequence of integers:

Step 1: Find the leaf with the smallest label and write down the number of its neighbor.
Step 2: Delete this leaf, together with the only edge adjacent to it.
Step 3: Repeat until we are left with only two vertices.
We present an algorithm that reconstructs the tree from the Prüfer code.
Step 1: Draw the n nodes, and label them from 1 to n.
Step 2: Make a list of all the integers (1, 2, . . . , n). This will be called the list.
 29

Step 3: If there are two numbers left in the list, connect them with an edge and then stop.
Otherwise, continue on to step 4.
Step 4: Find the smallest number in the list which is not in the sequence. Take the first number
in the sequence. Add an edge connecting the nodes whose labels correspond to those
numbers.
Step 5: Delete the smallest number from the list which is not in the sequence and the first
number in the sequence. This gives a smaller list and a shorter sequence. Then return
to step 3.
9.4. Counting unlabeled trees. The number of unlabeled trees, that is, classes of pairwise
nonisomorphic trees is only exponential in the number of vertices. We prove the following
theorem:
Theorem 9.5. The number of pairwise nonisomorphic trees on n vertices is at most 22n−4 .
Here is a sketch of a proof: The proof uses the following encoding of trees. We think of a
tree hanged from one of its vertices on a plane (we think of gravity working in the negative
y-direction). We go around the tree and form a binary sequence. If we are going one edge down,
we write 1 in the sequence. If we are going up - we write 0. At the end we corresponded one 0
and one 1 to each edge, which gives us a binary sequence of length 2n − 2. The last bit is always
0, and the first bit is always 1, so the total number of these sequences is at most 22n−4 . 
nn−2
Theorem 9.6. The number of pairwise nonisomorphic trees on n vertices is at least n! .
30

10. Kruskal’s algorithm for finding a minimal spanning tree

To read:
[1] 9.1. Finding the best tree
[3] 5.4. Minimum spanning tree problem

10.1. Subgraphs, induced subgraphs, and spanning trees.

Definition 10.1. Let G and G0 be graphs. We say that G is a subgraph of G0 if V (G) ⊂ V (G0 )
and E(G) ⊆ E(G0 ). We say that G is an induced subgraph of G0 if V (G) ⊆ V (G0 ) and
E(G) = E(G0 ) ∩ V (G)


2 .
Definition 10.2. Let G = (V, E) be a graph. We say that a tree T is a spanning tree of G if it
contains all the vertices of V and is a subgraph of G, that is every edge in the tree belongs to
the graph G.
Example. Below is an example of a spanning tree:

10.2. Weighted graphs.

Definition 10.3. A weighted graph is a graph in which each edge is given a numerical weight.
We define the weight of a graph as the sum of the weights of all its edges.
We are interested in the following problem: find a minimum weight spanning tree T for a
given weighted connected graph G.
Example. A minimum weight spanning tree in a weighted connected graph.
9 4

7
2
3 5
8 1

One way to solve the problem of finding a minimum spanning tree is using Kruskal’s algorithm.
This works as follows:
Step 1. Start with an empty graph.
Step 2. Take all the edges that have not been selected and that would not create a cycle with
the already selected edges and select it unless it creates a cycle. Add the one with the
smallest weight.
Step 3. Repeat until the graph is connected.
 31

Theorem 10.4. (Correctness of Kruskal’s algorithm). The Kruskal’s algorithm solves

the minimum spanning tree problem.
Proof. The proof can be found in [1] Chapter 9.1. 
32

11. Counting spanning trees in a graph. Kirchhoff’s theorem

11.1. A useful fact form linear algebra.
Theorem 11.1. (Binet–Cauchy theorem). Let A be an arbitrary matrix with n rows and m
columns. Then X
det(A AT ) = det(A[I])2 ,
I
where the sum is over all n-element subsets I ⊆ {1, 2, ..., m}, and where A[I] denotes the matrix
obtained from A by deleting all columns whose indices do not lie in I.
11.2. Laplace matrix and incidence matrix.
Definition 11.2. Let G = (V, E) be a graph. An orientation o on G is the choice of the ordered
pair (u, v) or (v, u) for each edge {u, v} ∈ E. (If we choose (u, v), say,then we think of putting
an arrow one pointing from u to v, and we say that {u, v} is directed from u to v ,that u is the
initial vertex and v the final vertex of {u, v}).
Definition 11.3. Let G = (V, E) be a graph and o be an orientation on G. The incidence
matrix of G with respect to o) is the matrix I(G, o) ∈ M|V |×|E| (Z), where the its entries Iv,e for
v ∈ V , e ∈ E are given by

1,
 if the edge e has initial vertex v ,
Iv,e = −1, if the edge e has initial vertex v ,

0, otherwise.


Definition 11.4. The Laplace matrix of G is the matrix L(G) ∈ M|V |×|V | (Z), where the its
entries Lu,v for u, v ∈ V are given by

deg(u), if u = v,

Lu,v = −1, if u 6= v and {u, v} is an edge,

0, otherwise.


11.3. Kirchhoff ’s theorem.

Theorem 11.5. (Kirchhoff ) Let G be a finite connected graph with Laplace matrix L = L(G).
Let L0 denote L with the last row and column removed. Then the number of spanning trees κ(G)
satisfies κ(G) = det(L0 ).
Proof. The proof can be found in [3] Section 8.5. 
Exercise 9. Suppose that a connected graph G has n vertices. Show that
1
κ(G) = λ1 · · · λn−1 ,
n
where λ1 , . . . , λn are the eigenvalues of L(G) and λn = 0.
 33

12. The probabilistic method.

12.1. Finite probability spaces. We denote by Ω a probability space, that is, the set consist-
ing of some elements called elementary events equipped with a measure p such that
(1) p(A) ≥ 0 for any event (by event we mean any union of some elementary events)
(2) p(Ω) = 1.
(3) p(A ∪ B) = p(A) + p(B) for any disjoint events A, B.
For simplicity of exposition we work only with discrete probability here, that is, we assume
that Ω is finite. A random variable X : Ω → R is just any measurable function that assigns values
to elementary events. Note that the measure p does not appear in this definition. However, it
appears in the next one. If X takes values x1 , . . . xk , then the expectation E(X) of X is defined
as
Xk
E(X) = xi p(X = xi ).
i=1
Pk
Note that i=1 p(X = xi ) = 1. Informally, it is a weighted average of X with respect to p.
Some useful properties:
a) The probability of a union of events A1 , . . . , An is at most the sum of the probabilities
of the events
p(A1 ∪ · · · ∪ An ) ≤ p(A1 ) + . . . + p(An ).
b) If A1 , . . . , An are independent events, then

p(A1 ∩ · · · ∩ An ) = p(A1 ) · · · p(An ).

c) The linearity of expectation: If X1 , · · · , Xn are random variables and a1 , . . . , an an are

real numbers, then

E(a1 X1 + . . . + an Xn ) = a1 E[X1 ]+ ::: +an E[Xn ].

d) If E(X) = m, then there is at least one elementary event A1 such that X(A1 ) ≥ m, and,
analogously, there is at least one elementary event A2 such that X(A2 ) ≤ m.
A general framework for the probabilistic method is the following: we are given a finite set of
objects Ω and X : Ω → R is a function assigning to each object A ∈ Ω a real number. The goal
is to show that there is at least one element A ∈ Ω for which X(A) is at least a given value m.
For this, we define a probability distribution p : Ω → [0, 1] and consider the resulting probability
space, where X becomes a random variable. Showing that the expected value of X is at least m
is enough, since, if this holds, then there exists at least one event A ∈ Ω for which X(A) ≥ m.

12.2. Applications of probabilistic method.

12.2.1. Existence of large bipartite subgraphs.

Theorem 12.1. Let G be a graph with an even number, 2n, of vertices and with m > 0 edges.
Then the set V = V (G) can be divided into two disjoint n-element subsets A and B in such a
way that more than m/2 edges go between A and B.

Proof. The proof can be found in [3] page 307. 

34

12.2.2. Turán’s theorem.

Definition 12.2. Let G = (V, E) be a graph. An independent set is a set of vertices S ⊆ V
such that no two of them are connected by an edge.
Theorem 12.3. (Turán) For any graph G on n vertices, we have
n2
α(G) ≥ ,
2|E(G)| + n
where α(G) denotes the size of the largest independent set of vertices in the graph G.
Proof. The proof can be found in [3] pages 308–309. 
Exercise 10. Consider the disjoint union of m copies of the complete graph Kr . Show that
this graph attains the bound of Theorem 12.3.
12.2.3. Schütte’s problem. (Not covered in the course)
Definition 12.4. A tournament is a directed graph obtained by assigning a direction for each
edge in an undirected complete graph. In a tournament, every pair of distinct vertices is con-
nected by a single directed edge.
Definition 12.5. We say that a tournament T = (V, E) has property Sk if for any k vertices
v1 , . . . , vk ∈ V there exist a vertex u ∈ V (T ) such that −→, . . . , −
uv1
→ ∈ E.
uvk

Schütte’s problem can be formulated as follows: do such tournaments exist, for every k fixed?
The answer is given by the following theorem:
Theorem 12.6. For every integers k ≥ 1 and n ≥ k 2 2k (ln(2) + o(1)), there exist a tournament
on n vertices having property Sk .
Proof. The proof can be found in [4], pages 44–45 or [3] pages 299–300.
 35

13. Bipartite graphs. König-Hall theorem. Sperner theorem

This material was not covered in the course. To read:
[1] 10.3. The Main Theorem
[3] 7.2. Sperner’s theorem on independent systems: Sperner theorem and proof of Theorem 7.2.1.
Definition 13.1. A bipartite graph (or bigraph) is a graph G whose vertices can be divided into
two disjoint sets A and B such that every edge of the graph connects a vertex in A to one in B
(in other words, there is no edge of the graph between two vertices of A or two vertices of B.
Lemma 13.2. A graph is bipartite if, and only if, it does not contain an odd cycle (that is, a
cycle of odd length).
Definition 13.3. Let G = (V, E) be a graph. A subset E0 ⊂ E of pairwise disjoint edges (that
is, edges which do not share any vertex) is called a matching in G.
Definition 13.4. A perfect matching is a matching where every vertex of the graph is incident
to exactly one edge of the matching.
Remark. A perfect matching is therefore a matching of a graph containing n/2 edges (where n
is the number of vertices). Thus, perfect matchings are only possible on graphs with an even
number of vertices!
Theorem 13.5. (König-Hall). Let G = (V, E) be a bipartite graph with bipartition V = A ∪ B
such that |A| = |B|. For every X ⊂ A, let
B(X) := {b ∈ B | there exists x ∈ X such that (b, x) ∈ E}.
Then, a perfect matching in the graph exists if and only if |B(X)| ≥ |X|, for all X ⊂ A.
Proof. You can find the proof in [1], chapter 10.3. The Main Theorem or [4], page 83. 
Theorem 13.6. (Sperner). Let X = {1, 2, . . . , n} and A1 , . . . , Am ⊆ X, with Aj 6⊆ Ai , for all
n


i 6= j. Then m ≤ bn/2c .
Proof. Two proofs of Sperner’s theorem (one of them using LYM inequality) can be found in
[3], pages 227–229. 
36

Acknowledgements: I thank Prof. Janos Pach for designing this course and Dr. Matthew de
Courcy-Ireland for sharing his lecture notes.

References
[1] Discrete Mathematics (L. Lovasz, J. Pelikan , K. Vesztergombi);
[2] Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability (B. Bollobas);
[3] Invitation to Discrete Mathematics (J. Matousek, J. Nesetril).
[4] Extremal combinatorics (S. Jukna).
[5] Combinatorial theory (M. Hall), Blaisdell publishing company, 1967.