MATH 239/249 Introduction to Combinatorics
Introduction to Combinatorics
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH 239/249
Introduction to Combinatorics
Hello World, and Thanks!
The following parts of these notes are still UNDER CONSTRUCTION.
(Estimated completion date: Fall 2021.) Most of these are additional topics
not covered during the semester. The old notes are also available on the
course website.
• Proof of Theorem 4.18 (inhomogeneous linear recurrence relations)
• Section 8.4 (planar duality)
• Part III: Chapters 12, 13, and 14 will appear in three installments over
the course of the next year.
Department of Combinatorics and Optimization
Preliminaries.
MATH 239 is an introduction to two of the main areas in combinatorics –
enumeration and graph theory. MATH 249 is an advanced version of MATH
239 intended for very strong students. These courses are designed for stu-
dents in the second year of an undergraduate program in mathematics or
computer science.
The prerequisites required from first-year mathematics are as follows.
• From MATH 135. Abstract algebra I: sets and propositional logic, proofs,
mathematical induction, modular arithmetic, complex numbers, the
Fundamental Theorem of Algebra.
• From MATH 136. Linear algebra I: systems of linear equations, Gaus-
sian elimination, matrix algebra, vector spaces.
• From MATH 137. Calculus I: algebra with power series, open/closed
sets, continuous functions, differentiation (but not integration).
We use the following standard notation for various number systems.
natural numbers N = {0, 1, 2, 3, ...} including zero 0
integers Z = {...,−2,−1, 0, 1, 2, ...}
rational numbers Q
real numbers R
complex numbers C
integers (modulo n) Zn = {[0], [1], [2], ..., [n− 1]}
finite field of prime size Fp = Zp
The cardinality (size) of a set S is denoted by |S|.
For convenience, we use LHS and RHS as shorthand for “left-hand side”
and “right-hand side”, respectively.
9
Part I
Introduction to Enumeration
11
Overview.
Suppose I pay $5 for a lottery ticket – what is the chance that I win a share
of the top prize? It depends on the details, of course. There are a certain
number of ways to win, and a certain number of ways to lose. Enumeration
is the art and science of figuring out this kind of thing. This is the subject of
the first part of these course notes.
There are two broad principles of the subject. The combinatorial ap-
proach is to construct explicit one-to-one correspondences between sets to
show that they have the same size. The algebraic approach is to translate the
information about the problem from combinatorics into algebra, and then to
use algebraic techniques to determine the sizes of the sets. We will see many
examples of both approaches.
In Chapter 1 we begin by introducing the basic building blocks of the the-
ory: subsets, lists and permutations, multisets, binomial coefficients, and so
on. In Section 1.2 the use of these objects is illustrated by analyzing various
applications and examples.
In Chapter 2 we introduce the idea of generating series. This begins with
the Binomial Theorem and Binomial Series, which are of fundamental im-
portance for later results. The general theory of generating series is devel-
oped in Section 2.2, and its use is illustrated by analyzing “compositions”
in Section 2.3.
In Chapter 3 we consider the enumeration of various sets of binary strings,
namely those which can be described by regular expressions – the “rational
languages”. This provides an interesting and varied class of examples to
which the results of Chapters 2 and 4 apply.
In Chapter 4 we consider sequences which satisfy a homogeneous linear
recurrence relation with initial conditions, the sequences arising in Chapters
13
2 and 3 being examples. This technique allows us to calculate the numbers
which answer the various counting problems we have been considering.
By using Partial Fractions we can derive an even better solution to such
problems, although the calculations involved are also more complicated.
(We include a proof of Partial Fractions for completeness.) In Section 4.4 we
briefly discuss recurrence relations which are quadratic rather than linear.
Two additional topics are discussed in Chapters 11 and 12.
Chapter 1
Basic Principles of Enumeration.
1.1 The Essential Ideas.
1.1.1 Choices – “AND” versus “OR”.
In the next few pages we will often be constructing an object of some kind
by repeatedly making a sequence of choices. In order to count the total
number of objects we could construct we must know how many choices are
available at each step, but we must know more: we also need to know how to
combine these numbers correctly. A generally good guideline is to look for
the words “AND” and “OR” in the description of the sequence of choices
available. Here are a few simple examples.
Example 1.1. On a table before you are 7 apples, 8 oranges, and 5 ba-
nanas.
• Choose an apple and a banana.
There are 7 choices for an apple AND 5 choices for a banana: 7×5 =
35 choices in all.
• Choose an apple or an orange.
There are 7 choices for an apple OR 8 choices for an orange: 7+8 =
15 choices in all.
• Choose an apple and either an orange or a banana.
There are 7× (8 + 5) = 91 possible choices.
15
16 Basic Principles. Section 1.1
• Choose either an apple and an orange, or a banana.
There are (7× 8) + 5 = 61 possible choices.
Generally, “AND” corresponds to multiplication and “OR” corresponds
to addition. The last two of the above examples show that it is important
to determine exactly how the words “AND” and “OR” combine in the de-
scription of the problem.
From a mathematical point of view, “AND” corresponds to the Cartesian
product of sets. If you choose one element of the set A AND you choose one
element of the set B, then this is equivalent to choosing one element of the
Cartesian product of A and B:
A×B = {(a, b) : a ∈ A and b ∈ B},
which is the set of all ordered pairs of elements (a, b) with a ∈ A and b ∈ B.
In general, the cardinalities of these sets are related by the formula
|A×B| = |A| · |B|.
Similarly, from a mathematical point of view, “OR” corresponds to the
union of sets. If you choose one element of the set A OR you choose one
element of the set B, then this is equivalent to choosing one element of the
union of A and B:
A ∪B = {c : c ∈ A or c ∈ B},
which is the set of all elements c which are either in A or in B.
It is not always true that |A∪B| = |A|+ |B|, because any elements in both
A and B would be counted twice by |A| + |B|. The intersection of A and B
is the set
A ∩B = {c : c ∈ A and c ∈ B},
which is the set of all elements c which are both in A and in B. What is
generally true is that
|A ∪B| = |A|+ |B| − |A ∩B|.
(This is the first instance of the Principle of Inclusion/Exclusion, which will
be discussed in general in Subsection 1.1.6.) In particular, if A ∩ B = ∅
then |A ∪ B| = |A| + |B|. Thus, in order to interpret “OR” as addition, it
Section 1.1 Basic Principles. 17
is important to check that the sets of choices A and B have no elements in
common. Such a union of sets A and B for which A ∩ B = ∅ is called a
disjoint union of sets.
When solving enumeration problems it is usually very useful to describe
a choice sequence for constructing the set of objects of interest, paying close
attention to the words “AND” and “OR”.
1.1.2 Lists, permutations, and subsets.
A list of a set S is a list of the elements of S exactly once each, in some
order. For example, the lists of the set {1, a,X, g} are:
1aXg a1Xg X1ag g1aX
1agX a1gX X1ga g1Xa
1Xag aX1g Xa1g ga1X
1Xga aXg1 Xag1 gaX1
1gaX ag1X Xg1a gX1a
1gXa agX1 Xga1 gXa1
A permutation is a list of the set {1, 2, ..., n} for some n ∈ N. A per-
mutation σ : a1a2...an can be interpreted as a function σ : {1, 2, ..., n} →
{1, 2, ..., n} by putting σ(i) = ai for all 1 ≤ i ≤ n.
To construct a list of S we can choose any element v of S to be the first
element in the list and follow this with any list of the set S r {v}. That is
how the table above is arranged – each of the four columns corresponds
to one choice of an element of {1, a,X, g} to be the first element of the list.
Within each column, all the lists of the remaining elements appear after the
first element.
Let pn denote the number of lists of an n-element set S. The first sentence
of the previous paragraph is translated into the equation
pn = n · pn−1,
provided that n is positive. (In this equation there are n choices for the first
element v of the list, AND pn−1 choices for the list of S r {v} which follows
it.) It is important to note here that each list of S will be produced exactly
once by this construction.
18 Basic Principles. Section 1.1
Since it is easy to see that p1 = 1 (and p2 = 2), a simple proof by induction
on n shows the following:
Theorem 1.2. For every n ≥ 1, the number of lists of an n-element set S is
n(n− 1)(n− 2) · · · 3 · 2 · 1.
In particular, taking S = {1, 2, ..., n}, this is the number of permutations of
size n. The term n factorial is used for the number n(n− 1) · · · 3 · 2 · 1, and it
is denoted by n! for convenience. We also define 0! to be the number of lists
of the 0-element (empty) set ∅. Since we want the equation pn = n · pn−1 to
hold when n = 1, and since p1 = 1! = 1, we conclude that 0! = p0 = 1 as
well.
A subset of a set S is a collection of some (perhaps none or all) of the
elements of S, at most once each and in no particular order.
To specify a particular subset A of S, one has to decide for each element v
of S whether v is in A or v is not in A. Thus we have two choices – v ∈ A OR
v 6∈ A – for each element v of S. If S = {v1, v2, ..., vn} has n elements then the
total number of choices is 2n since we have 2 choices for v1 AND 2 choices
for v2 AND . . . AND 2 choices for vn.
Theorem 1.3. For every n ≥ 0, the number of subsets of an n-element set
is 2n.
A partial list of a set S is a list of a subset of S. That is, it is a list of some
(perhaps none or all) of the elements of S, at most once each and listed in
some particular order. We are going to count partial lists of length k of an
n-element set.
First think about the particular case n = 6 and k = 3, and the set S =
{a, b, c, d, e, f}. A partial list of S of length 3 is a list xyz of elements of S,
which must all be different. There are:
6 choices for x (since x is in S), AND
5 choices for y (since y ∈ S but y 6= x), AND
4 choices for z (since z ∈ S but z 6= x and z 6= y).
Altogether there are 6 · 5 · 4 = 120 partial lists of {a, b, c, d, e, f} of length 3.
Section 1.1 Basic Principles. 19
This kind of reasoning works just as well in the general case. If S is an
n-element set and we want to construct a partial list v1v2...vk of elements of
S of length k, then there are:
n choices for v1, AND
n− 1 choices for v2, AND
....
n− (k − 2) choices for vk−1, AND
n− (k − 1) choices for vk.
This proves the following result.
Theorem 1.4. For n, k ≥ 0, the number of partial lists of length k of an
n-element set is n(n− 1) · · · (n− k + 2)(n− k + 1).
Notice that if k > n then the number 0 will appear as one of the factors in
the product n(n− 1) · · · (n− k + 2)(n− k + 1). This makes sense, because if
k > n then there are no partial lists of length k of an n-element set. On the
other hand, if 0 ≤ k ≤ n then we could also write this product as
n(n− 1) · · · (n− k + 2)(n− k + 1) = n!
(n− k)! .
We next count subsets of an n-element set S which have a particular size
k. So for n, k ≥ 0 let (n
k
)
denote the number of k-element subsets of an n-
element set S. Notice that if k < 0 or k > n then
(
n
k
)
= 0 because in these
cases it is impossible for S to have a k-element subset. Thus we need only
consider k in the range 0 ≤ k ≤ n.
To count k-element subsets of S we consider another way of constructing
a partial list of length k of S. Specifically, we can choose a k-element subset
A of S AND a list of A. The result will be a list of a subset of S of length
k. Since every partial list of length k of S is constructed exactly once in this
way, this translates into the equation(
n
k
)
· k! = n!
(n− k)! .
20 Basic Principles. Section 1.1
In summary, we have proved the following result.
Theorem 1.5. For 0 ≤ k ≤ n, the number of k-element subsets of an n-
element set is (
n
k
)
=
n!
k!(n− k)! .
The numbers
(
n
k
)
are read as “n choose k” and are called binomial coefficients .
1.1.3 Think of what the numbers mean.
Usually, when faced with a formula to prove, one’s first thought is to prove
it by algebraic calculations, or perhaps with an induction argument, or maybe
with a combination of the two. But often that is not the easiest way, nor is
it the most informative. A much better strategy is one which gives some in-
sight into the meaning of all of the parts of the formula. If we can interpret
all the numbers as counting things, addition as “OR”, and multiplication
as “AND”, then we can hope to find an explanation of the formula by con-
structing some objects in the correct way.
Example 1.6. Consider the equation, for any n ≥ 0:(
n
0
)
+
(
n
1
)
+
(
n
2
)
+ · · ·+
(
n
n
)
= 2n.
This could be proved by induction on n, but many more details would
have to be given and the proof would not address the true “meaning” of
the formula. Instead, let’s interpret everything combinatorially:
• the number of subsets of the n-element set {1, 2, ..., n} is 2n;
• for each 0 ≤ k ≤ n, the number of k-element subsets of {1, 2, ..., n}
is
(
n
k
)
;
• addition corresponds to “OR” (that is, disjoint union of sets).
So, this formula is saying that choosing a subset of {1, 2, ..., n} (in one of
2n ways) is equivalent to choosing a k-element subset of {1, 2, ..., n} (in
one of
(
n
k
)
ways) for exactly one value of k in the range 0 ≤ k ≤ n. Said
that way the formula becomes self–evident, and there is nothing more
to prove.
Section 1.1 Basic Principles. 21
Example 1.7. Consider the equation(
n
k
)
=
(
n− 1
k − 1
)
+
(
n− 1
k
)
where we are using the fact that
(
m
j
)
= 0 if j < 0 or j > m.
This equation can be proven algebraically from the formula of Theo-
rem 1.5, and that is a good exercise which I encourage you to try. But
a more informative proof interprets these numbers combinatorially as
follows:
• (n
k
)
is the number of k-element subsets of {1, 2, ..., n};
• (n−1
k−1
)
is the number of (k − 1)-element subsets of {1, 2, ..., n− 1};
• (n−1
k
)
is the number of k-element subsets of {1, 2, ..., n− 1};
• addition corresponds to disjoint union of sets.
So, this equation is saying that choosing a k-element subsetA of {1, 2, ..., n}
is equivalent to either choosing a (k−1)-element subset of {1, 2, ..., n−1}
or a k-element subset of {1, 2, ..., n − 1}. This is perhaps not as clear as
the previous example, but the two cases depend upon whether the cho-
sen k-element subset A of {1, 2, ..., n} is such that n ∈ A OR n 6∈ A. If
n ∈ A then Ar {n} is a (k− 1)-element subset of {1, 2, ..., n− 1}, while if
n 6∈ A then A is a k-element subset of {1, 2, ..., n − 1}. This construction
explains the correspondence, proving the formula.
This principle – interpreting equations combinatorially and proving the
formulas by describing explicit correspondences between sets of objects –
is one of the most important and powerful ideas in enumeration. We will
apply this way of thinking throughout the first part of these notes.
Incidentally, the equation in Example 1.7 is a very useful recurrence rela-
tion for computing binomial coefficients quickly. Together with the facts
(
n
k
)
=
n!
k!(n− k)! =
n!
(n− k)!(n− (n− k))! =
(
n
n− k
)
and
(
n
0
)
=
(
n
n
)
= 1 it can be used to compute any number of binomial coeffi-
22 Basic Principles. Section 1.1
cients without difficulty. The resulting table is known as Pascal’s Triangle :
n\k 0 1 2 3 4 5 6 7 8
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
1.1.4 Multisets.
Imagine a bag which contains a large number of marbles of three colours
– red, green, and blue, say. The marbles are all indistinguishable from one
another except for their colours. There are N marbles of each colour, where
N is very, very large (more precisely we should be considering the limit
as N → ∞). If I reach into the bag and pull out a handful of 11 marbles,
I will have r red marbles, g green marbles, and b blue marbles, for some
nonnegative integers (r, g, b) such that r + g + b = 11. How many possibile
outcomes are there?
The word “multiset” is meant to suggest a set in which the objects can oc-
cur more than once. For example, the outcome (4, 5, 2) in the above situation
corresponds to the “set” {R,R,R,R,G,G,G,G,G,B,B} in which R is a red
marble, G is a green marble, and B is a blue marble. This is an 11-element
multiset with elements of three types. The number of these multisets is the
solution to the above problem.
Definition 1.8. Let n ≥ 0 and t ≥ 1 be integers. A multiset of size nwith
elements of t types is a sequence of nonnegative integers (m1, ...,mt)
such that
m1 +m2 + · · ·+mt = n.
The interpretation is thatmi is the number of elements of the multiset which
are of the i-th type, for each 1 ≤ i ≤ t.
Section 1.1 Basic Principles. 23
Theorem 1.9. For any n ≥ 0 and t ≥ 1, the number of n-element multisets
with elements of t types is (
n+ t− 1
t− 1
)
.
Proof. Think of what that number means! By Theorem 1.5,
(
n+t−1
t−1
)
is the
number of (t − 1)-element subsets of an (n + t − 1)-element set. So, let’s
write down a row of (n+ t− 1) circles from left to right:
O O O O O O O O O O O O O
and cross out some t− 1 of these circles to choose a (t− 1)-element subset:
O O O O X O O O O O X O O
Now the t − 1 crosses chop the remaining sequence of n circles into t seg-
ments of consecutive circles. (Some of these segments might be empty,
which is to say of length zero.) Let mi be the length of the i-th segment
of consecutive O-s in this construction. Then m1 + m2 + · · · + mt = n, so
that (m1,m2, ...,mt) is an n-element multiset with t types. Conversely, if
(m1,m2, ...,mt) is an n-element multiset with t types then write down a se-
quence of m1 O-s, then an X, then m2 O-s, then an X, and so on, finishing
with an X and then mt O-s. The positions of the X-s will indicate a (t − 1)-
element subset of the positions {1, 2, ..., n+ t− 1}.
The construction of the above paragraph shows how to translate between
(t − 1)-element subsets of {1, 2, ..., n + t − 1} and n-element multisets with
t types of element. This one–to–one correspondence completes the proof of
the theorem.