An Introduction to Combinatorics and Graph Theory

An Introduction to

Combinatorics and Graph

Theory

David Guichard

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To

view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to

Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA. If you distribute

this work or a derivative, include the history of the document.

This copy of the text was compiled from source at 11:36 on 3/4/2023.

We will be glad to receive corrections and suggestions for improvement at [email protected].

Contents

Fundamentals 7

1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2 Combinations and permutations . . . . . . . . . . . . . . . . . 11

1.3 Binomial coeﬃcients . . . . . . . . . . . . . . . . . . . . . . . 16

1.4 Bell numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.5 Choice with repetition . . . . . . . . . . . . . . . . . . . . . . 27

1.6 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . 31

1.7 Sperner’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . 35

1.8 Stirling numbers . . . . . . . . . . . . . . . . . . . . . . . . . 39

Inclusion-Exclusion 45

2.1 The Inclusion-Exclusion Formula . . . . . . . . . . . . . . . . . 45

2.2 Forbidden Position Permutations . . . . . . . . . . . . . . . . . 48

4 Contents

Generating Functions 53

3.1 Newton’s Binomial Theorem . . . . . . . . . . . . . . . . . . . 53

3.2 Exponential Generating Functions . . . . . . . . . . . . . . . . 56

3.3 Partitions of Integers . . . . . . . . . . . . . . . . . . . . . . . 59

3.4 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . 62

3.5 Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . . . . 66

Systems of Distinct Representatives 71

4.1 Existence of SDRs . . . . . . . . . . . . . . . . . . . . . . . . 72

4.2 Partial SDRs . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.3 Latin Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.4 Introduction to Graph Theory . . . . . . . . . . . . . . . . . . 83

4.5 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

Graph Theory 91

5.1 The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5.2 Euler Circuits and Walks . . . . . . . . . . . . . . . . . . . . . 96

5.3 Hamilton Cycles and Paths . . . . . . . . . . . . . . . . . . . 100

5.4 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . 103

5.5 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

5.6 Optimal Spanning Trees . . . . . . . . . . . . . . . . . . . . 108

5.7 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.8 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . 118

5.9 The Chromatic Polynomial . . . . . . . . . . . . . . . . . . . 124

5.10 Coloring Planar Graphs . . . . . . . . . . . . . . . . . . . . . 125

5.11 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . 129

Contents 5

P´olya–Redﬁeld Counting 135

6.1 Groups of Symmetries . . . . . . . . . . . . . . . . . . . . . 137

6.2 Burnside’s Theorem . . . . . . . . . . . . . . . . . . . . . . 140

6.3 P´olya-Redﬁeld Counting . . . . . . . . . . . . . . . . . . . . 146

Hints 151

Index 153

Fundamentals

Combinatorics is often described brieﬂy as being about counting, and indeed counting is

a large part of combinatorics. As the name suggests, however, it is broader than this: it

is about combining things. Questions that arise include counting problems: “How many

ways can these elements be combined?” But there are other questions, such as whether a

certain combination is possible, or what combination is the “best” in some sense. We will

see all of these, though counting plays a particularly large role.

Graph theory is concerned with various types of networks, or really models of networks

called graphs. These are not the graphs of analytic geometry, but what are often described

as “points connected by lines”, for example:

.............................................................................................

•

The preferred terminology is vertex for a point and edge for a line. The lines need not

be straight lines, and in fact the actual deﬁnition of a graph is not a geometric deﬁnition.

The ﬁgure above is simply a visualization of a graph; the graph is a more abstract object,

consisting of seven vertices, which we might name {v

, . . . , v

}, and the collection of pairs

of vertices that are connected; for a suitable assignment of names v

to the points in

the diagram, the edges could be represented as {v

, v

},{v

, v

},{v

, v

},{v

, v

},{v

, v

},{v

, v

8 Chapter 1 Fundamentals

Suppose we have a chess board, and a collection of tiles, like domino es, each of which is the

size of two squares on the chess board. Can the chess board be covered by the domino es?

First we need to be clear on the rules: the board is covered if the dominoes are laid down so

that each covers exactly two squares of the board; no dominoes overlap; and every square

is covered. The answer is easy: simply by laying out 32 dominoes in rows, the board can

be covered. To make the problem more interesting, we allow the board to be rectangular

of any size, and we allow some squares to be removed from the board. What can be say

about whether the remaining board can be covered? This is such a board, for example:

What can we say? Here is an easy observation: each domino must cover two squares, so

the total number of squares must be even; the board above has an even number of squares.

Is that enough? It is not too hard to convince yourself that this b oard cannot be covered;

is there some general principle at work? Suppose we redraw the board to emphasize that

it really is part of a chess board:

Aha! Every tile must cover one white and one gray square, but there are four of the

former and six of the latter, so it is impossible. Now do we have the whole picture? No;

1.1 Examples 9

for example:

The gray square at the upper right clearly cannot be covered. Unfortunately it is not easy

to state a condition that fully characterizes the boards that can be covered; we will see

this problem again. Let us note, however, that this problem can also be represented as

a graph problem. We introduce a vertex corresponding to each square, and connect two

vertices by an edge if their associated squares can be covered by a single domino; here is

the previous board:

•

Here the top row of vertices represents the gray squares, the bottom row the white squares.

A domino now corresponds to an edge; a covering by dominoes corresponds to a collection

of edges that share no endpoints and that are incident with (that is, touch) all six vertices.

Since no edge is incident with the top left vertex, there is no cover.

Perhaps the most famous problem in graph theory concerns map coloring: Given a

map of some countries, how many colors are required to color the map so that countries

sharing a border get diﬀerent colors? It was long conjectured that any map could be

colored with four colors, and this was ﬁnally proved in 1976. Here is an example of a small

map, colored with four colors:

Typically this problem is turned into a graph theory problem. Suppose we add to each

country a capital, and connect capitals across common boundaries. Coloring the capitals so

10 Chapter 1 Fundamentals

that no two connected capitals share a color is clearly the same problem. For the previous

map:

...

•

Any graph produced in this way will have an important property: it can be drawn so that

no edges cross each other; this is a planar graph. Non-planar graphs can require more

than four colors, for example this graph:

•

This is called the complete graph on ﬁve vertices, denoted K

; in a complete graph,

each vertex is connected to each of the others. Here only the “fat” dots represent vertices;

intersections of edges at other points are not vertices. A few minutes spent trying should

convince you that this graph cannot be drawn so that its edges don’t cross, though the

number of edge crossings can be reduced.

Exercises 1.1.

1. Explain why an m ×n board can be covered if either m or n is even. Explain why it cannot

be covered if both m and n are odd.

2. Suppose two diagonally opposite corners of an ordinary 8 × 8 board are removed. Can the

resulting board be covered?

3. Suppose that m and n are both odd. On an m × n board, colored as usual, all four corners

will be the same color, say white. Suppose one white square is removed from any location

on the board. Show that the resulting board can be covered.

4. Suppose that one corner of an 8 × 8 board is removed. Can the remainder be covered by

1 × 3 tiles? Show a tiling or prove that it cannot be done.

1.2 Combinations and permutations 11

5. Suppose the square in row 3, column 3 of an 8 × 8 board is removed. Can the remainder be

covered by 1 × 3 tiles? Show a tiling or prove that it cannot be done.

6. Remove two diagonally opposite corners of an m × n board, where m is odd and n is even.

Show that the remainder can be covered with dominoes.

7. Suppose one white and one black square are removed from an n × n board, n even. Show

that the remainder can be covered by dominoes.

8. Suppose an n×n board, n even, is covered with dominoes. Show that the number of horizontal

dominoes with a white square under the left end is equal to the number of horizontal dominoes

with a black square under the left end.

9. In the complete graph on ﬁve vertices shown above, there are ﬁve pairs of edges that cross.

Draw this graph so that only one pair of edges cross. Remember that “edges” do not have

to be straight lines.

10. The complete bipartite graph K

3,3

consists of two groups of three vertices each, with all

possible edges between the groups and no other edges:

•

Draw this graph with only one crossing.

We turn ﬁrst to counting. While this sounds simple, perhaps too simple to study, it is

not. When we speak of counting, it is shorthand for determining the size of a set, or more

often, the sizes of many sets, all with something in common, but diﬀerent sizes depending

on one or more parameters. For example: how many outcomes are possible when a die is

rolled? Two dice? n dice? As stated, this is ambiguous: what do we mean by “outcome”?

Suppose we roll two dice, say a red die and a green die. Is “red two, green three” a

diﬀerent outcome than “red three, green two”? If yes, we are counting the number of

possible “physical” outcomes, namely 36. If no, there are 21. We might even be interested

simply in the possible totals, in which case there are 11 outcomes.

Even the quite simple ﬁrst interpretation relies on some degree of knowledge about

counting; we ﬁrst make two simple facts explicit. In terms of set sizes, suppose we know

that set A has size m and set B has size n. What is the size of A and B together, that is,

the size of A ∪ B? If we know that A and B have no elements in common, then the size

A ∪B is m + n; if they do have elements in common, we need more information. A simple

but typical problem of this type: if we roll two dice, how many ways are there to get either

7 or 11? Since there are 6 ways to get 7 and two ways to get 11, the answer is 6 + 2 = 8.

Though this principle is simple, it is easy to forget the requirement that the two sets be

12 Chapter 1 Fundamentals

disjoint, and hence to use it when the circumstances are otherwise. This principle is often

called the addition principle.

This principle can be generalized: if sets A

through A

are pairwise disjoint and have

sizes m

, . . . m

, then the size of A

∪···∪A



i=1

. This can be proved by a simple

induction argument.

Why do we know, without listing them all, that there are 36 outcomes when two dice

are rolled? We can view the outcomes as two separate outcomes, that is, the outcome

of rolling die number one and the outcome of rolling die number two. For each of 6

outcomes for the ﬁrst die the second die may have any of 6 outcomes, so the total is

6 + 6 + 6 + 6 + 6 + 6 = 36, or more compactly, 6 ·6 = 36. Note that we are really using the

addition principle here: set A

is all pairs (1, x), set A

is all pairs (2, x), and so on. This

is somewhat more subtle than is ﬁrst apparent. In this simple example, the outcomes of

die number two have nothing to do with the outcomes of die number one. Here’s a slightly

more complicated example: how many ways are there to roll two dice so that the two dice

don’t match? That is, we rule out 1-1, 2-2, and so on. Here for each possible value on

die number one, there are ﬁve possible values for die number two, but they are a diﬀerent

ﬁve values for each value on die numb er one. Still, because all are the same, the result is

5 + 5 + 5 + 5 + 5 + 5 = 30, or 6 ·5 = 30. In general, then, if there are m possibilities for one

event, and n for a second event, the number of possible outcomes for both events together

is m · n. This is often called the multiplication principle.

In general, if n events have m

possible outcomes, for i = 1, . . . , n, where each m

unaﬀected by the outcomes of other events, then the numb er of possible outcomes overall



i=1

. This too can be proved by induction.

EXAMPLE 1.2.1 How many outcomes are possible when three dice are rolled, if no two

of them may be the same? The ﬁrst two dice together have 6 · 5 = 30 possible outcomes,

from above. For each of these 30 outcomes, there are four possible outcomes for the third

die, so the total number of outcomes is 30 · 4 = 6 · 5 · 4 = 120. (Note that we consider the

dice to be distinguishable, that is, a roll of 6, 4, 1 is diﬀerent than 4, 6, 1, because the ﬁrst

and second dice are diﬀerent in the two rolls, even though the numbers as a set are the

same.)

EXAMPLE 1.2.2 Suppose blocks numbered 1 through n are in a barrel; we pull out k

of them, placing them in a line as we do. How many outcomes are possible? That is, how

many diﬀerent arrangements of k blocks might we see?

This is essentially the same as the previous example: there are k “spots” to be ﬁlled by

blocks. Any of the n blocks might appear ﬁrst in the line; then any of the remaining n −1

might appear next, and so on. The number of outcomes is thus n(n−1)(n−2) ···(n−k+1),

by the multiplication principle. In the previous example, the ﬁrst “spot” was die number

1.2 Combinations and permutations 13

one, the second spot was die number two, the third spot die number three, and 6 · 5 · 4 =

6(6 − 1)(6 − 2); notice that 6 − 2 = 6 − 3 + 1.

This is quite a general sort of problem:

DEFINITION 1.2.3 The number of permutations of n things taken k at a time is

P (n, k) = n(n − 1)(n − 2) ···(n − k + 1) =

(n − k)!

A permutation of some objects is a particular linear ordering of the objects; P (n, k)

in eﬀect counts two things simultaneously: the number of ways to choose and order k out

of n objects. A useful special case is k = n, in which we are simply counting the number

of ways to order all n objects. This is n(n − 1) ···(n − n + 1) = n!. Note that the second

form of P (n, k) from the deﬁnition gives

(n − n)!

This is correct only if 0! = 1, so we adopt the standard convention that this is true, that

is, we deﬁne 0! to be 1.

Suppose we want to count only the number of ways to choose k items out of n, that is,

we don’t care about order. In example 1.2.1, we counted the number of rolls of three dice

with diﬀerent numbers showing. The dice were distinguishable, or in a particular order: a

ﬁrst die, a second, and a third. Now we want to count simply how many combinations of

numbers there are, with 6, 4, 1 now counting as the same combination as 4, 6, 1.

EXAMPLE 1.2.4 Suppose we were to list all 120 possibilities in example 1.2.1. The list

would contain many outcomes that we now wish to count as a single outcome; 6, 4, 1 and

4, 6, 1 would be on the list, but should not be counted separately. How many times will a

single outcome appear on the list? This is a permutation problem: there are 3! orders in

which 1, 4, 6 can appear, and all 6 of these will be on the list. In fact every outcome will

appear on the list 6 times, since every outcome can appear in 3! orders. Hence, the list is

too big by a factor of 6; the correct count for the new problem is 120/6 = 20.

Following the same reasoning in general, if we have n objects, the number of ways to

cho ose k of them is P (n, k)/k!, as each collection of k objects will be counted k! times by

P (n, k).

14 Chapter 1 Fundamentals

DEFINITION 1.2.5 The number of subsets of size k of a set of size n (also called an

n-set) is

C(n, k) =

P (n, k)

k!(n − k)!





The notation C(n, k) is rarely used; instead we use





, pronounced “n choose k”.

EXAMPLE 1.2.6 Consider n = 0, 1, 2, 3. It is easy to list the subsets of a small n-set; a

typical n-set is {a

, a

, . . . , a

}. A 0-set, namely the empty set, has one subset, the empty

set; a 1-set has two subsets, the empty set and {a

}; a 2-subset has four subsets, ∅, {a

}, {a

, a

}; and a 3-subset has eight: ∅, {a

}, {a

, a

}, {a

, a

}, {a

, a

}. From these lists it is then easy to compute





0 1 2 3

0 1

n 1 1 1

2 1 2 1

3 1 3 3 1

You probably recognize these numbers: this is the beginning of Pascal’s Triangle.

Each entry in Pascal’s triangle is generated by adding two entries from the previous row:

the one directly above, and the one above and to the left. This suggests that







n−1

k−1





n−1



, and indeed this is true. To make this work out neatly, we adopt the

convention that





= 0 when k < 0 or k > n.

THEOREM 1.2.7







n − 1

k −1





n − 1



Proof. A typical n-set is A = {a

, . . . , a

}. We consider two types of subsets: those

that contain a

and those that do not. If a k-subset of A does not contain a

, then it is

a k-subset of {a

, . . . , a

n−1

}, and there are



n−1



of these. If it does contain a

, then it

consists of a

and k − 1 elements of {a

, . . . , a

n−1

}; since there are



n−1

k−1



of these, there

are



n−1

k−1



subsets of this type. Thus the total number of k-subsets of A is



n−1

k−1





n−1



Note that when k = 0,



n−1

k−1





n−1

−1



= 0, and when k = n,



n−1





n−1



= 0,

so that







n−1



and







n−1



. These values are the boundary ones in Pascal’s

Triangle.

Many counting problems rely on the sort of reasoning we have seen. Here are a few

variations on the theme.

1.2 Combinations and permutations 15

EXAMPLE 1.2.8 Six people are to sit at a round table; how many seating arrangements

are there?

It is not clear exactly what we mean to count here. If there is a “special seat”, for

example, it may matter who ends up in that seat. If this doesn’t matter, we only care

about the relative p osition of each person. Then it may or may not matter whether a

certain person is on the left or right of another. So this question can be interpreted in (at

least) three ways. Let’s answer them all.

First, if the actual chairs occupied by p eople matter, then this is exactly the same

as lining six people up in a row: 6 choices for seat number one, 5 for seat two, and so

on, for a total of 6!. If the chairs don’t matter, then 6! counts the same arrangement too

many times, once for each person who might be in seat one. So the total in this case is

6!/6 = 5!. Another approach to this: since the actual seats don’t matter, just put one

of the six people in a chair. Then we need to arrange the remaining 5 people in a row,

which can be done in 5! ways. Finally, suppose all we care about is who is next to whom,

ignoring right and left. Then the previous answer counts each arrangement twice, once for

the counterclockwise order and once for clockwise. So the total is 5!/2 = P (5, 3).

We have twice seen a general principle at work: if we can overcount the desired set in

such a way that every item gets counted the same number of times, we can get the desired

count just by dividing by the common overcount factor. This will continue to be a useful

idea. A variation on this theme is to overcount and then subtract the amount of overcount.

EXAMPLE 1.2.9 How many ways are there to line up six people so that a particular

pair of people are not adjacent?

Denote the people A and B. The total number of orders is 6!, but this counts those

orders with A and B next to each other. How many of these are there? Think of these

two people as a unit; how many ways are there to line up the AB unit with the other 4

people? We have 5 items, so the answer is 5!. Each of these orders corresponds to two

diﬀerent orders in which A and B are adjacent, depending on whether A or B is ﬁrst. So

the 6! count is too high by 2 · 5! and the count we seek is 6! − 2 · 5! = 4 · 5!.

Exercises 1.2.

1. How many positive factors does 2 ·3

·7

·11

·47

have? How many does p

···p

have,

where the p

are distinct primes?

2. A poker hand consists of ﬁve cards from a standard 52 card deck with four suits and thirteen

values in each suit; the order of the cards in a hand is irrelevant. How many hands consist

of 2 cards with one value and 3 cards of another value (a full house)? How many consist of

5 cards from the same suit (a ﬂush)?

16 Chapter 1 Fundamentals

3. Six men and six women are to be seated around a table, with men and women alternating.

The chairs don’t matter, only who is next to whom, but right and left are diﬀerent. How

many seating arrangements are possible?

4. Eight people are to be seated around a table; the chairs don’t matter, only who is next to

whom, but right and left are diﬀerent. Two people, X and Y, cannot be seated next to each

other. How many seating arrangements are possible?

5. In chess, a rook attacks any piece in the same row or column as the rook, provided no other

piece is between them. In how many ways can eight indistinguishable rooks be placed on a

chess board so that no two attack each other? What about eight indistinguishable rooks on

a 10 ×10 board?

6. Suppose that we want to place 8 non-attacking rooks on a chessboard. In how many ways

can we do this if the 16 most ‘northwest’ squares must be empty? How ab out if only the 4

most ‘northwest’ squares must be empty?

7. A “legal” sequence of parentheses is one in which the parentheses can be properly matched,

like ()(()). It’s not hard to see that this is possible precisely when the number of left and right

parentheses is the same, and every initial segment of the sequence has at least as many left

parentheses as right. For example, ()) . . . cannot possibly be extended to a legal sequence.

Show that the number of legal sequences of length 2n is C





−



n+1



. The numbers

are called the Catalan numbers.

Recall the appearance of Pascal’s Triangle in example 1.2.6. If you have encountered the

triangle before, you may know it has many interesting properties. We will explore some of

these here.

You may know, for example, that the entries in Pascal’s Triangle are the coeﬃcients

of the p olynomial produced by raising a binomial to an integer power. For example,

(x + y)

= 1 ·x

+ 3 ·x

y + 3 ·xy

+ 1 ·y

, and the coeﬃcients 1, 3, 3, 1 form row three of

Pascal’s Triangle. For this reason the numbers





are usually referred to as the binomial

coeﬃcients.

THEOREM 1.3.1 Binomial Theorem

(x + y)









n−1

y +





n−2

+ ···+







i=0





n−i

Proof. We prove this by induction on n. It is easy to check the ﬁrst few, say for

n = 0, 1, 2, which form the base case. Now suppose the theorem is true for n − 1, that is,

(x + y)

n−1



i=0



n − 1



n−1−i

Then

(x + y)

= (x + y)(x + y)

n−1

= (x + y)

n−1



i=0



n − 1



n−1−i

1.3 Binomial coeﬃcients 17

Using the distributive property, this becomes

n−1



i=0



n − 1



n−1−i

+ y

n−1



i=0



n − 1



n−1−i

n−1



i=0



n − 1



n−i

n−1



i=0



n − 1



n−1−i

i+1

These two sums have much in common, but it is slightly disguised by an “oﬀset”: the ﬁrst

sum starts with an x

term and ends with an x

n−1

term, while the corresponding

terms in the second sum are x

n−1

and x

. Let’s rewrite the second sum so that they

match:

n−1



i=0



n − 1



n−i

n−1



i=0



n − 1



n−1−i

i+1

n−1



i=0



n − 1



n−i



i=1



n − 1

i − 1



n−i



n − 1



n−1



i=1



n − 1



n−i

n−1



i=1



n − 1

i − 1



n−i



n − 1





n − 1



n−1



i=1

(



n − 1





n − 1

i − 1



n−i



n − 1



Now we can use theorem 1.2.7 to get:



n − 1



n−1



i=1

(



n − 1





n − 1

i − 1



n−i



n − 1





n − 1



n−1



i=1





n−i



n − 1







n−1



i=1





n−i







i=0





n−i

At the next to last step we used the facts that



n−1







and



n−1







Here is an interesting consequence of this theorem: Consider

(x + y)

= (x + y)(x + y) ···(x + y).

One way we might think of attempting to multiply this out is this: Go through the n

factors (x + y) and in each factor choose either the x or the y; at the end, multiply your

18 Chapter 1 Fundamentals

choices together, getting some term like xxyxyy ···yx = x

, where of course i + j = n.

If we do this in all possible ways and then collect like terms, we will clearly get



i=0

n−i

We know that the correct expansion has





= a

; is that in fact what we will get by this

method? Yes: consider x

n−i

. How many times will we get this term using the given

method? It will be the number of times we end up with i y-factors. Since there are n

factors (x + y), the numb er of times we get i y-factors must be the number of ways to pick

i of the (x + y) factors to contribute a y, namely





. This is probably not a useful method

in practice, but it is interesting and occasionally useful.

EXAMPLE 1.3.2 Using this method we might get

(x + y)

= xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy

which indeed becomes x

+ 3x

y + 3xy

+ y

upon collecting like terms.

The Binomial Theorem, 1.3.1, can be used to derive many interesting identities. A

common way to rewrite it is to substitute y = 1 to get

(x + 1)



i=0





n−i

If we then substitute x = 1 we get



i=0





that is, row n of Pascal’s Triangle sums to 2

. This is also easy to understand combinato-

rially: the sum represents the total number of subsets of an n-set, since it adds together

the numbers of subsets of every possible size. It is easy to see directly that the numb er of

subsets of an n-set is 2

: for each element of the set we make a choice, to include or to

exclude the element. The total number of ways to make these choices is 2 ·2 ···2 = 2

, by

the multiplication principle.

Suppose now that n ≥ 1 and we substitute −1 for x; we get

(−1 + 1)



i=0





(−1)

n−i

. (1.3.1)

The sum is now an alternating sum: every other term is multiplied by −1. Since the left

hand side is 0, we can rewrite this to get









+ ··· =









+ ···. (1.3.2)

So each of these sums is 2

n−1

1.3 Binomial coeﬃcients 19

Another obvious feature of Pascal’s Triangle is symmetry: each row reads the same

forwards and backwards. That is, we have:

THEOREM 1.3.3







n − i



Proof. This is quite easy to see combinatorially: every i-subset of an n-set is associated

with an (n − i)-subset. That is, if the n-set is A, and if B ⊆ A has size i, then the

complement of B has size n −i. This establishes a 1–1 correspondence between sets of size

i and sets of size n − i, so the numbers of each are the same. (Of course, if i = n − i, no

proof is required.)

Note that this means that the Binomial Theorem, 1.3.1, can also be written as

(x + y)



i=0



n − i



n−i

(x + y)



i=0





n−i

Another striking feature of Pascal’s Triangle is that the entries across a row are strictly

increasing to the middle of the row, and then strictly decreasing. Since we already know

that the rows are symmetric, the ﬁrst part of this implies the second.

THEOREM 1.3.4 For 1 ≤ i ≤ ⌊

⌋,







i − 1



Proof. This is by induction; the base case is apparent from the ﬁrst few rows. Write







n − 1

i − 1





n − 1





i − 1





n − 1

i − 2





n − 1

i − 1



Provided that 1 ≤ i ≤ ⌊

n−1

⌋, we know by the induction hypothesis that



n − 1





n − 1

i − 1



Provided that 1 ≤ i − 1 ≤ ⌊

n−1

⌋, or equivalently 2 ≤ i ≤ ⌊

n−1

⌋ + 1, we know that



n − 1

i − 1





n − 1

i − 2



Hence if 2 ≤ i ≤ ⌊

n−1

⌋,







i − 1



This leaves two special cases to check: i = 1 and for n even, i = ⌊

n−1

⌋ + 1 = ⌊

⌋. These

are left as an exercise.

20 Chapter 1 Fundamentals

Exercises 1.3.

1. Suppose a street grid starts at position (0, 0) and extends up and to the right:

(0, 0)

A shortest route along streets from (0, 0) to (i, j) is i + j blocks long, going i blocks east and

j blocks north. How many such routes are there? Suppose that the block between (k, l) and

(k + 1, l) is closed, where k < i and l ≤ j. How many shortest routes are there from (0, 0) to

(i, j)?

2. Prove by induction that



k=0







n+1

i+1



for n ≥ 0 and i ≥ 0.

3. Use a combinatorial argument to prove that



k=0







n+1

i+1



for n ≥ 0 and i ≥ 0; that is,

explain why the left-hand side counts the same thing as the right-hand side.

4. Use a combinatorial argument to prove that







n−k



+ k(n − k) =





5. Use a combinatorial argument to prove that





is even.

6. Suppose that A is a non-empty ﬁnite set. Prove that A has as many even-sized subsets as it

does odd-sized subsets.

7. Prove that



k=0





k =



n+1

i+1



n −



n+1

i+2



for n ≥ 0 and i ≥ 0.

8. Verify that



n+1







= n

. Use exercise 2 to ﬁnd a simple expression for



i=1

9. Make a conjecture about the sums of the upward diagonals in Pascal’s Triangle as indicated.

Prove your conjecture is true.

1 1

1 2 1

1 3 3 1

1 4 6 4 1

10. Find the number of ways to write n as an ordered sum of ones and twos, n ≥ 0. For example,

when n = 4, there are ﬁve ways: 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, and 2 + 2.

11. Use (x + 1)



i=0





to ﬁnd a simple expression for



i=1





i−1

. Then ﬁnd a simple

expression for



i=1





12. Use (x + 1)



i=0





to ﬁnd a simple expression for



i=0

i+1





i+1

. Then ﬁnd a

simple expression for



i=0

i+1





13. Use the previous exercise to ﬁnd a simple expression for



i=0

(−1)

i+1





1.4 Bell numbers 21

14. Give a combinatorial proof of



i=0





k − i





m + n



Rewrite this identity in simpler form if m = n, and when k = m = n.

15. Finish the proof of theorem 1.3.4.

16. Give an alternate proof of theorm 1.3.4 by characterizing those i for which







i−1



> 1.

17. When is







i−1



a maximum? When is







i−1



= 2?

18. When is





−



i−1



a maximum?

19. A Galton board is an upright ﬂat surface with protruding horizontal pins arranged as shown

below. At the bottom are a number of bins; if the number of rows is n, the number of bins

is n + 1. A ball is dropped directly above the top pin, and at each pin bounces left or right

with equal probability. We assume that the ball next hits the pin below and immediately left

or right of the pin it has struck, and this continues down the board, until the ball falls into

a bin at the bottom. If we number the bins from 0 to n, how many paths can a ball travel

to end up in bin k?

This may be interpreted in terms of probability, which was the intent of Sir Francis

Galton when he designed it. Each path is equally likely to be taken by a ball. If many balls

are dropped, the number of balls in bin k corresponds to the probability of ending up in

that bin. The more paths that end in a bin, the higher the probability. When a very large

number of balls are dropped, the balls will form an approximation to the b ell curve familiar

from probability and statistics.

There is an animation of the process at

https://www.randomservices.org/random/apps/GaltonBoardExperiment.html.

There was once a very nice physical implementation at the Pacific Science Center in

Seattle.

•

We begin with a deﬁnition:

22 Chapter 1 Fundamentals

DEFINITION 1.4.1 A partition of a set S is a collection of non-empty subsets A

⊆ S,

1 ≤ i ≤ k (the parts of the partition), such that



i=1

= S and for every i ̸= j,

∩ A

= ∅.

EXAMPLE 1.4.2 The partitions of the set {a, b, c } are {{a}, {b}, {c}}, {{a, b}, {c}},

{{a, c}, {b}}, {{b, c}, {a}}, and {{a, b, c}}.

Partitions arise in a numb er of areas of mathematics. For example, if ≡ is an equiv-

alence relation on a set S, the equivalence classes of ≡ form a partition of S. Here we

consider the number of partitions of a ﬁnite set S, which we might as well take to be

[n] = {1, 2, 3, . . . , n}, unless some other set is of interest. We denote the number of parti-

tions of an n-element set by B

; these are the Bell numbers. From the example above, we

see that B

= 5. For convenience we let B

= 1. It is quite easy to see that B

= 1 and

= 2.

There are no known simple formulas for B

, so we content ourselves with a recurrence

relation.

THEOREM 1.4.3 The Bell numbers satisfy

n+1



k=0





Proof. Consider a partition of S = {1, 2, . . . , n + 1}, A

,. . . ,A

. We may suppose that

n + 1 is in A

, and that |A

| = k + 1, for some k, 0 ≤ k ≤ n. Then A

,. . . ,A

form a

partition of the remaining n −k elements of S, that is, of S\A

. There are B

n−k

partitions

of this set, so there are B

n−k

partitions of S in which one part is the set A

. There are





sets of size k + 1 containing n + 1, so the total number of partitions of S in which n+ 1

is in a set of size k + 1 is





n−k

. Adding up over all possible values of k, this means

n+1



k=0





n−k

. (1.4.1)

We may rewrite this, using theorem 1.3.3, as

n+1



k=0



n − k



n−k

and then notice that this is the same as the sum

n+1



k=0





written backwards.

1.4 Bell numbers 23

EXAMPLE 1.4.4 We apply the recurrence to compute the ﬁrst few Bell numbers:



k=0





= 1 · 1 = 1



k=0













= 1 · 1 + 1 · 1 = 1 + 1 = 2



k=0





= 1 · 1 + 2 · 1 + 1 · 2 = 5



k=0





= 1 · 1 + 3 · 1 + 3 · 2 + 1 · 5 = 15

The Bell numbers grow exponentially fast; the ﬁrst few are 1, 1, 2, 5, 15, 52, 203, 877,

4140, 21147, 115975, 678570, 4213597, 27644437.

The Bell numbers turn up in many other problems; here is an interesting example.

A common need in some computer programs is to generate a random permutation of

1, 2, 3, . . . , n, which we may think of as a shuﬄe of the numbers, visualized as numbered

cards in a deck. Here is an attractive method that is easy to program: Start with the

numbers in order, then at each step, remove one number at random (this is easy in most

programming languages) and put it at the front of the list of numbers. (Viewed as a shuﬄe

of a deck of cards, this corresponds to removing a card and putting it on the top of the

deck.) How many times should we do this? There is no magic number, but it certainly

should not be small relative to the size of n. Let’s choose n as the number of steps.

We can write such a shuﬄe as a list of n integers, (m

, m

, . . . , m

). This indicates

that at step i, the number m

is moved to the front.

EXAMPLE 1.4.5 Let’s follow the shuﬄe (3, 2, 2, 4, 1):

(3) : 31245

(2) : 23145

(4) : 42315

(1) : 14235

Note that we allow “do nothing” moves, removing the top card and then placing it on

top. The number of possible shuﬄes is then easy to count: there are n choices for the card

24 Chapter 1 Fundamentals

to remove, and this is repeated n times, so the total number is n

. (If we continue a shuﬄe

for m steps, the number of shuﬄes is n

.) Since there are only n! diﬀerent permutations

of 1, 2, . . . , n, this means that many shuﬄes give the same ﬁnal order.

Here’s our question: how many shuﬄes result in the original order?

EXAMPLE 1.4.6 These shuﬄes return to the original order: (1, 1, 1, 1, 1), (5, 4, 3, 2, 1),

(4, 1, 3, 2, 1).

THEOREM 1.4.7 The number of shuﬄes of [n] that result in the original sorted order

is B

Proof. Since we know that B

counts the number of partitions of {1, 2, 3, . . . , n}, we can

prove the theorem by establishing a 1–1 correspondence between the shuﬄes that leave

the deck sorted and the partitions. Given a shuﬄe (m

, m

, . . . , m

), we put into a single

set all i such that m

has a single value. For example, using the shuﬄe (4, 1, 3, 2, 1), Since

= m

, one set is {2, 5}. All the other values are distinct, so the other sets in the

partition are {1}, {3}, and {4}.

Note that every shuﬄe, no matter what the ﬁnal order, produces a partition by this

method. We are only interested in the shuﬄes that leave the deck sorted. What we now

need is to show that each partition results from exactly one such shuﬄe.

Suppose we have a partition with k parts. If a shuﬄe leaves the deck sorted, the last

entry, m

, must be 1. If the part containing n is A

, then it must be that m

= 1 if and

only if i ∈ A

. If k = 1, then the only part contains all of {1, 2, . . . , n}, and the shuﬄe

must be (1, 1, 1, . . . , 1).

If k > 1, the last move that is not 1 must be 2, since 2 must end up immediately after

1. Thus, if j

is the largest index such that j

/∈ A

, let A

be the part<