Description

Please solve the Question and show all the steps. you may need the note(pdf) but you cannot copy from.

2 attachmentsSlide 1 of 2attachment_1attachment_1attachment_2attachment_2

Unformatted Attachment Preview

MATH3143

Combinatorics

Lecture Notes, 2021

University of Leeds

Lecturer for 2021 Course: Rudolf Tange.

Acknowledgments

Apart from some changes by Rudolf Tange, these notes were written by Charles

Harris and Richard Elwes who used for Chapters 1-4 and 9 a previous version written

by Prof. Anand Pillay and Dr Alison Parker (with their permission).

Chapters 1-5 and 9 are based on material from How to Count: An Introduction to

Combinatorics by R. Allenby and A. Slomson.

Chapters 6-8 are based on material from Combinatorics: Topics, Techniques and

Algorithms, by P. Cameron.

These are the references books for the course. Copies are held in the library.

Contents

Chapter 1. Ordered and unordered selections, occupancy problems.

1

Chapter 2. Partitions of sets, Bell numbers, and Stirling numbers.

10

Chapter 3. The Inclusion–Exclusion principle and applications.

14

Chapter 4. Partitions of numbers.

18

Chapter 5. Generating functions. Euler’s generating function for partition

numbers.

22

1. Functions and Power Series.

22

2. Generating Functions.

24

3. Euler’s generating function for partition numbers.

26

Chapter 6. Systems of distinct representatives and Hall’s Theorem.

30

1. Hall’s (marriage) Theorem

30

2. How many SDR’s are there?

34

Chapter 7. Latin squares.

35

1. Latin squares and Latin rectangles

35

2. How many Latin Squares are there?

36

3. Youden squares

37

Chapter 8. Extremal Set Theory.

38

1. Intersecting Families

38

2. Sperner Families

40

3. The De Bruijn Erdös Theorem (Not Examinable)

43

Chapter 9. The pigeonhole principle & Ramsey numbers.

45

1. Preliminaries

45

2. The Pigeonhole Principle

46

3. Ramsey Theory

47

ii

CHAPTER 1

Ordered and unordered selections, occupancy problems.

There is some overlap between this chapter and Chapter 2 of Allenby–Slomson.

What is Combinatorics?

Combinatorics is about counting. But how can this be, when counting is something we all learn to do in early childhood? The difference is that in combinatorics

we count sets of objects which depend on one or more parameters, and we want the

answer as a function of these parameters; preferably an explicit formula.

The applications of Combinatorics are widespread in computer science, finance,

statistics, optimisation, and industrial engineering to name just a few. There is also

a particularly close connection between combinatorics and probability theory.

Many problems arise in the real world in the form “how many…?” Not all such

problems have easy solutions. During this module we will introduce techniques for

dealing with some of the more difficult problems of this kind.

We’ll start with some basic counting principles and examples.

Principle 1.1. Two ways of counting the same finite set give the same answer.

This is obvious of course. All the same, it is the basis of many of the proofs we

shall meet in this course. A closely related principle is

Principle 1.2. If there is a bijection between two finite sets, then these sets

have the same size.

Here is an application of the first principle.

Lemma 1.3 (Hand-shaking lemma). The number of delegates at a conference

who shake hands an odd number of times is even.

Proof. Let D1 ,. . .,Dn be the delegates, and let X = {(i, j) | Di and Dj shake hands}.

We count |X| in two ways.

First, |X| is twice the number of handshakes, so |X| is even.

Next, let xi be the number of times that Di shakes hands. Then |X| = x1 +

· · · + xn . Thus x1 + · · · + xn is even, which implies that evenly many of the xi are

odd, which is what we wanted to prove.

1

Principle 1.4 (Multiplication principle). If we make k successive choices, and

for 1 ≤ i ≤ k the number of ways of making the ith choice is ni , then the total

number of choices is n1 × · · · × nk .

One way of illustrating this is to use a tree. For example, suppose we are in a

restaurant ordering from a menu with 2 different starters (soup or pâté), 3 different

main courses (steak, fish or veggie) and 2 desserts (chocolate cake or lemon sorbet).

Pâté

Soup

Steak

Fish

Steak

Veggie

Fish

Veggie

Cake Sorbet Cake Sorbet Cake Sorbet Cake Sorbet Cake Sorbet Cake Sorbet

Since our choice at each course doesn’t affect the number of choices for subsequent courses, we see that there are 2 × 3 × 2 = 12 different total possible dinners.

We can also use this to illustrate a connection to probability theory. What is the

chance that someone selecting randomly from the menu will choose Soup, Veggie,

Sorbet? This is one choice among 12 equally likely possibilities, giving

1

.

12

(What

is the probability they will start with Soup and end with Sorbet?)

Corollary 1.5. For k ≤ n the number of ways of arranging (or permuting, or

selecting in order) k objects from a total of n, is n × (n − 1) × · · · × (n − k + 1) =

n!

.

(n−k)!

This number is also denoted P (n, k) (the “P” stands for permutations).

NB: to make our formulae consistent, it is convenient to set 0! = 1.

Example 1.6. In a race with 20 horses the number of ways in which the first 3

places can be filled (with no ties) is 20 × 19 × 18 = P (20, 3) = 6840.

Remark 1.7. Note that P (n, n) = n! = the number of permutations of a set of

n objects.

Example 1.8. How many ways can we place 8 rooks on an 8 by 8 chessboard

(with a distinguished corner) so that no two rooks can attack each other? This is

2

the same as asking how many ways are there placing 8 ones in an 8 by 8 matrix so

that no column or row has more than 1 one in it.

We place a rook in each row in turn. We first have 8 choices, then 7 choices for

the 2nd rook in the 2nd row and then 6 choices for the third rook in the third row

and so on. There are thus 8! = 40320 different arrangements.

Lemma 1.9. The number of ways of choosing k out of n objects (without regard

to order) is the same as the number of k-element subsets of an n-element set; it

equals

P (n,k)

k!

=

n×(n−1)×···×(n−k+1)

k!

=

(“C” for “choose” or “combination”)

n!

.

(n−k)!k!

n

or k .

We denote this number by C(n, k)

Proof. Each choice of k out of n objects gives rise to k! permutations of k out

of n objects. So C(n, k).k! = P (n, k).

Remark 1.10. Note that C(n, k) = C(n, n − k). (Why? Because to choose k

out of n is the same thing as choosing the complement.)

Example 1.11. The number of different poker hands (5 cards) drawn from a

normal pack of cards (containing 52 cards) is C(52, 5) =

P (52,5)

.

5!

Lemma 1.12. The number of subsets of an n-element set is 2n .

Proof. Let the set be {a1 , . . . , an }. A subset S of this set is determined by

choosing for each i whether ai ∈ S or ai ∈

/ S. By the multiplication principle there

are 2 × · · · × 2 = 2n choices, hence 2n subsets.

Corollary 1.13.

2n = C(n, 0) + C(n, 1) + · · · + C(n, n).

(Why? The left hand side is the total number of subsets, and the right hand side

is the number of subsets with 0 elements plus the number of subsets with 1 element,

etc.)

The numbers C(n, k) =

n

k

for k ≤ n are also known as the binomial coefficients

(on your calculator they may be denoted n Cr , Crn or n Cr ). There are numerous

algebraic identities involving these numbers!

Lemma 1.14. (i). (a + b)n =

Pn

k=0

C(n, k)ak bn−k whenever a and b commute.

(ii). C(n + 1, k) = C(n, k) + C(n, k − 1).

Proof. (i). (a + b)n = (a + b)(a + b) · · · (a + b). When we multiply this out

each term arises from picking either a or b in each bracket and multiplying them

together. The number of ways of getting ak bn−k is the number of ways of choosing k

3

of the n factors (then we pick a from these factors and b from the remaining n − k).

By definition, this number is C(n, k).

(ii). Let X = {1, . . . , n + 1}. Every subset Y ⊆ X where |Y | = k arises in one

of two ways:

(a) n + 1 ∈

/ Y , so Y is a subset of {1, . . . , n} of size k.

(b) n + 1 ∈ Y . In this case Y is determined by Y ∩ {1, . . . , n} which is a subset of

{1, . . . , n} of size k − 1.

There are C(n, k) possibilities in case (a), and C(n, k − 1) possibilities in case (b).

As cases (a) and (b) are mutually exclusive, C(n + 1, k) = C(n, k) + C(n, k − 1).

It is the second part of this lemma that gives us Pascal’s triangle.

n=0

1

n=1

1

n=2

1

n=3

2

1

n=4

1

n=5

1

..

.

1

3

4

1

3

6

5

..

.

10

..

.

1

4

10

..

.

1

5

..

.

1

..

.

Apart from the 1s along the edges, every entry is formed by adding together the two

numbers above it.

Lemma 1.15. For all positive integers r, n with r 6 n we have

r · C(n, r) = n · C(n − 1, r − 1).

Proof. We could prove this purely algebraically using the formula for C(n, r)

(this is an exercise). Instead let’s give a combinatorial proof.

Let X be an n-element set. Consider the set

def

S = {(x, A) | x ∈ A, A ⊆ X, |A| = r}.

We will count this set in two different ways, using the multiplication principle in

both cases.

Firstly, we can first choose A and then x. The number of choices for A is C(n, r)

and the number of choices for x, once A is chosen, is r. So |S| = C(n, r) · r.

Secondly, we can first choose x ∈ X and then A ⊆ X with |A| = r and x ∈ A.

The number of choices for x is n. Given x ∈ X we can choose A ⊆ X with |A| = r

and x ∈ A by choosing r − 1 elements from X {x} and then adding x to these to

4

obtain A. There are C(n − 1, r − 1) choices for such A. So |S| = n · C(n − 1, r − 1)

and therefore r · C(n, r) = n · C(n − 1, r − 1).

Example 1.16. How many different ice cream cones are there with 3 different

flavoured scoops of ice cream, where order doesn’t matter, if there are 10 different

possible flavours of ice-cream? How many are there if the order does matter?

Answer: If the order doesn’t matter, we want C(10, 3) =

10.9.8

3.2

= 120.

If the order does matter, the number we need is P (10, 3) = 10.9.8 = 720.

Before we move on, Lemma 1.12 gives us the total number of making a selection

from n objects, with no repetitions and without regard to order. What happens if

we do take the order into account?

Lemma 1.17. The total number of ordered selections, of different sizes without

repetitions, from n > 1 objects is

n

X

P (n, k) = be · n!c

k=0

(That is the greatest integer less than or equal to e · n!.)

Proof. It is obvious that the number of selections is

this is equal to e · n!, we shall use the fact that e =

1

0!

+

1

1!

Pn

k=0 P (n, k). To prove

+ 2!1 + . . .. The number

we are interested in is

n

X

P (n, k) =

k=0

=

=

=

=

n! n! n!

n!

+

+

+ … +

0!

1!

2!

n!

1

1

1

1

+ + + … +

n!

0! 1! 2!

n!

1

1

1

n! e −

−

−

− …

(n + 1)! (n + 2)! (n + 3)!

n!

n!

n!

+

+

+ …

n! · e −

(n + 1)! (n + 2)! (n + 3)!

1

1

1

+

+

+ … .

n! · e −

(n + 1) (n + 1)(n + 2) (n + 1)(n + 2)(n + 3)

5

So the number we want is an integer and is equal to n! · e less the error term (call

it E) inside the brackets. If we can show that E < 1 we will have finished. Well,
1
1
1
+
+
+ ...
(n + 1) (n + 1)(n + 2) (n + 1)(n + 2)(n + 3)
1
1
1
<
+
+
+ ...
2
n + 1 (n + 1)
(n + 1)3
E =
=
1
n+1
1−
1
n+1
=
1
6 1.
n
Example 1.18. Four people are having a picnic, when an ice-cream van arrives.
Some number between 0 and 4 of them go to queue up. How many distinct queues
are possible?
Solution We treat different orderings as different queues. In this case we need to
know the number of total permutations of between 0 and 4 objects from 4. This is
be · 4!c = 65.
We now add a little twist to the situation by allowing repetitions, meaning that
we can choose the same object more than once. Of course, we can consider this
scenario either with or without regard to order – it can get a bit fiddly! First we
consider the case where we select in order. In fact this is rather easy:
Lemma 1.19. Let n > 0 and k ≥ 0. The number of ways of selecting in order k

from n objects, with repetitions allowed, is nk .

Proof. For the first we have n choices, for the second n choices, . . . , and for

the k-th we have n choices. So altogether there are nk choices by the multiplication

principle.

One example of this sort is a piece of paper divided into k stripes, and we want

to colour each stripe with one of n colours. (We’re allowed to use the same colour

for different stripes.) This amounts to choosing k colours from n in a given order,

but with repetition allowed.

Another important class of example is that of occupancy problems, such as how

many ways are there of putting k distinguishable balls in n distinct boxes.

Example 1.20. How many ways are there to put 5 distinguishable balls into 3

distinct boxes?

Answer

Think of the balls as the numbers 1, 2, 3, 4, 5 and the boxes as A, B, C.

One way of making the assignment is putting ball 1 in box A, ball 2 in A, ball 3 in

6

C, ball 4 in B, ball 5 in A. This corresponds to the selection (in order) AACBA, of

5 (=k) from 3 (n) with repetitions allowed. By Lemma 1.19 there are 35 different

ways of doing this.

Now, things become a little more subtle when we want to choose k objects from

n, allowing repetitions, but without regard to order.

For example, suppose we wish to paint each of k canvases with one of n colours,

where, as before, we can choose the same colour twice, but now where the canvases

are identical (unlike the stripes in the example above). Notice that making choice

of paints is equivalent to deciding, for each of the n colours, how many canvases are

painted with that colour.

A corresponding occupancy problem is to place k indistinguishable balls in n

distinguishable boxes. Again, a choice here is equivalent to deciding, for each box,

how many of the balls are placed in it. (So this is different from Example 1.20,

as we now consider AACBA and ABACA to be the same choice, since the balls

are treated as indistinguishable.) The following result gives the general solution to

problems of this type:

Theorem 1.21. Let n > 0, k ≥ 0. The number of ways of selecting k objects

from n, without regard for order, and with repetitions allowed, is C(n + k − 1, k) =

C(n + k − 1, n − 1).1

The proof of this theorem will be in two steps. The first is:

Lemma 1.22. Let n > 0, k ≥ 0. The number of ways of selecting (without regard

for order) k out of n distinct objects, with repetitions allowed, is equal to the number

of solutions to e1 + · · · + en = k where the ei are nonnegative integers. That is to

say, quantity we want is the number of (ordered) n-tuples (e1 , . . . , en ) of nonnegative

P

integers such that ni=1 ei = k.

Proof. Let {x1 , . . . , xn } be our set of n objects. Consider some selection k

from these, without regard for order, and with repetitions allowed. Suppose that ei

is the number of times xi is chosen. Clearly then, because we have chosen k objects

P

altogether, we must have ni=1 ei = k.

P

Conversely, any tuple of nonnegative integers e1 , . . . , en where ni=1 ei = k corresponds to a unique choice of k objects from {x1 , . . . , xn }, by interpreting ei as the

number of times xi is chosen.

1The

corresponding occupancy problem is placing k indistinguishable balls into n distinguish-

able boxes. Note that the boxes in the occupancy problem play the role of the objects in the

corresponding selection problem: You make an unordered selection of k boxes from the total of n.

7

The second step is:

Lemma 1.23. The number of solutions to e1 + · · · + en = k where ei are nonnegative integers is C(n + k − 1, k) = C(n + k − 1, n − 1).

Proof. We use the bijection principle to prove this: we will give a bijection

onto another set which we can count easily. The other set is the set of sequences of

k stars (∗) and n − 1 bars (|). The bijection is given by

(e1 , . . . , en ) 7→ |∗ ·{z

· · ∗} | ∗| ·{z

· · ∗} | · · · · · · | |∗ ·{z

· · ∗}

e1 stars e2 stars

en stars

It is easy to see that this map is a bijection. Since the star-bar sequences have total

length n + k − 1 and are completely determined by where we choose the k stars,

there are C(n + k − 1, k) of them.

The previous two lemmas yield Theorem 1.21.

Example 1.24. How many ways are there to place 5 indistinguishable balls into

3 distinct boxes?

Answer:

The quantity we want is the number of ways of choosing 5 objects from

3 without regard to order and with repetitions allowed. So we may apply Theorem

1.21, taking n = 3 and k = 5.

This gives C(3 + 5 − 1, 2) = C(7, 2) =

7!

5!.2!

=

7.6

2

= 21.

Example 1.25. Using Lemma 1.23 we can now say exactly how many nonnegative integer solutions there are to equations like

x1 + x2 + x3 + x4 + x5 = 20.

We get that there are C(5 + 20 − 1, 5 − 1) = C(24, 4) solutions.

We can also now say exactly how many non-negative integer solutions there are

to the inequality

x1 + x2 + x3 + x4 + x5 < 20.
First note that as all the xi are integers this is the same as asking how many nonnegative integer solutions are there to:
x1 + x2 + x3 + x4 + x5 6 19.
8
We change this inequality to an equation by adding a slack variable x6 . The idea
being that x6 is the difference between 19 and x1 + x2 + x3 + x4 + x5 . This difference
has to be non-negative as the sum of the xi ’s is less than or equal to 19. (It’s equal
exactly when x6 = 0.) Thus the number of non-negative integer solutions there are
to the orginal inequality is the same as the non-negative integer solutions to the
equality
x1 + x2 + x3 + x4 + x5 + x6 = 19.
which is C(6 + 19 − 1, 6 − 1) = C(24, 5).
9
CHAPTER 2
Partitions of sets, Bell numbers, and Stirling numbers.
See Chapter 4 and 5 of Allenby–Slomson for more information about Stirling
numbers and Chapter 6 for partitions.
Definition 2.1. A (finite) partition of a set X is an (unordered) collection
{A1 , . . . , Ak } of nonempty, pairwise disjoint, subsets A1 , . . . , Ak of X whose union
is X.
To say the same things in symbols: Ai 6= ∅ for all i = 1, . . . , k, as well as
S
Ai ∩ Aj = ∅ for i 6= j, and ki=1 Ai = X.
The number of parts of the partition is by definition k.
Example 2.2. If X = {1, 2, 3} the partitions of X are:
n
o n
o n
o n
o n
o
{1}, {2}, {3} , {1, 2}, {3} , {1, 3}, {2} , {2, 3}, {1} , {1, 2, 3} .
(Note that the partition {{1, 2}, {3}} is the same as the partition {{3}, {1, 2}}.)
Definition 2.3. (i) The Bell number, B(n) is the number of partitions of an
n-element set. (Also we take B(0) = 1 by convention.)
(ii) The Stirling number, S(n, k) is the number of partitions of an n-element set into
k parts.
Example 2.4. By taking n = 3 and referring to the previous example we see
that B(3) = 5, S(3, 1) = 1, S(3, 2) = 3 and S(3, 3) = 1.
The sequence of Bell numbers begins 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147,
115975, . . .
Note that S(0, 0) = 1 and S(n, k) = 0 for k > n, and S(n, 0) = 0 and S(n, 1) =

S(n, n) = 1 for n ≥ 1. Now, the following is obvious by definition:

P

Lemma 2.5. We have B(n) = nk=0 S(n, k).

The aims of this chapter and the next are to find formulae for these quantities

and to relate them to counting and occupancy problems.

Lemma 2.6. The number of ways of distributing b distinct balls among c indistinguishable boxes, with no box being empty is S(b, c).

10

Proof. Suppose we have some distribution of the b balls with every box being

nonempty. Label the boxes 1, . . . , c. Let Ai be the set of balls in box i. Then clearly

the Ai are all nonempty, and are pairwise disjoint (no ball goes in more than one

box), and A1 ∪· · ·∪Ac is the original set of b balls. This establishes that {A1 , . . . , Ac }

is a partition of the set of b balls into c parts, and it is clearly independent of the

labelling of the boxes.

We give the inverse to the above correspondence. Suppose {A1 , . . . , Ac } is a

partition of the set of b balls into c parts. Then if we put all the balls in Ai into

the ith box, we have found a way to distribute the b balls among c non-empty

boxes. The indistinguishability of the boxes guarantees that this is independent of

the labelling of the sets in the partition. (For instance {A1 , A2 , . . . , Ac } represents

the same partition as {A2 , A1 , . . . , Ac }, and also gives rise to the same distribution

of balls into boxes because we cannot distinguish between box 1 and box 2.)

What if we wish to dispense with the no empty boxes clause? All we can do is

the following:

Corollary 2.7. The number of ways of distributing b distinct balls among c

indistinguishable boxes (allowing empty boxes) is S(b, 0) + S(b, 1) + . . . + S(b, c).

Definition 2.8. An equivalence relation on a set X is a binary relation R on

X which is reflexive, symmetric, and transitive. That is to say:

(i) xRx for all x ∈ X

(ii) xRy implies yRx for all x, y ∈ X

(iii) if xRy and yRz then xRz for all x, y, z ∈ X.

Furthermore, the equivalence class of y ∈ X under R is the set

[y]R := {x ∈ X : xRy}.

Example 2.9. Let X = Z (the set of integers). Define xRy if and only if x − y

is divisible by 2.

In this case R has two equivalence classes: the set of even numbers and the set

of odd numbers. Notice also that this pair comprise a partition of X.

For another example, consider the nine cells of a 3 × 3 grid. Given two cells x

and y, say xRy if there is a symmetry of the grid taking x to y. Here there are three

equivalence classes: the four corner cells, the four central edge cells, and the single

central cell.

The following generalises this observation, and establishes that partitions and

equivalence relations are essentially the same thing.

11

Proposition 2.10. If R is an equivalence relation on a set X, then the collection

of equivalence classes comprises a partition of X, and every partition of X arises

this way. This gives a 1-1 correspondence between equivalence relations on X and

partitions of X.

Proof. (Sketch — filling in the details is an exercise on coursework 2.) Given

an equivalence relation R on X, show that any two equivalence classes are either

equal or disjoint, that no equivalence class is empty, and that every element of X

lies in some equivalence class. Hence the set of distinct equivalence classes forms a

partition of X.

Conversely, if {A1 , A2 , . . . , Ak } is a partition of X, then define the relation R on

X by xRy if x and y are in the same member of the partition (i.e. in the same Ai ).

Then prove that R is an equivalence relation on X.

Finally, check the above maps are each others inverse.

P

Theorem 2.11. For n ≥ 1, B(n) = nk=1 C(n − 1, k − 1) · B(n − k).

Proof. Let X = {1, . . . , n}. Any partition P of X can be constructed as follows:

first pick a subset Y of X containing n. Then choose a partition {A1 , . . . , A` } of

X Y , and then put P = {A1 , . . . , A` , Y }.

Now (for fixed k) there are C(n − 1, k − 1) ways of choosing a subset Y of X

which has cardinality k and contains n. For each such choice of Y there are B(n−k)

partitions of X Y .

So, using the multiplication principle, the number of partitions of X where n lies

in a set of size k is C(n − 1, k − 1) · B(n − k). The final step is to sum this over all

P

k, giving us nk=1 C(n − 1, k − 1)B(n − k).

Proposition 2.12. For n > 0 and k > 1 we have S(n + 1, k) = k · S(n, k) +

S(n, k − 1).

Proof. This is a similar style of proof to that of the previous theorem. Let

X = {1, . . . n + 1}. Now, any partition of X into k parts arises in one of the

following two ways:

(i) Choose a partition {A1 , . . . , Ak } of {1, . . . , n} into k parts, then add n + 1

to one of the Ai to form a partition of X into k parts. There are S(n, k) · k

ways this can be done (using the multiplication principle).

(ii) Choose a partition {A1 , . . . , Ak−1 } of {1, . . . , n} into k −1 parts, then adjoin

{n + 1} to obtain the partition {A1 , . . . , Ak−1 , {n + 1}} of X into k parts.

There are S(n, k − 1) ways this can be done.

12

Furthermore these two are mutually exclusive, since (ii) arises precisely when

{n + 1} is one of the sets in the partition. Thus the total number of partitions of X

into k parts is S(n, k) · k + S(n, k − 1).

Proposition 2.13. The number of functions from an n-element set to a kelement set is k n .

Proof. Let the sets be X = {a1 , . . . , an }, Y = {b1 , . . . , bk }. A function f from

X to Y is determined by deciding the value of f (ai ) for each i. There are k choices for

f (a1 ). For each such choice there are k choices for f (a2 ), etc. So by multiplication

principle the number of choices is k × · · · × k = k n .

Notice that this is the same as the occupancy problem of distributing n distinguishable balls between k distinct boxes. This is also the same as selecting in order

n from k distinct objects allowing repetitions. (see Lemma 1.19, be careful about

the roles of n and k.)

What about the number of surjective functions from a set of size n to a set of

size k?

Lemma 2.14. The number of surjective (or onto) functions from an n-element

set to a k-element set is k!S(n, k).

Proof. Let A = {a1 , . . . , an } and B = {b1 , . . . , bk }. Observe that a surjective

function from A to B is given by a partition of A into k parts together with an ordering (or arrangement) of those parts. Namely the first part is {x ∈ A | f (x) = b1 },

second part is {x ∈ A | f (x) = b2 }, etc. Hence the number of surjective functions

from A to B is precisely the number of partitions of A into k parts multiplied by

the number of possible arrangements of k objects, which is S(n, k) × k!.

Corollary 2.15. The number of ways of distributing n distinct balls among k

distinct boxes leaving no box empty, is k!S(n, k).

Remark 2.16. The number of injective functions from a set of size k to a set of

size n, where k ≤ n is P (n, k). See Exercise 1, Workshop 2.

13

CHAPTER 3

The Inclusion–Exclusion principle and applications.

See also Chapter 4 of Allenby–Slomson and/or Chapter 2 of Slomson’s first

edition for more on Inclusion-Exclusion.

Our aim now is to find a formula for the Stirling numbers S(n, k). See Corollary

3.4 below. We will make use of the so-called inclusion-exclusion principle, which

also has many other uses.

First, recall the easy fact that if A and B are finite sets, then

|A ∪ B| = |A| + |B| − |A ∩ B|.

Similarly

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

We can now give the general formula:

Theorem 3.1 (The Inclusion–Exclusion Principle Theorem). Given finite subsets A1 , . . ., An of some given set,

|A1 ∪ · · · ∪ An | =

n

X

k=1

!

X

(−1)k+1

|Ai1 ∩ · · · ∩ Aik | .

1≤i1 1, an integer, (iv) B(4).

2

1

1 X

1

(−1)2−j C(2, j)j 3 =

−C(2, 1) · 1 + C(2, 2) · 23 = [−2 + 8] = 3.

2! j=1

2

2

(i) S(3, 2) =

4

1 X

(ii) S(8, 4) =

(−1)4−j C(4, j)j 8

4! j=1

1

−C(4, 1) · 1 + C(4, 2) · 28 − C(4, 3) · 38 + C(4, 4) · 48

24

1

1

−4 + 6 · 28 − 4 · 38 + 48 =

[1532 − 26, 244 + 65, 536] = 1, 701.

=

24

24

=

2

1 X

1

(iii) S(n, 2) =

(−1)2−j C(2, j)j n = [−C(2, 1) · 1 + C(2, 2) · 2n ]

2! j=1

2

=

(iv) B(4) =

1 n

[2 − 2] = 2n−1 − 1.

2

n

X

S(4, k) = S(4, 1)+S(4, 2)+S(4, 3)+S(4, 4)

k=1

16

We know S(4, 1) = 1, S(4, 2) = 23 − 1, by (iii). Also S(4, 4) = 1 so we need to

calculate S(4, 3).

3

1 X

S(4, 3) =

(−1)3−j C(3, j)j 4

3! j=1

1

C(3, 1) · 1 − C(3, 2) · 24 + C(3, 3) · 34

6

1

= [3 − 3 · 16 + 81] = 6.

6

So B(4) = 1 + 7 + 6 + 1 = 15.

=

Example 3.6. How many hands of 5 cards from a normal 52 card deck are there

for which there is at least one suit contributing no cards?

We let VS , VH , VD and VC be the five-card hands with no spades, hearts, diamonds or clubs respectively. We want to calculate |VS ∪ VH ∪ VD ∪ VC |. Using

inclusion-exclusion this is:

|VS |+|VH |+|VD |+|VC |−|VS ∩VH |−|VS ∩VD |−|VS ∩VC |−|VH ∩VD |−|VH ∩VC |−|VD ∩VC |

+|VS ∩VH ∩VD |+|VS ∩VH ∩VC |+|VS ∩VD ∩VC |+|VH ∩VD ∩VC |−|VS ∩VH ∩VD ∩VC |.

Now each suit has 13 cards in it so |VS | = C(39, 5) = 575, 757, we pick 5 cards from

the 39 cards which aren’t spades. Similarly, |VH | = |VD | = |VC | = 575, 757.

A hand in VS ∩ VH consists of 5 cards drawn from the 26 cards which are neither

spades nor hearts so |VS ∩VH | = C(26, 5) = 65, 780. Similarly, |VS ∩VD | = |VS ∩VC | =

|VH ∩ VD | = |VH ∩ VC | = |VD ∩ VC | = 65, 780.

Similarly |VS ∩ VH ∩ VD | = |VS ∩ VH ∩ VC | = |VS ∩ VD ∩ VC | = |VH ∩ VD ∩ VC | =

C(13, 5) = 1, 287. (5 cards from 13 cards).

Also, VS ∩ VH ∩ VD ∩ VC = ∅ as a hand must contain cards from at least one suit.

So, but noting that there are C(4, 1) ways to get one set by itself, C(4, 2) ways

to get 2 sets, C(4, 3) ways to get 3 sets and C(4, 4) ways to get 4 sets we have:

|VS ∪ VH ∪ VD ∪ VC | = C(4, 1)C(39, 5) − C(4, 2)C(26, 5) + C(4, 3)C(13, 5) − C(4, 4) · 0

= 4 · 575, 757 − 6 · 65, 780 + 4 · 1, 287 = 1, 913, 496.

17

CHAPTER 4

Partitions of numbers.

See Chapter 6 of Allenby-Slomson and Chapter 3 of Slomson (first edition).

Definition 4.1. Let n be an integer > 0. By a partition of the number n we

mean a representation of n as a sum of positive integers, where the order does not

matter (and repetition is allowed).

So (2, 2, 1, 3) and (2, 3, 1, 2) count as the same partition of 8. We may also write

this as 2 + 2 + 1 + 3.

The numbers that occur in the partition are called the parts or the sizes of parts.

Our convention will be to write the parts in decreasing order: (3, 2, 1) for the

partition representing 6 = 3 + 2 + 1. So an equivalent definition of a partition of the

number n is a decreasing sequence of positive integers which sum to n:

(n1 , n2 , . . . , nk ) where n1 ≥ · · · ≥ nk ≥ 1 and

k

X

ni = n.

i=1

The number of parts k is called the length of the partition.

Example 4.2. The partitions of 3 are (3), (2, 1) and (1, 1, 1).

The partitions of 5 are:

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

Remark 4.3. A partition of the number n does not mean the same thing as

a partition of a set of size n. But what is the relationship? Take a partition

{A1 , . . . , Ak } of a set X where |X| = n. Arrange the parts Ai such that |A1 | ≥

|A2 | ≥ · · · |Ak | ≥ 1. Then |A1 | + |A2 | + · · · + |Ak | = n so (|A1 |, |A2 |, . . . , |Ak |) is

a partition of the number n. All partitions of n arise this way. But two distinct

partitions of an

n n elemento set can

n give rise oto the same partition of the number n.

For instance, {1, 2}, {3} and {1, 3}, {2} each correspond to the partition (2, 1)

of 3.

Suppose {A1 , . . . , Ak } and {B1 , . . . , B` } are partitions of a set X of size n, both

ordered by size. We could say they are equivalent if k = ` and |Ai | = |Bi | for all i.

Then equivalent partitions of X correspond to the same partition of n. Hence the

number of partitions of n is the number of equivalence classes of partitions of X.

18

Remark 4.4. The number of partitions of the number n with at most k parts

coincides with the number of ways of distributing n indistinguishable balls among

k indistinguishable boxes. (Why?)

Definition 4.5. If n and k are integers > 0, then

(i) p(n) is the number of partitions of n.

(ii) pk (n) is the number of partitions of n with at most k parts.

(iii) By convention p(0) = 1, pk (0) = 1 for k ≥ 0 and p0 (n) = 0 for n ≥ 1.

The sequence of partition numbers p(n) begins 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42,

56, 77, 101, 135, 176, 231, 297, 385, 490, . . .

Remark 4.6 (Non-examinable). A very nice approximate expression for p(n)

was provided by Hardy and Ramanujan in 1918:

√ 2n

1

p(n) ∼ √ eπ· 3

4n 3

This is a limiting value in the sense that if you divide p(n) by this expression, the

result tends to 1 as n → ∞. We shall not get this far!

Lemma 4.7. Let n ≥ 0. Then

(a) p1 (n) = 1.

(b) For all k ≥ n, we have pk (n) = p(n).

(c) p2 (n) = b n2 c + 1,

where bxc is the largest integer ≤ x.

Proof. (a) is obvious, and (b) is true because if k ≥ n then any partition of

the number n has at most k parts.

(c) For n = 0 it’s obvious, so assume n > 1. By (a) there is exactly one partition

of n with one part: (n). The partitions of the number n with two parts are clearly

(n − 1, 1), (n − 2, 2), . . . , (n − b n2 c, b n2 c). So altogether there are b n2 c + 1 partitions

of n with at most two parts.

Definition 4.8. We let qk (n) be the number of partitions of n with all parts

(or summands) at most k.

Example 4.9. For example q5 (5) = p(5).

Also, q1 (5) = 1 (the only partition being (1, 1, 1, 1, 1)).

Theorem 4.10. For all integers k, n > 0, pk (n) = qk (n).

Proof. This theorem follows from an interesting duality for partitions, which

can itself be seen via so-called Ferrers diagrams. We start with an example.

19

The partition (7, 4, 3, 3, 1) of 18 can be represented by the following diagram of

dots:

• • • • • • •

• • • •

• • •

• • •

•

The first row is 7 dots, second row is 4 dots etc. The total number of dots is (of

course) 18. Note that the number of rows in the diagram is 5 which is the length

of the partition. Also, the number of columns is 7 which is the largest part of the

partition.

Here is the key insight: we can also read the diagram vertically rather than

horizontally, to obtain another partition of 18, namely (5, 4, 4, 2, 1, 1, 1). We call

this the dual (or conjugate or transpose) of the original partition.

We can do this in general: given a partition π of the number n, write down its

Ferrers diagram. Formally, if π = (n1 , n2 , . . . , nk ), then the Ferrers diagram consists

of a grid of k rows. In the ith row, the first ni spaces contain dots, and the remaining

spaces are empty.

Once again, reading the diagram vertically gives another partition of n. We

denote this π ∗ . Note that (π ∗ )∗ = π, and the map taking π to π ∗ gives a permutation

of the set of partitions of n.

Let us emphasize that π has k parts if and only if the largest part of π ∗ is k.

Similarly, π has at most k parts if and only if all the parts of π ∗ are ≤ k.

So

∗

induces a bijection between the set of partitions of n with at most k parts,

and the set of partitions of n with all parts ≤ k. Thus pk (n) = qk (n).

Theorem 4.11. Let 1 ≤ k ≤ n. Then

(a) pk (n) = pk−1 (n) + pk (n − k), and

(b) qk (n) = qk−1 (n) + qk (n − k).

Proof. By the previous theorem, it suffices to prove (a). Let (n1 , . . . , n` ) be a

partition of n into l 6 k parts. We have two cases:

Case (i). ` < k. Then the partition is already a partition of n into at most k − 1
parts. There are pk−1 (n) possibilities here.
Case (ii). ` = k, i.e. the partition has exactly k parts, meaning n1 , . . . , nk ≥ 1. But
then (n1 − 1) + (n2 − 1) + · · · + (nk − 1) = n − k. Now, some of these summands
may be zero. Deleting these leaves us with a partition of n − k into at most k parts.
There are precisely pk (n − k) possibilities here.
20
Now add up the possibilities for case (i) and for case (ii) to get the answer.
Before the next theorem let us first note some properties of b nk c. Assume 1 ≤
k ≤ n. We can write n = sk + r where s, r ∈ N and 0 6 r < k. Dividing by k we
get
where 0 6
r
k
< 1. So
r
k
n
r
=s+
k
k
is the fractional part of
n
k
and s = b nk c. By noting that
r = n − sk we get 0 6 n − sk < k. Also observe that n − (s − 1)k = n − sk + k =
r + k > k.

Theorem 4.12. Let 1 ≤ k ≤ n. Let s = bn/kc. Then

(a) qk (n) = qk−1 (n) + qk−1 (n − k) + qk−1 (n − 2k) + · · · + qk−1 (n − sk).

(b) pk (n) = pk−1 (n) + pk−1 (n − k) + pk−1 (n − 2k) + · · · + pk−1 (n − sk).

Proof. It is enough to prove (a), by Theorem 4.10. Iterating Theorem 4.11(b)

yields:

qk (n) = qk−1 (n) + qk (n − k)

qk (n − k) = qk−1 (n − k) + qk (n − 2k)

..

.

..

.

..

.

qk (n − (s − 1)k) = qk−1 (n − (s − 1)k) + qk (n − sk).

As remarked above n − sk < k, and thus no partition of n − sk can have a part of
size k. So qk (n − sk) = qk−1 (n − sk). Putting all this together:
qk (n) = qk−1 (n) + qk−1 (n − k) + · · · + qk−1 (n − (s − 1)k) + qk−1 (n − sk).
Remark 4.13. If we define p(k, n) to be the number of partitions of n of length
k and q(k, n) to be the number of partitions of n with largest part k, then
(i) p(0, 0) = 1, p(0, n) = 0 for n > 1, and p(k, n) = 0 for k > n > 0,

(ii) p(k, n) = q(k, n) for all k, n > 0,

(iii) p(k, n) = p(k − 1, n − 1) + p(k, n − k) for 1 6 k 6 n.

Assertion (i) is obvious, (ii) is Coursework 2 Question 4(i) and (iii) is Workshop 2

Question 5(i).

21

CHAPTER 5

Generating functions. Euler’s generating function for

partition numbers.

1. Functions and Power Series.

We shall consider power series both from an algebraic and from a functional

point of view in order to solve combinatorial problems.

Question 5.1. Consider the series given by the product:

(1 + x + x2 + x3 + · · · )(1 + x2 + x4 + x6 + · · · ) .

(5.1)

What is the coefficient of x7 in this product?

Answer. When we multiply out we obtain the following terms (also called summands) of degree 7:

x · x 6 , x 3 · x 4 , x 5 · x 2 , x 7 · x0 .

So the coefficient of x7 is 4.

Question 5.2. In how many ways can you write down 7 as the sum l + m of

nonnegative integers l, m where m is even?

Answer. 1 + 6, 3 + 4, 5 + 2, 7 + 0.

Note the correspondence! In fact we can see that the coefficient of xn in equation

(5.1) is the number of ways of representing n as the sum l+m of nonnegative integers

such that m is even. In other words, if an is the number of ways of writing n as the

sum of two nonnegative integers where the second is even, then

2

3

2

4

6

(1 + x + x + x + · · · )(1 + x + x + x + · · · )

=

∞

X

an x n .

(5.2)

n=0

Now, to obtain combinatorial results we consider power series in two ways: algebraically and functionally.

22

The Algebraic Approach. Here we view the series

a0 + a1 x + a2 x 2 + · · ·

∞

X

=

an x n

(5.3)

n=0

as the infinite sequence

(a0 , a1 , a2 , · · · )

=

(an )n>0

(5.4)

Note. A polynomial corresponds to the series in (5.3) with only finitely many

nonzero coefficients and so in (5.4) to a finite sequence.

Important Point. Coefficients of power series themselves obtained by multiplication and addition of power series can be obtained by multiplication and addition of

the corresponding sequences as set out below.

Addition.

(a0 , a1 , a2 , · · · ) + (b0 , b1 , b2 , · · · )

=

(a0 + b0 , a1 + b1 , a2 + b2 , · · · )

Multiplication.

(a0 , a1 , a2 , · · · ) ∗ (b0 , b1 , b2 , · · · )

where cn =

Pn

i=0

=

(c0 , c1 , c2 , · · · )

ai bn−i . Indeed, multiplying a0 +a1 x+a2 x2 +· · · and b0 +b1 x+b2 x2 +

· · · and gathering terms/summands of the same degree we see that the coefficient

of xn is:

a0 bn + a1 bn−1 + · · · + an b0

=

n

X

ai bn−i .

i=0

The Functional Approach. We regard a power series as a function of x. Thus,

in equation (5.2) we have

f (x) · g(x) = h(x)

(5.5)

P

P∞ 2n

P

n

n

where f (x) = ∞

and h(x) = ∞

n=0 x , g(x) =

n=0 x

n=0 an x . This equation

now tells us that the product f (x)·g(x) is the same as h(x) if both f (x) and g(x) are

defined. Thus equation (5.2) makes sense provided f (x) and g(x) are both defined

for some x ∈ R (i.e. if they both have radius of of convergence > 0.)

For example in equation (5.2) f (x) and g(x) correspond to geometric series and

so converge for any x ∈ R such that |x| < 1. So their product—i.e. the series
corresponding to h(x)—also converges for such x.
23
Combining the Algebraic and Functional Approaches. A standard theoP
n
rem (that we could easily prove) tells us that if, for some R > 0, the series ∞

n=0 an x

P

n

and ∞

n=0 bn x both converge for all x ∈ R with |x| < R, then
∞
X
an x n =
n=0
∞
X
bn xn for all x with |x| < R
⇔
an = bn for all n > 0.

(5.6)

n=0

Thus (under such conditions) an equation such as (5.2) is true regarded as a functional equation if and only if it is true when regarded as an algebraic equation

between (formal) power series /infinite sequences.

We often use equation (5.6) to argue that if two functions are the same, then the

coefficients in the power series represented by these functions must match exactly.

i.e. we use the method of equating coefficients.

2. Generating Functions.

Definition 5.3. The generating function of the sequence (an )n>0 is the function

x 7→

∞

X

an x n

n=0

(i.e. f (x) such that f (x) =

P∞

n=0

an xn ).

Note. We only use Definition 5.3 when

P∞

n=0

an xn has positive radius of con-

vergence, i.e. is defined for some x 6= 0, in which case we can use the method of

equating coefficients.

Example 5.4. Find the generating function of the (finite) sequence {C(m, n)}m

n=0 .

P

n

m

Answer. By the binomial theorem m

n=0 C(m, n)x = (1 + x) . Hence f (x) =

(1 + x)m is the generating function of the sequence {C(m, n)}m

n=0 .

(Remark. f (x) is clearly convergent. Why?)

1

is the generating function

1−x

where an = 1 for all n > 0—i.e. the constant sequence

Example 5.5. Show that the function f (x) =

of the sequence (an )n>0

(1, 1, 1, . . . ).

P

n

Answer. The geometric series ∞

n=0 x converges for any x ∈ R such that |x| < 1
P
1
n
and, for this range of values ∞
. Note that this
n=0 x = f (x) where f (x) =
1−x
P∞
series is of the form n=0 an xn with an = 1 for all n > 0. Hence the result.

Example 5.6. Determine the generating function of the sequence (n)n>0 .

24

Answer. We know that we can compute the derivative of a power series over its

domain of convergence by differentiating the series term by term. Thus, as

1

1−x

∞

X

=

xn

for x such that |x| < 1 ,
(5.7)
n=0
∞
X
1
by differentiating both sides of equation (5.7) we see that
=
nxn−1 . So
2
(1 − x)
n=0
x
(1 − x)2
∞
X
=
nxn
for x such that |x| < 1 .
n=0
x
Thus g(x) =
is the generating function for the sequence {n}.
(1 − x)2
Example 5.7. We can obtain the generating function f (x) of
1
n(n + 1) n>0

2

by

first finding the generating function h(x) for (n2 )n>0 (See Exercise 3 on Coursework

3) so that we get f (x) = 21 (h(x) + g(x)) where g(x) is the generating function for

(n)n>0 from above.

Alternatively we note that 21 n(n + 1) = 1 + 2 + · · · + n so that

1

n(n + 1) n>0

2

is the

sequence (an )n>0 where:

a0 = 0 and an+1 = an + (n + 1) for all n > 0.

Then

f (x) =

∞

X

an x n .

n=0

Multiplying the equation an+1 = an + (n + 1) by xn and summing we get:

∞

X

an+1 x

n

=

∞

X

n=0

n

an x +

n=0

n=0

However

∞

X

∞

X

nx +

n=0

∞

an+1 x

n

n

∞

X

xn .

n=0

∞

1X

1X

1

=

an+1 xn+1 =

an xn = f (x)

x n=0

x n=0

x

where we note that the second to last equality holds due to the fact that a0 =

1

0(0

2

+ 1) = 0. Thus, from these equations we deduce that:

1

x

1

f (x) = f (x) +

+

2

x

(1 − x)

1−x

1

= f (x) +

.

(1 − x)2

Hence

f (x) =

x

.

(1 − x)3

25

(5.8)

3. Euler’s generating function for partition numbers.

In this section we aim to solve the following type problem.

Problem (∗). Given an integer n > 0, is the number of ways of writing n as the

sum of odd positive integers the same as the number of ways of writing n as the

sum of positive integers that are all different?

Question 5.8. Check that the solution to Problem (∗) is yes for n = 7.

Answer. There are five partitions of 7 into parts that are all odd as follows:

7, 5 + 1 + 1, 3 + 3 + 1, 3 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1

and there are five partitions of 7 into distinct parts:

7, 6 + 1, 5 + 2, 4 + 3, 4 + 2 + 1 .

We will solve Problem (∗) in general by showing that the generating functions

for the sequences corresponding to these two types of numbers are identical.

Our next question exemplifies our approach.

Question 5.9. What is the coefficient of x89 in the series:

(1 + x3 + x6 + x9 + · · · )(1 + x8 + x16 + x24 + · · · )

(5.9)

Answer. By inspection we obtain x89 in the following four ways,

x9 · x80 , x33 · x56 , x57 · x32 , x81 · x8 ,

and hence the coefficient of x89 in the series is 4. This is the same as the number

of ways of writing 89 in the form 3m + 8n where m and n are positive integers. I.e.

the number of partitions of 89 using only parts of size 3 and 8.

Remark 5.10. So the general observation here is that a partition π = (n1 >

n2 > · · · > nk > 1) of n, can also be written in ascending order and then in

“exponential form”:

1, . . . , 1 , 2, . . . , 2 · · · · · · = 1m1 2m2 · · · ,

| {z } | {z }

m1 copies

m2 copies

where the mi , 1 6 i 6 n1 , are integers > 0 satisfying

Pn1

i=1

i · mi = n. Here mi = 0

means that i does not occur as a part in π. E.g. (4, 4, 2, 1, 1, 1) = 13 2 42 = 13 21 30 42 .

26

Now, we easily generalise the example in Question 5.9.

All Partitions. Since a partition of positive integer n may use parts of any size

1 6 t 6 n, a series whose coefficients count all the partitions of n (for whichever n

we choose) must be the infinite product of (all) infinite series corresponding to parts

of size 1, 2, 3, . . . Indeed the following result gives us the generating function for the

sequence p(n) n>0 of partition numbers. (Remember that p(0) = 1 by convention.)

Theorem 5.11 (Euler). If P (x) =

the sequence p(n) n>0 , then

P∞

n=0

p(n)xn is the generating function for

P (x) = (1 + x + x2 + x3 + · · · )(1 + x2 + x4 + x6 + · · · )(1 + x3 + x6 + x9 + · · · ) · · ·

=

∞

Y

k

(1 + x + x

2k

+x

3k

+ ···) =

k=1

∞

Y

1

.

(1 − xk )

k=1

Proof. Note firstly that, to compute the coefficients of xn in the first (or second)

expression for P (x), we do not need to consider factors (1 + xk + x2k + · · · ) of the

product where k > n. Hence, when multiplying out, each copy of xn arises as

xn = (x1 )m1 × (x2 )m2 × · · · × (xn )mn

(5.10)

where 0 6 mi 6 n for all1 1 6 i 6 n and

1 · m1 + 2 · m2 + · · · + n · mn = n .

(5.11)

So in the i-th factor we pick the (mi + 1)-th term. It follows that the coefficient

of xn in P (x) is the number of tuples (m1 , m2 , . . . , mn ) as above. By Remark 5.10,

this is the number of partitions of n.

Remark. It is not hard to show that the infinite product in Theorem 5.11

Q

converges for |x| < 1. A series product ∞
k=1 uk makes sense purely algebraically if
(1) all but finitely many uk ’s have constant term one and (2) the degree of the first
nonconstant term of uk tends to infinity when k → ∞. The latter can be rephrased
as saying that each power xn , n > 1, occurs in only finitely many uk ’s with nonzero

coefficient.

Now for some examples.

1Note,

for example, that the only case when we have mi = n for some i is when i = 1, in

which case mj = 0 for all 1 < j 6 n. On the other hand mn ∈ {0, 1} and in the case when mn = 1
clearly mk = 0 for all 1 6 k < n.
27
Example 5.12. Evaluate p(n) for 1 6 n 6 5.
Q
k
2k
3k
Answer. We restrict ourselves to terms in ∞
k=1 (1 + x + x + x + · · · ) of degree
at most 5. (Make sure at this point that you understand why!) I.e. the product
(1 + x1 + x2·1 + x3·1 + x4·1 + x5·1 )(1 + x2 + x2·2 )(1 + x3 )(1 + x4 )(1 + x5 ) .
Now, rewriting this product as a sum we see that—when we truncate the sum to
show only the first six terms—we have
1 + x + 2x2 + 3x3 + 5x4 + 7x5
since, for example there are 7 individual terms of degree 5 in the sum2:
x5 , x2 · x3 , x1 · x4 , x1 · x2·2 , x2·1 · x3 , x3·1 · x2 , x5·1
(and a similar analysis gives the other coefficients). Thus we see that:
p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, and p(5) = 7 .
Reminder. In Problem (∗) we asked whether, for any n > 0 the number of ways

podd (n) of writing n as the sum of odd positive integers is the same as the number

of ways pdis (n) of writing n as the sum of integers that are all distinct.

Definition. Having defined podd (n) and pdis (n) as above, define Podd (x) and

Pdis (x) to be the generating functions for the sequences podd (n) n>0 and pdis (n) n>0 .

Lemma 5.13. Let Podd (x) and Pdis (x) be the generating functions defined above.

Then the following are true.

1

Podd (x) =

,

(1 − x)(1 − x3 )(1 − x5 ) · · ·

(a)

2

3

i.e. Podd (x) =

t=1

1

.

(1 − x2t−1 )

∞

Y

(1 + xt ) .

i.e. Pdis (x) =

4

Pdis (x) = (1 + x)(1 + x )(1 + x )(1 + x ) · · · ,

(b)

∞

Y

t=1

Proof. • podd (n) is the number of partitions of n into odd parts so the gener

ating function for the sequence podd (n) n>0 is obtained by taking the factors in the

product in Theorem 5.11 corresponding to parts of odd size. So

∞

Y

Podd (x) =

t

2t

(1 + x + x + · · · ) =

t=1

t>1, t odd

2Written

1

2·2

x ·x

0

out in full this is: x0 · x0 · x0 · x0 · x5 ,

0

0

·x ·x ·x , x

2·1

0

3

0

∞

Y

0

3·1

·x ·x ·x ·x , x

2

1

.

(1 − x2t−1 )

x0 · x2 · x3 · x0 · x0 ,

0

0

0

·x ·x ·x ·x , x

5·1

0

x1 · x0 · x0 · x4 · x0 ,

0

· x · x · x0 · x0 .

Note also that these terms correspond (respectively) to (all) the partitions of 5 as follows: (5),

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

28

• pdis (n) is the number of partitions of n into distinct parts, i.e. partitions of n in

which there is at most one part of any given size. So the generating function for the

sequence pdis (n) n>0 is obtained by taking the first two summands/terms in each

factor of the product. I.e.

∞

∞

.

.

Y

Y

t

2t

3t

Pdis (x) =

(1 + x + x + x + · · · ) =

(1 + xt ) .

t=1

t=1

The statement of the Lemma follows immediately from the above observations.

Now to solve Problem (∗) on page 26 it suffices to prove that the functions

Podd (x) and Pdis (x) are identical.

Proposition 5.14. For all integers n > 0, pdis (n) = podd (n).

Proof. Note that (1 − x2t ) = (1 + xt )(1 − xt ), so

∞

Q

Podd (x) = Q

∞

1

(1 −

t=1

=

x2t−1 )

(1 − x2t )

t=1

∞

Q

=

(1 −

xt )

(1 − x2t )

= (1 + xt ). Therefore

(1 − xt )

∞

Y

(1 − x2t )

t=1

(1 − xt )

∞

Y

(1 + xt ) = Pdis (x) ,

=

t=1

t=1

where the third expression is obtained from the second by multiplying numerator

∞

Q

and denominator by (1 − x2t ).

t=1

Thus the generating functions of the sequences pdis (n) n>0 and podd (n) n>0

are equal. But this is equivalent to saying that the coefficients of (the series corresponding to) these generating functions are equal. I.e. pdis (n) = podd (n) for all

n > 0.

29

CHAPTER 6

Systems of distinct representatives and Hall’s Theorem.

The Students Union has n clubs. Each club elects a delegate to the Executive

Committee. Clearly:

• The delegate must be a member of the club that he/she represents.

• No one person can represent more than one club.

Questions for the combinatorialist.

(1) Is it possible to choose representatives according to these rules?

(2) In how many ways can this be done?

We consider (1) here and touch on (2) which is more difficult.

Example. Jane and Peter are the only members of the Tennis Club, the Music

Club and the Chess Club. Then clearly the election is impossible.

More generally. If any m clubs contain between them less than m members then

the election is impossible. So a necessary condition for the election is that any m

clubs have between them at least m members. This condition also turns out to be

sufficient. This is the content of Hall’s Theorem.

1. Hall’s (marriage) Theorem

Continuing more mathematically, let A1 , A2 , . . . , An be sets which we suppose to

be subsets of some universal finite set X.

Note. In general the Ai “share” elements, i.e. any an element x ∈ X may be in

several Ai (i.e. x ∈ Ai1 ∩ · · · ∩ Aik for some i1 , . . . , ik ) or x may be in just one Ai

(or in no Ai ). We also allow for the possibility that some sets are equal.

Definition 6.1. A system of distinct representatives (SDR) for the (ordered)

family of sets A1 , . . . , An is an n-tuple (x1 , . . . , xn ) of elements of X with the

following properties.

(a) xi ∈ Ai for i = 1, . . . , n.

This says that the xi are representatives of the sets Ai .

(b) xi 6= xj for i 6= j. This says that the representatives are distinct.

30

Notation 6.2. For J = {i1 , . . . , ik } ⊆ {1, . . . , n} we will often use the shorthand:

A(J) =

[

Ai = Ai1 ∪ · · · ∪ Aik .

i∈J

Note that A(J1 ∪ J2 ) = A(J1 ) ∪ A(J2 ).

Definition 6.3. The family of sets A1 , . . . , An satisfies Hall’s condition if, for

any subset J ⊆ {1, . . . , n},

|A(J)| > |J| .

Theorem 6.4 (Hall’s Theorem). Let A1 , . . . , An be a family of subsets of X.

Then there exists a SDR for A1 , . . . , An ⇔ Hall’s condition holds (for this family).

In other words, Hall’s condition is a sufficient and necessary condition for A1 , . . . , An

to have a SDR.

Proof. (⇒) Suppose that there is a SDR—say (x1 , . . . , xn )—for the family

A1 , . . . , An . Consider any subset J ⊆ {1, . . . , n}. Then A(J) contains all the

S

sets Ai for i ∈ J (as A(J) = i∈J Ai ) and so contains the set of representatives

{ xi | i ∈ J }. Since the representatives are distinct we have |A(J)| > |J|. So Hall’s

condition holds.

(⇐) Let A1 , . . . , An be a family of sets satisfying Hall’s condition. We must prove

that a SDR can be found for the family. Our proof will be by induction on n. Firstly

we note the following.

• Base case n = 1. Hall’s condition guarantees that A1 is nonempty. (Why?) So

picking x1 ∈ A1 we have that (x1 ) is a SDR for the family {A1 }.

• So we assume that n > 1 and as Inductive Hypothesis (IH) that, any family

{B1 , . . . , Bm } such that m < n which satisfies Hall’s condition has a SDR.
Let us call a set J ⊆ {1, . . . , n} is critical if |A(J)| = |J|. (Note that in this case
all of the members of the sets Ai such that i ∈ J must be used as representatives
for these sets.)
We split the rest of the proof into 2 cases.
Case 1. No nonempty set is critical except possibly {1, . . . , n}. I.e. |A(J)| > |J|

for every nonempty proper subset of indices J.

• Choose any element in An as the representative xn for this set. (Note that

An 6= ∅ by Hall’s condition applied to J = {n}.) Then xn cannot be the

representative of any other set so we remove it.

31

• Let A0i = Ai {xn } for each 1 6 i 6 n − 1. Note that, for any nonempty

subset J ⊆ {1, . . . , n − 1} we have

|A0 (J)| > |A(J)| − 1 > |J| − 1

since |A(J)| > |J| in the present case. But this implies that |A0 (J)| > |J|,

so the family A01 , . . . , A0n−1 satisfies Hall’s condition. By the inductive

hypothesis this family has a SDR (x1 , . . . , xn−1 ) say.

• Hence (x1 , . . . , xn−1 , xn ) is a SDR for the original family A1 , . . . , An since

xn ∈ An and xn 6= xi for 1 6 i 6 n − 1 since xi belongs to A0i but xn does

not!

Case 2. There is a critical subset J ⊆ {1, . . . , n} such that 1 6 |J| 6 n − 1.

• By the inductive hypothesis we can choose a SDR xi i∈J for the family of

sets Ai i∈J (it clearly satisfies Hall’s condition).

• For any k ∈ {1, . . . , n} J let A∗k = Ak A(J). In other words, we obtain

S

A∗k by removing from Ak all the elements in A(J) = i∈J Ai as they have

all been used as representatives for the family Ai i∈J .

• We check Hall’s condition for the family of sets A∗k k∈{1,…,n}J . For K ⊆

{1, . . . , n} J we have A∗ (K) = A(K) A(J) = A(J ∪ K) A(J).1 So

|A∗ (K)| = |A(J ∪ K)| − |A(J)|

(6.1)

> |J ∪ K| − |J|

(6.2)

= |J| + |K| − |J|

(6.3)

= |K| ,

where (6.1) holds since A(J) ⊆ A(J ∪K), and (6.2) holds by Hall’s condition

and the fact that J is critical. Also, (6.3) holds since K ∩ J = ∅. Hence

the family of sets A∗k k∈{1,…,n}J satisfies Hall’s condition. By the inductive

hypothesis (as |{1, . . . , n}J| < n) we can find a SDR xk k∈{1,...,n}J for this
family. Putting this together with the previously chosen SDR for Ai i∈J
gives us a SDR for the whole family A1 , . . . , An .
This concludes the inductive step and hence the theorem follows by mathematical
induction on n > 1.

1Remember

A(J ∪ K) =

S

to read the expressions used in (6.1) as A∗ (K) =

i∈J ∪ K

Ai = A(J) ∪ A(K).

32

S

k∈K

A∗k , A(J) =

S

i∈J

Ai and

Remark (Marriage Interpretation). Assume given n women labelled 1, . . . , n

and for each i a set of men Ai which woman i would be happy to marry. Then all

n women can be happily married if and only if A1 , . . . , An has a SDR. Of course,

we used here that bigamy is illegal.

We can make this problem a bit less “sexist” by taking Ai to be the set of men

that woman i would be happy to marry and that would be happy to marry woman

i. Then the happiness above can be taken to be mutual.

In order to check Hall’s condition there is a lot of work to do in general. However

there is one situation in which we can guarantee Hall’s condition.

Proposition 6.5. Let A1 , . . . , An be a family of subsets of the set X. Suppose

that there is some k > 1 such that

(a) |Ai | > k for each index i = 1, . . . , n, and

(b) for each x ∈ X there are at most k indices i ∈ {1, . . . , n} with x ∈ Ai .

Then the family has a SDR.

Proof. We show that Hall’s condition holds.

Take J ⊆ {1, . . . , n} and consider the set of pairs

Y = { (i, x) | i ∈ J and x ∈ Ai } .

Then we see the following.

• |Y | > |J| · k, since |Ai | > k for all i.

• On the other hand consider any x such that (i, x) ∈ Y for some i ∈ J. Then

S

x ∈ A(J) = i∈J Ai . Also, there are 6 k indices i ∈ J ⊆ {1, . . . , n} with

x ∈ Ai . Hence there are 6 k pairs (i, x) ∈ Y with x as second component.

So |Y | 6 k · |A(J)|.

• We thus have that k · |A(J)| > |Y | > |J| · k. I.e. |A(J)| > |J|.

Example 6.6. The Fano Plane, see also the picture on the next page,

n

o

{1, 2, 3}, {1, 4, 5}, {1, 6, 7}, {2, 4, 6}, {2, 5, 7}, {3, 4, 7}, {3, 5, 6}

consists of seven subsets of X = {1, . . . , 7} called “lines”. The elements of X are

called “points”. So each line contains exactly 3 points and each point is on exactly

three lines. Thus we know by Proposition 6.5 (which applies with n = 7 and k = 3)

that the Fano Plane has a SDR. For example, (1, 4, 6, 2, 7, 3, 5) is a SDR.

For those of you who have heard of projective planes and finite fields, the Fano

plane is the projective plane P2 (F2 ) = P(F32 ) over the field F2 with 2 elements.

33

2. How many SDR’s are there?

If the family A1 , . . . , An does not satisfy Hall’s condition then it has no SDR.

But if it does satisfy Hall’s condition then it may have many SDR’s.

Proposition 6.7. Let A1 , . . . , An be a family of subsets of a set X which

satisfies Hall’s condition. Suppose that |Ai | > k for i = 1, . . . , n where k > 1. Then

the number of SDR’s of the family A1 , . . . , An is at least2

k!

if k 6 n ,

P (k, n) if k > n .

Proof. By induction on n. See Cameron’s book.

Corollary 6.8. Suppose that the hypotheses of Proposition 6.5 are satisfied

with k 6 n. Then there are at least k! distinct SDR’s of the family of sets.

2Remember

that, for 0 6 n 6 k, P (k, n) = k(k − 1) · · · (k − n + 1).

34

CHAPTER 7

Latin squares.

1. Latin squares and Latin rectangles

Definition 7.1. A Latin square of order n is an n × n array with each entry

of the array being one element from the set {1, . . . , n} with the property that each

element of the set {1, . . . , n} occurs exactly once in each row and exactly once in

each column of the array.

Example 7.2. The following is

1

2

3

4

5

a Latin square of order 6.

2 3 4 5 6

4 6 1 3 5

6 2 5 1 4

1 5 2 6 3

3 1 6 4 2

6 5 4 3 2 1

Notice that every row and every column can be seen as a permutation of {1, . . . , 6}.

Note. Sometimes we use a different set of symbols (i.e. not {1, . . . , n}) but the

definition of Latin square is still the same.

We also need a more general definition.

Definition 7.3. A Latin rectangle is a k × n array with k 6 n, having entries

from the set {1, . . . , n}, such that each element occurs exactly once in each row and

at most once in each column. Thus the first k rows of a Latin square form a Latin

rectangle.

We now show that, for any n > 1, we can construct a Latin square row by row

using Proposition 6.5.

Proposition 7.4. Let L be a k × n Latin rectangle with k < n. Then L can be
extended to a (k + 1) × n Latin rectangle.
Proof. • For i = 1, . . . , n Let Ai be the set of symbols which do not occur in
the ith column. Then |Ai | = n − k since there are k distinct symbols in each column
of L.
35
• Consider a symbol j. How many i are there with j ∈ Ai ? Well, we know that j
occurs k times in L—once in each row. However these occurrences are in k different
columns, so there are n − k columns in which j does not occur. I.e. there are n − k
indices i with j ∈ Ai .
• We have now verified the hypotheses of Proposition 6.5 for the family of sets
A1 , . . . , An . Hence we know that this family has a system of distinct representatives (x1 , . . . , xn ) say.
• Now, all of the xi are distinct so no symbol is repeated in (x1 , . . . , xn ). Also
xi ∈ Ai for each 1 6 i 6 n, i.e. xi does not occur in the ith column. Thus, by adding
(x1 , . . . , xn ) as the (k + 1)th row we obtain a (k + 1) × n Latin rectangle.
2. How many Latin Squares are there?
Theorem 7.5. The number of Latin squares of order n is at least
n! × (n − 1)! × · · · × 2! × 1! .
Proof. In the proof of Proposition 7.4 we replace Proposition 6.5 by Corol
lary 6.8 to conclude that the number of SDR’s of the family of sets A1 , . . . , An is
at least (n − k)! and so the number of ways of extending a k × n Latin rectangle to
a (k + 1) × n Latin rectangle is at least (n − k)!.
Note that there are n! many 1 × n Latin rectangles. Each such rectangle can be
extended to a 2 × n Latin rectangle in > (n − 1)! ways. Then each such choice can

be extended to a 3 × n Latin rectangle in > (n − 2)! ways etc. We thus deduce the

result.

Finding an upper bound for the number of Latin squares of order n.

2

• There is a trivial upper bound: nn which is the number of ways of putting

n symbols in an n × n array (ignoring the Latin square constraints.)

• Refining this we see that every row is a permutation of {1, . . . , n} so there

are 6 (n!)n Latin squares of order n.

• Refining this further. . . we see that, having chosen the first row, every other

row is a derangement (i.e. a permutation π such that π(i) 6= i for all 1 6

i 6 n) of it so the number of Latin squares is 6 n!(d(n))n−1 where d(n) is

n

X

(−1)i

the derangement number. (And it is known that d(n) = n!

.)

i!

i=0

36

• The exact number has been calculated for n 6 11 by exhaustive search. For

example McKay and Wanless, in the Annals of Combinatorics 2005, show

that the number of Latin squares of order 11 is:

11! × 10! × 5363937773277371298119673540771840

i.e. very very roughly 11 × (10!)2 × 5.36393777 × 1033 .

3. Youden squares

Latin rectangles can arise from families of subsets of {1, . . . , n} in the following

way.

Proposition 7.6. Let A1 , . . . , An be subsets of {1, . . . , n}. Suppose that, for

some k > 0 every set Ai has k elements and every element x ∈ {1, . . . , n} lies in

precisely k of the sets Ai . Then there is a k × n Latin rectangle M such that the

entries in the ith column of M form the set Ai .

Proof. • By Proposition 6.5 the family of sets has a SDR (x1 , . . . , xn ) which

we can take to be the first row of the rectangle.

• Now let A0i = Ai {xi } for i = 1, . . . , n. Clearly |A0i | = k − 1. Also, given any

x ∈ {1, . . . , n}, we have used x as the representative for one of the sets of which

it is a member. So there are precisely k − 1 indices with x ∈ A0i . So the family

{A0i , . . . , A0n } satisfies the conditions of Proposition 6.5 with k replaced by k − 1. We

continue this process with each SDR forming a new row until k = 0.

The Latin rectangles that represent a family of sets as above are sometimes called

Youden squares (although they aren’t squares).

37

CHAPTER 8

Extremal Set Theory.

Given X = {1, . . . , n} we know that |P(X)| = 2n (where P(X) denotes the

powerset of X, i.e. the set/family of subsets of X) and that the number of subsets of

X of fixed size k is C(n, k). We will now look at families of subsets of X (i.e. subsets

of the elements of P(X)) which satisfy some given constraint on the relationship

between members of the family. Our objective is to find an upper bound on the

cardinality of such a family and to try to find out which families achieve this upper

bound.

1. Intersecting Families

Definition 8.1. A family F of subsets of a set X is intersecting if, for all

A, B ∈ F, A ∩ B 6= ∅.

Notation 8.2. We say that a (unordered) pair of subsets {A, B} of a set X is

a complementary pair if B = X A. (I.e. if either {A, B} = {X, ∅} or {A, B} is a

partition of X into 2 parts.)

Proposition 8.3. An intersecting family F of subsets of X = {1, . . . , n} satisfies |F| 6 2n−1 . There exist intersecting families of size 2n−1 .

Proof. • We can partition the 2n subsets of X into 2n−1 complementary pairs

{A, X A}. Note that an intersecting family F contains at most one set from each

pair. Hence |F| 6 2n−1 .

• Let F 0 be the family of all subsets containing 1 (say). Then |F 0 | = 2n−1 =

|P({2, . . . , n})|

There are many intersecting families of subsets (of an n-element set X) of size

n−1

2

. We saw one example in the proof of Proposition 8.3. The following are further

examples.

Notation 8.4. For simplicity, we sometimes use the shorthand i1 i2 . . . ik to

denote the subset {i1 , i2 , . . . , ik } of some set X. For example, {12, 13, 14, 23, 24, 34}

denotes the family of subsets

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

38

of size 2 of the set X = {1, 2, 3, 4}.

Example 8.5. We suppose that X = {1, . . . , n}.

• Suppose firstly that n is odd. Then the family of subsets containing more than

n

2

elements has size/cardinality 2n−1 since it contains exactly one of each comple-

mentary pair of subsets. Note that this family is intersecting (see below for the

argument).

• If n is even, then any family F which contains all the subsets of size >

precisely one of each complementary pair of sets of size

n

2

n

2

and

(i.e. pairs {A, X A} such

that |A| = |X A| = n2 ) contains 2n−1 sets (one from each complementary pair). It

is also intersecting. Indeed if A, B ⊆ X are such that |A| >

|A ∩ B| = |A| + |B| −|A ∪ B| >

n

2

n

2

and |B| > n2 , then

+ n2 − n = 0; and if |A| = |B| =

n

2

and A ∩ B = ∅,

then A and B are complementary, so they cannot both belong to F.

• Specific examples of the second case above are (using the shorthand of Notation 8.4) for X = {1, 2, 3, 4} the two families

F1 = {1234, 123, 124, 134, 234, 12, 24, 23} ,

F2 = {1234, 123, 124, 134, 234, 13, 14, 34} .

Note that these intersecting families both have cardinality 8 and differ precisely in

the 3 sets of size 2. There are 6 more of such intersecting families of maximal size.

Example 8.6. Let X = {1, 2, 3, 4, 5, 6, 7} and let B be the family of seven subsets

{123, 145, 167, 246, 257, 347, 356} .

This is the Fano Plane from Example 6.6. It is also known that (X, B) is the only

Steiner Triple System of order 7. Let F be the family of all those subsets of X

which contain a member of B. Then F is intersecting and |F| = 64 = 27−1 (See

Workshop 5, Question 2).

Remark 8.7. Suppose that, given some universal n-element set X, we only

consider families F consisting of k-element subsets. Note the following.

(a) For n < 2k any family of k-element subsets is intersecting.
(b) Now assume n > 2k.

• If n = 2k, then, by the argument from Example 8.5, the intersecting

families F of k-element subsets are precisely those which contain at most

39

one of each complementary pair of subsets (as defined in Notation 8.2) of

X of size k. So

1

1 (2k)(n − 1)!

|F| 6 · C(n, k) = ·

=

2

2 (n − k)!k!

(n − 1)!

(n − 1) − (k − 1) !(k − 1)!

= C(n − 1, k − 1) .

Note that if we define for i ∈ X (n arbitrary), Fk (i) as the family of all

k-element subsets of the n-element set X containing the element i, then

|Fk (i)| = C(n − 1, k − 1).

• If n > 2k, then we still have for any intersecting family F of k-element

subsets of X that |F| 6 C(n − 1, k − 1). Moreover, if n > 2k and F is such

a family with |F| = C(n − 1, k − 1), then F = Fk (i) for some i ∈ X.

• We can generalise this further. Call a family F t-intersecting if |A ∩ B| > t

for all A, B ∈ F. Then we have the following result

Theorem 8.8. (Not Examinable) Given k > t > 1 there exist n1 and

n2 such that the following hold.

(a) If n > n1 , any t-intersecting family of k-element subsets of an nelement set has size at most C(n − t, k − t).

(b) If n > n2 , a t-intersecting family of k-element subsets of an n-element

set which has size C(n − t, k − t) consists of all k-element subsets

containing some fixed t-element subset (of the n-element set).

Theorem 8.8 and the t = 1 result for n > 2k before it are due to Erdös,

Ko and Rado.

2. Sperner Families

Definition 8.9. A family F of subsets of a set X is called a Sperner family if

no member of F properly contains any other member of F, i.e.

A, B ∈ F ⇒ A 6⊂ B and B 6⊂ A ,

where ⊂ denotes proper inclusion.

Note 8.10. Suppose that |X| = n. Then, for any fixed 1 6 k 6 n the family of

all k-element subsets of X forms a Sperner family containing C(n, k) sets. Notice

that the binomial coefficients increase to the midpoint and then decrease. So the

largest Sperner families of this type occur when k =

n+1

2

n

2

if n is even and k =

n−1

2

or

if n is odd. We will see that these are the largest Sperner families in general.

40

Theorem 8.11. (Sperner’s Theorem) Let F be a Sperner family of subsets of

the n-element set X. Then the following statements are true.

(a) |F| 6 C(n, b n2 c).

(b) If equality holds in (a) then F consists of all subsets of X of size b n2 c or F

consists of all subsets of X of size d n2 e.

Note. If n is even, then b n2 c = d n2 e = n2 .

Proof. We may assume X = {1, . . . , n}. Define a chain of subsets of X to be

a sequence of the form

∅ = A0 ⊂ A1 ⊂ · · · ⊂ An = X

Remark. Recall that “⊂” is proper inclusion. Thus |Aj+1 Aj | = 1 for all

j ∈ {0, . . . , n − 1}.

We now prove (a) and (b).

(a) Claim 1. There are n! chains.

Proof of Claim 1. If π is a permutation of X, then A0 ⊂ A1 ⊂ · · · ⊂

An is a chain where Ai = {π(1), . . . , π(i)} for 1 6 i 6 n (and A0 = ∅). Also,

if B0 ⊂ B1 ⊂ · · · ⊂ Bn is a chain, then π : X → X defined by setting π(i)

to be the element in Bi+1 Bi for all 0 6 i 6 n − 1 is a permutation of

X. Thus chains and permutations of X are in one-one correspondence. So

there are n! chains.

Claim 2. For any k-element subset A, A lies in k!(n − k)! chains.

Proof. Indeed, there are k! chains ∅ = A0 ⊂ · · · ⊂ Ak = A and (n−k)!

chains A = B0 ⊂ · · · ⊂ Bn−k = X (by the same reasoning). So there are

k!(n − k)! such chains in total.

Remark. Note also that

k!(n − k)! = n! ×

1

.

C(n, k)

Thus A (in the proof of Claim 2) is contained in

(8.1)

1

C(n,k)

of the overall number

of chains. Moreover, by symmetry we can deduce this directly from the fact

that there are C(n, k) k-element subsets and that for any two distinct kelement subsets the sets of chains to which they belong are disjoint. Using

this observation and equation (8.1) we obtain another proof of Claim 2.

41

Now consider a Sperner family F of subsets of X. By definition any chain

contains at most one member of F. So for the number N of chains containing a member of F we have

X

N =

|A|!(n − |A|)!

A∈F

|A|!(n − |A|)!

=

n!

n!

A∈F

!

X

1

= n!

.

C(n, |A|)

A∈F

X

However N 6 n! as there are only n! chains in all. Thus

X

N

1

=

6 1.

C(n, |A|)

n!

A∈F

But, as mentioned above the middle binomial coefficients are largest so their

reciprocals are smallest. Thus, setting m = b n2 c we have

X

1

1

|F| ×

6

6 1.

C(n, m)

C(n, |A|)

A∈F

Thus |F| 6 C(n, m).

(b) When is |F| = C(n, b n2 c)?

By inspection of the argument above, this only happens when every chain

contains a member of F (N = n!) and for all A ∈ F, C(n, |A|) = C(n, b n2 c).

So, noting that C(n, b n2 c) = C(n, d n2 e) we must have |A| ∈ {b n2 c, d n2 e} for

all A ∈ F. There are two cases.

(i) n is even. Then

n

2

= b n2 c = d n2 e and F consists of all subsets of size n2 .

(ii) n is odd. Again put m = b n2 c. Then m + 1 = d n2 e.

Claim. F either consists of all subsets of size m or all subsets of size m + 1.

Proof of Claim. • Suppose that F contains some A such that |A| =

m. Note that any other m-element subset B of X contains j elements

outside A and m − j elements in A, for a unique 1 6 j 6 m. We call B “jdifferent” to A. We prove by induction that all j-different (to A) m-element

subsets are in F (and so all m-element subsets are in F). For j = 1, suppose

A = Y ∪ {a} and B = Y ∪ {b}. Then A ⊂ Y ∪ {a, b} so Y ∪ {a, b} ∈

/ F.

Also B ⊂ Y ∪ {a, b} is part of a chain. Thus, as Y ∪ {a, b} ∈

/ F it must

be the case that B ∈ F (B and Y ∪ {a, b} are the only elements in such

42

a chain which have size m or m + 1, so one of these two must be in F).

Hence every “1-different” (to A) k-element subset is in F. Now suppose

that 1 6 j 6 m and that every “j-different” m-element subset is in F. Let

B be a “(j + 1)-different” m-element subset. Then choose any “j-different”

m-element subset C which differs from B on just one element. Then C ∈ F

and by the argument above we show that therefore also B ∈ F. Thus by

induction on 1 6 j 6 m we see that all m-element subsets are in F (as

each such subset is “j-different” (to A) for some 0 6 j 6 m). As there are

C(n, m) such subsets there are no other subsets in F.

• If F doesn’t contain some A with |A| = m, then |A| = m + 1 for all

A ∈ F. Since there are C(n, m + 1) = C(n, m) such subsets, F consists of

all the (m + 1)-element subsets of X.

This concludes the proof of Theorem 8.11.

Example 8.12.

(a) Show that the largest Sperner family of subsets of X =

{1, 2, 3, 4, 5, 6} containing the subsets {1}, {2}, {3, 4} and {5, 6} has cardinality 8 (i.e. contains precisely 8 subsets of X).

Solution. Suppose that F ⊆ P(X) is a Sperner family such that {1}, {2},

{3, 4}, {5, 6} ∈ F. Then, for any other B ∈ F, 1, 2 ∈

/ B; B contains 3 or 4,

but not both (otherwise B ⊂ {5, 6} or {3, 4} ⊂ B); and B contains 5 or 6,

but not both (otherwise B ⊂ {3, 4} or {5, 6} ⊂ B). Hence F contains the

four subsets above and some of the sets {3, 5}, {3, 6}, {4, 5}, {4, 6}. Note

that these four sets together with the initial four sets form a Sperner family.

So any Sperner family F containing the subsets {1}, {2}, {3, 4} and {5, 6}

satisfies |F| 6 8 and amongst these there is a unique one with |F| = 8.

(b) How does this compare with the bound N given by Sperners Theorem?

Solution. The bound N is achieved by a family F where F contains all

subsets of size b 26 c =

6

2

= 3. Thus N = |F| = C(6, 3) =

6×5×4

3×2×1

= 20.

3. The De Bruijn Erdös Theorem (Not Examinable)

This concerns a special case of intersecting families. Here, instead of assuming

that any two sets in the family F intersect over at least one element we assume that

they intersect in precisely one element.

43

Theorem 8.13. Let F be a family of subsets of X = {1, . . . , n}. Suppose that

any two sets of F have exactly one point in common. Then |F| 6 n. If equality

holds, then one of the following situations occurs.

(a) Up to renumbering the points and sets, we have F = {A1 , . . . , An } where

Ai = {i, n} for 1 6 i 6 n (so that An = {n}).

(b) Up to renumbering the points and sets, we have F = {A1 , . . . , An } where

An = {1, 2, . . . , n − 1} and Ai = {i, n} for all 1 6 i 6 n − 1.

(c) For some positive integer q we have n = q 2 + q + 1 with each set in F being

of size q + 1 and each point lying in q + 1 members of F.

Remarks 8.14.

1. The proof of Theorem 8.13 uses Hall’s Theorem on the existence of SDR’s.

2. When n = 3 (i.e. q = 1), then case (b) and case (c) describe the same case.

3. For q > 2 the structure described in case (c) is called a projective plane of order

q. Only for q a prime power examples are known. In this case the usual projective

plane P2 (Fq ) = P(F3q ) over the finite field Fq with q elements is an example. The

first example—i.e. for q = 2—is known as the Steiner triple system (X, F) of order

7 where X = {1, 2, 3, 4, 5, 6, 7} and F = {123, 145, 167, 246, 257, 347, 356}. This

configuration is also known as the Fano Plane, see Examples 6.6 and 8.6. Note that,

as q = 2, n = q 2 + q + 1 = 7 and each set has q + 1 = 3 elements whereas each point

lies in q + 1 = 3 sets of the family F.

44

CHAPTER 9

The pigeonhole principle & Ramsey numbers.

In this final chapter we discuss counting problems with a slightly different flavour.

We start with some preliminary definitions which will be useful to our understanding

of Ramsey Theory.

1. Preliminaries

We start by defining the notion of a graph.

Intuitively by a graph we will mean a certain set of “points”, called vertices,

where some pairs of points are joined by an edge (and others not).

The edges have no direction, we only allow distinct points to be joined by an edge,

and at most one edge can link any two points. These objects are sometimes called

simple graphs or “undirected graphs without loops and without multiple edges”.

More formally, a graph is a pair G = (V, E) such that V is a set and E is a

set which consists of 2-element subsets of V . So V consists of the vertices of G and

{x, y} ∈ E means that x and y are connected by an edge of G. We will be concerned

with finite graphs, namely graphs with a finite number of vertices, so also a finite

number of edges. In this case we often take the set of vertices to be {1, 2, . . . , n}.

By a subgraph of a graph G = (V, E) we mean a graph G0 = (V 0 , E 0 ) where

V 0 is a subset of V and E 0 consists of all edges in E which have endpoints in V 0 .

So a subgraph of G is completely determined by choosing a subset V 0 of the set of

vertices V of G.

Graphs are a useful mathematical way of modelling networks of various types.

For example, the Facebook network can be modelled by a node for every user, and an

edge between nodes if the people are friends. (Notice that the Twitter and Google+

networks are not immediately graphs in our sense, since ‘following’ and ‘encircling’

are not symmetric: I can follow Stephen Fry without him following me.)

The actual graphs that we will encounter in this chapter are complete graphs as

described in the following example.

45

Example 9.1. A graph G = (V, E) is called complete, if E consists of all 2element subsets of V . So in a complete graph any two (distinct) vertices are connected by an edge. Note that a subgraph of a complete graph is again complete.

We denote the complete graph with vertex set {1, . . . , n} by Kn and will refer to

any complete graph G = (V, E) with |V | = n as “a Kn ”.

So K3 has vertex set V = {1, 2, 3} while its edge set is E = {{1, 2}, {1, 3}, {2, 3}}

(namely all unordered pairs).

Figure 1. The complete graphs Kn for n = 1, 2, 3, 4, 5

2. The Pigeonhole Principle

Proposition 9.2 (Pigeonhole principle). Suppose that n > r ≥ 1. If n pigeons

are distributed among r pigeonholes then at least one pigeonhole will contain at least

two pigeons.

Here is a slight generalisation:

Proposition 9.3 (Generalised pigeonhole principle). Suppose that r, m ≥ 1 and

n > mr. Suppose that a set of n elements is written as a disjoint union of r subsets.

Then at least one of these subsets will contain at least m + 1 elements.

Proof. Notation: we shall use the square union symbol t to indicate pairwise

disjoint union. So, if S is our set of size n, then the hypothesis is that S = S1 t

S2 t · · · t Sr for some sets Si . Suppose for a contradiction that each Si has size

≤ m. Then n = |S| = |S1 t S2 t · · · t Sr | = |S1 | + |S2 | + · · · + |Sr | ≤ mr, which is a

contradiction.1

Example 9.4. Show that at least 29 numbers between 1 and 200 have the same

remainder when is divided by 7.

Let S := {1, 2, 3, . . . , 200}. For i ∈ {0, 1, 2, 3, 4, 5, 6}, let Si be the set of elements

of S whose remainder under division by 7 is i. Then S = S0 t S1 t S2 t . . . t S6 .

Since 200 > 28 · 7 = 196, the generalised pigeonhole principle tells us that at least

one Si contains at least 29 elements, meaning that at least 29 of the numbers in S

have remainder i when divided by 7.

1For

the proof we only need that S is the union of the Si , we don’t really need the disjointness.

46

Example 9.5. Suppose that each day, a child paints her calendar with 2 out of

a total set of 5 colours. Prove that over a period of 21 days there are at least 3 days

which she has painted with the same two colours.

Let S be the set of 21 days. There are C(5, 2) = 10 possible choices of 2 out of

5. For each such choice, i say, let Si be the set of days that she chooses i. Then

S = S1 t · · · t S10 . As 21 > 2 · 10, by the generalised pigeonhole principle, some Si

contains at least 3 elements. Namely the same choice is made on at least 3 days.

Here is a rather harder statement proven in 1935:

Theorem 9.6 (Erdős and Szekeres). Let r, s be integers ≥ 0. Then any sequence

a1 , a2 , . . ., an of n > rs distinct real numbers contains a subsequence of length

r + 1 which is strictly increasing or a subsequence of length s + 1 which is strictly

decreasing.

Proof. For each i = 1, 2, . . . , n, let ti be the length of the longest increasing

subsequence starting with ai . If some ti ≥ r + 1, the proposition is proved. So let’s

assume that each ti ≤ r, and we will try to find a decreasing subsequence of length

s + 1.

For k = 1, . . . , r, let Sk be the set of those i such that ti = k. So the sets Sk for

k = 1, . . . , r break up the set {1, 2, . . . , n} into r (disjoint) subsets (some of which

may be empty). By the generalised pigeonhole principle, as n > r · s, there is some

k such that Sk contains at least s + 1 elements.

Let Sk = {i1 , i2 , . . . , is+1 , . . .} with i1 < i2 < · · · < is+1 . Now suppose that
ail < aim for l, m with 1 6 l < m 6 s + 1. Then, since im ∈ Sk , there is an
increasing subsequence of length k starting with aim . Appending ail to the start of
the subsequence would then give an increasing sequence of length k + 1 beginning
with ail , contradicting il ∈ Sk . So ai1 > ai2 > · · · > ais+1 , which is a strictly

decreasing sequence of length s + 1 as required.

Remark. If in Theorem 9.6 we omit “distinct” and replace one of the two

occurrences of “strictly” by “weakly”, then the result is still true.

3. Ramsey Theory

The subject of Ramsey theory has the same flavour as the generalised pigeonhole principle and the Erdős and Szekeres Theorem. In a very general setting, with

apparently little information to work with, we want to find a large subset which is

well-behaved or structured in some sense.

47

More precisely, we shall work in the following context: we have a set S of n

elements, and the unordered pairs {a, b} from S are assigned colours red or blue

(according to some rule, algorithm, or random process about which we may know

nothing). The challenge is then to find a “large” subset S 0 ⊆ S such that all

unordered pairs of elements from S 0 have the same colour.

Recalling that unordered pairs can be thought of as the edges of a graph, it will

be convenient to think of this situation graph-theoretically. We consider our set S

of n elements as the set of vertices of the complete graph Kn . (Recall that in the

complete graph, all pairs of distinct vertices are joined by an edge.) The edges of

Kn are then coloured red or blue. Our challenge is to find a “large” subgraph where

all edges have the same colour.

Here is a key example, sometimes called the Party problem: At a party of 6

people there must be 3 people who have all met one another before, or 3 people who

are mutual strangers.

Lemma 9.7 (The Party Problem). Suppose |S| = 6, and unordered pairs from S

are assigned colours red or blue. Then there is a subset S 0 of S of size 3 such that

all unordered pairs of elements of S 0 are assigned the same colour.

Equivalently if the edges of K6 are coloured red or blue then K6 has a subgraph

on 3 vertices with all edges having the same colour.

Proof. Pick some fixed a ∈ S. Of the remaining 5 elements of S let X be the

set of those elements joined to a by a red edge, and Y the set of those joined to a

by a blue edge. Then S {a} = X t Y . So, by the generalised pigeon-hole principle,

either |X| ≥ 3 or |Y | ≥ 3.

Suppose first that |X| ≥ 3. Let b, c, d ∈ X be three distinct elements. If at

least 2 of them, for example b, c, are joined by a red edge, then {a, b, c} solves our

problem, namely each pair from {a, b, c} is joined by a red edge. Otherwise all pairs

from b, c, d are joined by a blue edge, and we have again solved the problem.

The case where |Y | ≥ 3 proceeds by the same argument.

Example 9.8. We cannot do the same thing with a set S of size 5. In the

following picture, interpret dashed lines as red edges, and solid lines as blue edges.

Then there is no red or blue triangle.

48

• Given integers n, p, q ≥ 1, we say that Ram(p, q, n)

Definition 9.9.

holds if: for any colouring of the edges of Kn with red and blue, Kn contains a subgraph on p vertices all of whose edges are red, or Kn contains a

subgraph on q vertices all of whose edges are blue.

• The Ramsey number R(p, q) is the least integer n, if one exists, such that

Ram(p, q, n) holds.

Of course, if given p, q there is no integer n satisfying Ram(p, q, n) then R(p, q)

is undefined.

Lemma 9.10.

(i) If Ram(p, q, n) holds then Ram(p, q, m) holds for all m ≥ n.

(ii) R(p, q) = R(q, p).

Proof.

(i) Let m ≥ n and let c be a 2-colouring of G = Km . Now look at

any n vertices of G and the subgraph G0 they form. Since Ram(p, q, n) holds,

there is a suitable red subgraph on p vertices of G0 —and so of G—or a suitable

blue subgraph on q vertices of G0 —and so of G.

(ii) Suppose that Ram(p, q, n) fails. Then there is some colouring c of Kn which

witnesses this. Now look at the reverse colouring c0 which has a red edge everywhere c has a blue edge, and vice versa. Then c0 witnesses that Ram(q, p, n)

fails.

We have actually already computed one Ramsey number:

Proposition 9.11. R(3, 3) = 6.

Proof. By Lemma 9.7 R(3, 3) exists and R(3, 3) ≤ 6. On the other hand, by

Example 9.8, R(3, 3) > 5.

Some other Ramsey numbers are easy to pin down:

Proposition 9.12.

(i) R(p, 1) = R(1, p) = 1 for all p ≥ 1.

(ii) R(p, 2) = R(2, p) = p for all p ≥ 2.

Proof. Part (i) is entirely trivial since a subgraph on one vertex has no edges,

and thus all the subgraph’s edges are vacuously red/blue. Thus we move swiftly on

to part (ii). By Remark 9.10, it is enough to show that R(p, 2) = p. As usual, we

do this in two steps:

Claim 1 R(p, 2) ≤ p.

Proof of Claim 1 We have to show that Ram(p, 2, p) in Definition 9.9 holds. Let

c be any colouring of Kp .

49

Case (i). All edges are coloured red. In this case Kp is a subgraph of itself with all

edges coloured red.

Case (ii). Some edge is coloured blue. Then the subgraph of Kp whose vertices are

the endpoints of one fixed blue edge gives a subgraph of Kp on 2 vertices all of whose

edges are blue. QED Claim 1

Claim 2 R(p, 2) > p − 1.

Proof of Claim 2 We shall show that Ram(p, 2, p − 1) does not hold. We need a

colouring c of the edges of Kp−1 red/blue with no totally red subgraph on p vertices

and no totally blue subgraph on 2 vertices. We can simply let c be the colouring

which colours all edges of Kp−1 red. QED Claim 2

More general Ramsey numbers are notoriously hard to pin down. But we can at

least establish that they exist, and give a (weak) bound:

Theorem 9.13.

(i) R(p, q) exists for all p, q ≥ 1.

(ii) R(p, q) ≤ R(p, q − 1) + R(p − 1, q) for all p, q ≥ 2.

Proof. We shall prove part (i) by induction on p+q, establishing part (ii) in the

process. By Proposition 9.12(i), we may assume that both p, q > 2. The inductive

assumption will be that R(x, y) exists for all x, y ≥ 1 such that x + y < p + q.
We shall prove that if G = (V, E) is a complete graph with R(p, q−1)+R(p−1, q)
vertices and its edges are coloured red or blue then there will be a subgraph on p
vertices with all edges red or a subgraph on q vertices with all edges blue. This will
establish both parts of the theorem.
Fix a vertex v ∈ V . Let X(v) be the set of vertices of G joined to v by a red
edge, and Y (v) the set of vertices of G joined to v by a blue edge. Then either
(I) |X(v)| ≥ R(p − 1, q), or
(II) |Y (v)| ≥ R(p, q − 1).
(Otherwise, if both (I) and (II) fail, then |V | = |V {v}| + 1 = |X(v)| + |Y (v)| + 1 6
R(p, q − 1) + R(p − 1, q) − 1.)
Suppose first that (I) holds. Then by the definition of R(p − 1, q), the subgraph
of G with X(v) as set of vertices has either (a) a subset of p − 1 vertices with all
edges between them red, or (b) a subset of q vertices with all edges between them
blue. Case (b) gives us a totally blue subgraph of G on q edges. In case (a), by
adjoining v, we get a totally red subgraph of G on p vertices.
There is a similar argument when (II) holds. This proves the theorem.
50
Corollary 9.14. For all p, q ≥ 1, R(p, q) ≤ C(p + q − 2, p − 1) = C(p + q −
2, q − 1).
Proof. This follows from Proposition 9.12(i), Theorem 9.13, induction, and the
fact (1.14 (ii)) that C(n + 1, k) = C(n, k) + C(n, k − 1). It will be left as as exercise
on the coursework.
We finish with a lower bound.
Proposition 9.15. For all p, q ≥ 1, R(p, q) > (p − 1)(q − 1).

Proof. By Proposition 9.12(i), we may assume p, q > 2. It is enough to show

that for n = (p − 1)(q − 1), Ram(p, q, n) does not hold. We will colour the edges of

the complete graph Kn on n vertices with colours red and blue such that there is

no red subgraph on p vertices and no blue subgraph on q vertices. Arrange the n

vertices in a rectangle with p − 1 rows and q − 1 columns. If u, v are in the same

row, colour the edge between them blue. Otherwise colour the edge between them

red. So clearly there is no subgraph on q vertices with all edges blue, because then

the vertices would have to be in the same row, but each row has only q − 1 elements.

Note also that there is no subgraph on p vertices with all edges red, because given

as there are only p − 1 rows, 2 of these p vertices would be in the same row (by the

pigeon-hole principle), so the edge between them would be coloured blue.

Apart from the easy values given by Proposition 9.12, here are all the Ramsey

numbers whose values are known exactly at time of writing:

R(3, 3) = 6, R(3, 4) = 9, R(3, 5) = 14, R(3, 6) = 18, R(3, 7) = 23, R(3, 8) = 28,

R(3, 9) = 36, R(4, 4) = 18, R(4, 5) = 25.

As you can see, finding the exact values of Ramsey numbers is extremely hard.

Paul Erdős is quoted as having said:

“Suppose aliens invade the earth and threaten to obliterate it in a year’s time

unless human beings can find the Ramsey number for red five and blue five. We

could marshal the world’s best minds and fastest computers, and within a year we

could probably calculate the value. If the aliens demanded the Ramsey number for

red six and blue six, however, we would have no choice but to launch a preemptive

attack.”

51

4. (a) Let X = {1, …, n}, n an integer > 1.

i. Show that any intersecting family F of 2-subsets of X for which there is no x

X which is contained in all A EF, must have size 3.

ii. Show that when n = 4 any intersecting family of 2-subsets of X must have size

5 the intersecting families of 2-subsets of X of size n-1

are the ones that consist of the 2-subsets of X containing a fixed element of X.

(b)

(c)

Let X = {1, 2, 3, 4, 5). Determine all the Sperner families of subsets

of X containing the sets {1, 2}, {4} and {2,3,5}. Explain your answer.

About a certain country we only know that every adult person has

exactly one of the possible genders: male, female, neutral, and one or two of the

following possible hobbies: handcraft, computer games, tennis, maths, politics.

What is the minimum number n such that we can guarantee that amongst any n

adults from this country at least five have the same gender and exactly the same

hobbies? Explain your answer.

An edge coloured graph is called monochromatic if all its edges have

the same colour. You are given the following fact. For any red-blue edge colouring

of K6 there are at least two monochromatic triangles (K3’s).

Show that for any red-blue edge colouring of K, there are at least three monochro-

matic triangles.

Hint. Apply the above result to a subgraph of K, and then again to another

subgraph of that K7.

(d)

Purchase answer to see full

attachment

Tags:

Sperner families

intersecting family

family of subsets

fixed element

monochromatic triangle

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.

## Reviews, comments, and love from our customers and community:

This page is having a slideshow that uses Javascript. Your browser either doesn't support Javascript or you have it turned off. To see this page as it is meant to appear please use a Javascript enabled browser.