Discrete Mathematics with Applications

FISHAN KONDOWE NICHOLAS SIAME ADAM

JEREMOT MASOAMBETA

November 6, 2017

1
Preface

i
Acknowledgments

ii
Dedication

iii
TABLE OF CONTENTS TABLE OF CONTENTS

Table of Contents
Preface i

Acknowledgments ii

Dedication iii

1 Unit 1 : Counting Techniques 1

1.1 Lesson 1: Counting Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Multiplication Rule or Product Rule . . . . . . . . . . . . . . . . . . . . 2
1.2 Lesson 2: Permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Lesson 3: Combination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Lesson 4: Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Lesson 5: Multinomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Lesson 6: Sum Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 Lesson 7: Inclusion-Exclusion Principle . . . . . . . . . . . . . . . . . . . . . . . 19

2 Unit 2 : Difference Equations 24

2.1 Lesson 1: Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Counting with Generating Functions . . . . . . . . . . . . . . . . . . . . 26
2.2 Lesson 2: Formulating Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.1 Methods of Solving Recursive Equations . . . . . . . . . . . . . . . . . . 33

3 Unit 3 : Pigeon-hole Principle 41

3.1 Lesson 1: Pigeon-hole Principle (PHP) . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Lesson 2: Simple Form of PHP . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Lesson 3: Regular Form of PHP . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Lesson 4: Extended Regular Form of PHP . . . . . . . . . . . . . . . . . . . . . 46
3.5 Lesson 5: Generalized PHP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Unit 4: Graph Theory Basics 50

4.1 Lesson 1: Vertex, Edge and Valence . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Lesson 2: Walks, Paths’s, Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3 Lesson 3: Disconnectedness of Graphs . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 lesson 4: Vertex Colouring & Time Tabling . . . . . . . . . . . . . . . . . . . . . 58
4.4.1 The Greedy Algorithm For Colouring Vertices . . . . . . . . . . . . . . . 63
4.4.2 Map Colouring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

iv
 1 UNIT 1 : COUNTING TECHNIQUES

1 Unit 1 : Counting Techniques

Introduction
Counting of things is what we always do on daily basis. Different things are counted differently
based on the context on which they do exist. One of the general context is that of Set Theory
you covered in College Algebra. This unit reviews some of the principals of counting elements in
a set. These techniques will bring us to understanding “Combination Principle” which explores
more on determining the number of possible outcomes of a particular experiment or event.

Objectives/Learning Outcomes
By the end of this Unit, you should be able to:

(a) Describe basic counting principals

(b) Define binomial coefficients

(c) Describe the Pascal’s triangle

(d) Differentiate between a combination and permutation

(e) Use counting techniques to solve real life problems.

Key Terms
Counting, Binomial coefficient, Permutation, Combination, multinomial coefficient.

1.1 Lesson 1: Counting Principles

Counting may be in form of addition or multiplication. Multiplication and addition forms two
basic principles of counting called the ‘Multiplication Rule or Product Rule” and “Sum Rule”.
We will also be exposed to permutations and combinations as we will be exploring the content.

1
1.1 Lesson 1: Counting Principles 1 UNIT 1 : COUNTING TECHNIQUES

1.1.1 Multiplication Rule or Product Rule

The product rule involves a possibility of two events occurring at the same time. Consider the
following Figure:

How many ways can we switch on the bulb? Obviously the answer is 6. Thus, we have multiplied
the number of switches in A and number of switches in B.
In other words, if we let set A = {a, b, c} and set B = {1, 2}, then the number of ways of
choosing a pair of members such that one is from A and another from set B is 6. Thus,
(a, 1), (a, 2), (b, 1), (b, 2), (c, 3), (c, 4) = 3 × 2 = 6
We can now generalize the problem above with the following Theorem.

Theorem 1.1 Product Rule of Counting/ Multiplication Rule

Let A and B be two finite sets. Then the number of ways of choosing one member from A and
another from B is
n(A) × n(B)

Example 1.1

a) How many two digit positive integers are there such that 2 does not appear on the units
(ones)?

Solution

There are nine positive integers:{1, 2, 3, 4, 5, 6, 7, 8, 9} from where two sets of integers; the
tens and the units (one) are to be generated. We are restricted that 2 cannot appear on
the units(ones). Hence, there remains 8 options of generating a unit integer. There is no
restriction on the tens integers set hence there are 9 integers. By product rule, there are
9 × 8 = 72 two positive integers such that 2 does not appear on the units.

b) In Malawi, each automobile license plate number consists of two letters followed by a four-
digit number. How many distinct license plate numbers can be formed in Malawi?

Solution

2
1.1 Lesson 1: Counting Principles 1 UNIT 1 : COUNTING TECHNIQUES

We are choosing 2 letters from 26 letters of English alphabet. In the ordered arrangement,
a letter may be repeated. Thus, we have 26 × 26 = 262 = 676 possible letters.

Similarly, we are choosing 4 digits from 10 digits which are 0, 1, 2, 3, 4, 5, 6, 7, 8 ,9. In the
ordered arrangement, a digit may be repeated. Thus, we have 10×10×10×10 = 104 = 10, 000
possible digits.

Therefore, by product rule of counting, there are

262 · 104 = 676 · 10000 = 6, 760, 000

distinct license plate numbers which can be formed in Malawi.

The product rule is not just restricted to two sets, we can have as many sets as possible. The
idea is now generalized in the following theorem.

Theorem 1.2 Generalized Product Rule

Let A1 , A2 , A3 , · · · , Ak be finite sets. Then the number of ways of choosing k members one from
each set is
n(A1 ) × n(A2 ) × n(A3 ) × · · · × n(Ak )

Example 1.2

a) How many rows of T and F can one have for the statement (proposition)

q1 ∨ q2 ∨ q3 ∨ · · · ∨ qn ?

Solution

Each of the proposition can be evaluated to be T or F . Putting the responses on the rows,
we end up having two rows. Thus,  
T
F
for n times. Hence, we have 2n rows.

b) How many 4 digit positive integers are there using the digits 1, 2, 3, · · · , 9 such that no digit
is repeated.

Solution

We can visualize the digits arrangement as:

3
1.2 Lesson 2: Permutation 1 UNIT 1 : COUNTING TECHNIQUES

There are respectively 9, 8, 7 and 6 options, in the first, second, third and fourth digits for
them to be filled. Therefore by generalized product rule we have 9 × 8 × 6 = 3024.

Activity 1.1

Q.1. A senior control inspector has to visit five factories P, Q, R, S and T every week. She visits
a different factory each day, from Monday to Friday, but she chooses the order of her visits
at random each week. In how many different ways can she order her week’s visit?

Q.2. How many telephone numbers are possible for

i. Airtel Malawi ii. Telekom Networks Malawi (TNM)?

Q.3. In the morning, I have a number of different possible ways to travel from my home to my
office. I could walk all the way, travel by school bus, or take any of three different bicycles.
In how many ways could I have possible of such moves?

Q.4. In Zambia, each automobile license plate number consists of three letters of English alpha-
bet followed by a two-digit number then finish with two letters of English alphabet. To
avoid confusion between “O” and “zero” and between “I” and “one”, the letters “O” and
“I” are not used. How many distinct license plate numbers can be formed in Zambia?

1.2 Lesson 2: Permutation

Permutation refers to number of ways of choosing r objects from n and placing the chosen
objects on r fixed positions.
The notation 9 P4 means number of ways of choosing 4 items from 9 and placing them on 4 fixed
position. Thus, 9 P4 = 9 × 8 × 7 × 6, read as: “9 permute 4” or “9 choose 4 and permute”.
Note that permutation is just the short hand for product rule without repetitions.
Notation

4
1.2 Lesson 2: Permutation 1 UNIT 1 : COUNTING TECHNIQUES

Permutation is denoted by n Pr or n Pr or P (n, r). They are all equivalent to saying “n permute
r ”.
Investigation: 5 P2
Let A, B, C, D, E be different items. For instance, the first selection of the two objects would
be to place item A in the first position and item B on the second position making AB. The
second selection would be to put item B on the first position and item A on the second, BA.
Thus, there are two possibilities of positioning a pair of items A and B. In the same way, there
are two possibilities for each of the pairs : AC, AD, AE, BC, BD, BE, CD, CE, DE. In total,
there are 20 possibilities of choosing two items from A, B, C, D, E and placing them in two fixed
positions. Thus, 5 P2 = 5 × 4 = 20.

Example 1.3

a) Nicholas, Jeremot and Ellen were all born in the same ordinary year. In how many ways can
these three persons have different birthdays?

Solution

An ordinary year has 365 days (different dates). Three birth dates are selected from a
possible 365 days and assigned to three distinct persons. No, birth date may repeat itself
within each year. The number of ways that this can occur is

P (365, 3) = 365 · 364 · 363 = 48, 228, 180

b) How many 9-digit positive integers are there that use the digit 1, 2, 3, · · · , 9 where no digit
is repeated?

Solution

We want 9 P9 = 9 × 8 × 7 × 6 × 5 × 4 × 3 × ×1 = 362, 880

Factorial Notation
We were introduced to factorial notation in College Algebra as the product of integers from 1 to
n inclusive occurring in n factorial ways, denoted n!. Thus, n! = n×(n−1)×(n−2)×· · ·×3×2×1
For instance, 5! = 5 × 4 × 3 × 2 × 1 ≡ 5 × 4! and 9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × ×1
Notice that 9 P9 = 9!. Therefore, n Pn = n! read “n factorial”.

Theorem 1.3 Permutation

n n!
Pr = (n−r)!

Investigation of n Pr

5
1.2 Lesson 2: Permutation 1 UNIT 1 : COUNTING TECHNIQUES

Consider the following Figure

We therefore conclude that n Pr = n × (n − 1) × (n − 2) × · · · × n − (r − 1) ≡ n × (n − 1) × (n −

2) × · · · × n − r + 1.
x
If x 6= 0, then x
= 1. Therefore,

n
Pr = n × (n − 1) × (n − 2) × · · · × n − r + 1 × 1
(n − r) (n − r − 1) 3 2 1
= n × (n − 1) × (n − 2) × · · · × (n − r + 1) × × × ··· × × ×
(n − r) (n − r − 1) 3 2 1
n!
=
(n − r)!
5! 5×4×3!
Thus, 5 P2 = (5−2)!
= 3!
= 20.
Permutations that have been performed so far are under the assumption that items are not re-
peated at any of the positions. However, in some scenarios, permutation may involve repetition.
Permutation with Repetition
Suppose we are asked to find the distinct permutations from the word CHANCELLOR. How
would you go about it?
We are interested with number of permutations of a multiset, that is a set of objects some
which are alike. We observe that the word CHANCELLOR has 10 letters where the letters
C and L appear twice, letters H, A, N, E, OR appear once.
Let P (n; n1 , n2 , · · · , nr ) denote the number of permutations of n objects of which n1 are alike,
n2 are alike, · · ·, nr are alike. Then the total permutations are calculated using the following
theorem:

Theorem 1.4 Permutation with Repetition

n!
P (n; n1 , n2 , · · · , nr ) =
n1 ! × n2 ! × n3 ! × · · · × nr !
where n = n1 + n2 + · · · + nr .
Using the given formula the total permutations on the word CHANCELLOR is:
10!
P (10; 2, 1, 1, 1, 1, 2, 1, 1) = = 907, 200
2! × 1! × 1! × 1! × 1! × 2! × 1! × 1!

Example 1.4

6
1.2 Lesson 2: Permutation 1 UNIT 1 : COUNTING TECHNIQUES

a) An organism has 4 molecules of Adenine (A), 3 molecules of Guanine (G), 2 molecules of

Thymine (T) and 1 molecule of Cytosine C. If molecules appear as chain. How many varieties
(different chains) are possible?

Solution

We want a sequence of 4A’s, 3G’s, 2T ’s and 1C. By the theorem:

(4 + 3 + 2 + 1)!
P (4 + 3 + 2 + 1; 4, 3, 2, 1) =
4! × 3! × 2! × 1!
10!
=
4! × 3! × 2! × 1!
10 × 9 × 8 × 7 × 6 × 5 × 4!
=
4! × 3! × 2! × 1!
= 12600

b) A 3 × 2 × 4 cube is formed from stacking together 1 × 1 × 1 cubes

How many shortest routes are there between two most distant corners, such that one moves
along edges of 1 × 1 × 1 cube?

Solution

Each shortest route can UNIQUELY be represented as a sequence of 3x’s, 2y’s and 4z’s
where x means moving an edge to the right, y means moving an edge at perpendicular to x
motion horizontally and z means moving an edge [Link] the theorem, we have:
9!
P (3 + 2 + 4; 3, 2, 4) = = 1, 260
3! × 2! × 4!

Activity 1.2

Q.1. Three cards are chosen in succession from a deck of 52 cards. Find the number of ways
this can be done

7
1.3 Lesson 3: Combination 1 UNIT 1 : COUNTING TECHNIQUES

i. With replacement ii. Without replacement

Q.2. Three hungry Eagles are flying in the sky in search for the food. They suddenly see 200
Chambo fish being sun-dried in preparation for the market. In how many possible ways
would these Eagles take away the fish?

Q.3. A row of six seats in a classroom is to be filled by selecting individuals from a group of
ten students

i. In how many different ways can the seats be occupied?

ii. If there are six boys and four girls in the group and if boys and girls are to be
alternated, find the number of different seating arrangements.

Q.4. Find distinguishable permutations of letters in the words:

i. ARRANGEMENT ii. MASOAMBETA iii. PROFESSOR

1.3 Lesson 3: Combination

Suppose we have a collection of n objects. A combination of these n objects taken r at a time,
is any selection of r objects where order does not matter. For example: How many ways can
one choose two boys from 5?
In the example, the issue of putting boys on two fixed position is missing. Recall our solution
from “first principle” (without using any formula/technique).
Let A, B, C, D, E be our boys. Then, we have 10 pairs: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE.
The required answer is 10.
The notation 5 C2 means number of ways of choosing 2 boys from 5. At this time we do not
know the formula for 5 C2 . However, we know 5 P2 .
Recall: For any choice of 2 boys, AB, we have 2 P2 = 2 × 1 = 2 [Link],

5
C 2 × 2 P2 = P25
5
5 P2
∴ C2 = 2
P2
20
= = 10
2
Notation
Combination is denoted, n Cr or n Cr or Crn to mean number of ways of choosing r items from n.
NB: If the chosen r are to be placed into r fixed positions, then r Pr = r! possible permutations.
Therefore,

n n
Pr = C r × r Pr

8
1.3 Lesson 3: Combination 1 UNIT 1 : COUNTING TECHNIQUES

n n
Pr = Cr × r!
n
n Pr n!
∴ Cr = = /r!
r! (n − r)!
n n!
∴ Cr =
r!(n − r)!

Theorem 1.5 Combination

n!
i. n Cr = r!(n−r)!

ii. n Cr ≡ n
Cn−r

Proof

n!
i. n Cr = r!(n−r)!
already proved.

ii. Number of ways of choosing r items from n is equivalent to choosing n − r from n to

DISCARD. Therefore, n Cr ≡ n
Cn−r

Example 1.5

a) A class has 6 girls and four boys. How many ways can we choose 2 girls and 2 boys from
this class?

Solution

Number of ways of choosing 2 girls from 6 is 6 C2 . Number of ways of choosing 2 boys from 4
is 4 C2 . By product rule, the number of ways of choosing 2 girls and 2 boys is 6 C2 ×4 C2 = 90

b) Five (5) points lie on a circumference of a circle. How many chords can we have by joining
any two points?

Solution

Each chord requires two points. Therefore, number of chords are 5 C2 = 10 chords.

c) Find the total number of triangles that can be drawn using points in (b) above as the corners
(vertices) of a triangle?

Solution

For us to draw a triangle, there is need of joining three points. Thus, we are choosing
three points out of five. On the other hand, we are choosing 2 points out of five to discard.
Therefore, the total number of triangles are: 5 C3 =6 C2 = 10 triangles.

9
1.4 Lesson 4: Binomial Coefficients 1 UNIT 1 : COUNTING TECHNIQUES

Activity 1.3

Q.1. How many different committees of 3 people can be formed from a pool of 7 people?

Q.2. In how many ways can a committee consisting of 2 faculty members and 3 students be
formed if 6 faculty members and 10 students are eligible to serve on the committee?

Q.3. The University of Malawi Senate has 100 members. Suppose that it is desired to place each
senator on exactly 1 of 7 possible committees. The first committee has 22 members, the
second has 13, the third has 10, the fourth has 5, the fifth has 16, and sixth and seventh
have 17 apiece. In how many ways can these committees be formed?

Q.4. Let x represent a horizontal movement from A to the right and y be the vertical movement
from A upwards in the following Figure.

Find:

i. The shortest route from A to C

ii. The shortest route from C to B
iii. The shortest route from A to B

1.4 Lesson 4: Binomial Coefficients

Understanding Binomial Coefficients relates much with understanding sequence expansion of a
strictly increasing sequence.
Review: Strictly Increasing Sequence
A sequence a0 , a1 , a2 , a3 , · · · , an , an+1 , · · · is said to be strictly increasing if and only if an <
an+1 , ∀n. For instance, 2, 6, 7, 8, 9, 12, 14 is a strictly increasing sequence while 3, 8, 6, 7, 1, 0 is
NOT a strictly increasing sequence.

Example 1.6

10
1.4 Lesson 4: Binomial Coefficients 1 UNIT 1 : COUNTING TECHNIQUES

a) How many strictly increasing sequences of 3 numbers can you form from the set {3, 1, 2, 9, 7}.
For instance, the choice of {3, 1, 3} gives 1, 2, 3 as a strictly increasing sequence.

Solution

In here, we observe that any choice of 3 different numbers give one unique strictly increas-
ing sequences. Therefore, the number of sequences required is the same as number of ways
of choosing 3 numbers from 5 numbers which is also equivalent to choosing 2 numbers from
5 to discard. Thus,
5
C3 ≡ 5 C2 = 10

b) Figure1 shows roads intersecting at right angle. How many shortest routes are there from A
to B?

Figure 1: Crossing Roads

Solution

Let x be the horizontal movement and y be a vertical movement as labeled above. Then,
every route from A to B is uniquely expressed as the sequence of 3x’s and 2y’s. Therefore,
the number of possible shortest routes is equivalent to number of sequences of 3x’s and 2y’s.
Thus we have:
5
C3 = 10 =5 C2

Recall: b + b = 2b. This implies that (x + y) + (x + y) = 2(x + y) = 2x + 2y. Thus, we can now
generalize for c = constat that c(x + y) = cx + cy.
Suppose we are multiplying three brackets, (x1 +x2 )(y1 +y2 )(z1 +z2 ). We can choose to multiply
out the first and the second brackets and finish with the third bracket as:

(x1 + x2 )(y1 + y2 )(z1 + z2 ) = [(x1 + x2 )y1 + (x1 + x2 )y2 ](z1 + z2 )

= [x1 y1 + x2 y1 + x1 y2 + x2 y2 ](z1 + z2 )
= x1 y1 z1 + x2 y1 z1 + x1 y2 z1 + x2 y2 z1 + x1 y1 z2 + x2 y1 z2 + x1 y2 z2 + x2 y2 z2

Each term has a member of first second and third brackets. Therefore, expansion is a choice of
one member from each bracket without repeating a choice.

11
1.4 Lesson 4: Binomial Coefficients 1 UNIT 1 : COUNTING TECHNIQUES

For instance, the coefficient of x3 y 2 in the expansion of (x + 5)5 will be 5 C2 ≡ 5 C2 = 10. Thus,
(x + 5)5 is a product of five brackets.

(x + y)5 = (x + y)(x + y)(x + y)(x + y)(x + y)

y2 ⇒ y’s came from choices of y from 2 out of 5 brackets
x3 ⇒ x’s came from choices of x from 3 out of 5 brackets
∴ Number of ways of getting x3 y 2 is 5 C2 ≡ 5 C2 = 10

In other words (x + 5)5 has 5 C2 x3 y 2 = 10x3 y 2 as one term and x3 y 2 has a coefficient of 10.
In College Algebra, you learnt the Binomial Expansion as the expansion of the form (x+y)n =
n
C0 x0 y n +n C1 x1 y n−1 +n C2 x2 y n−2 + · · · + n Cn xn y 0 from which the following formula is derived.

Theorem 1.6 Binomial Theorem

n
X
n n
(x + y) = Cp xp y n−p
p=0

Notation
n


The notation n Cp ≡ p
n
!
X n
(x + y)n = xp y n−p
p=0 p
To find the coefficient of the expansion, it does not matter the letter you use.

Example 1.7

Find the coefficient of x3 y 2 in the expansion of (2x + y 1/2 )10

Solution
We would observe that y 2 = y 1/2 × y 1/2 × y 1/2 × y 1/2 comes from 4 brackets. 2x must have
been chosen from 6 brackets to give x3 . Therefore, the corresponding term in the expansion
10
is C6 (2x)6 (y 1/2 )4 = 210(2x)6 (y 1/2 )4 . Therefore, the coefficient of x3 y 2 in the expansion of
(2x + y 1/2 )10 is 210.

Activity 1.4

Q.1 The term and its coefficient that contains x in the expansion of 2 + x)9 .
5

Q.2 Find the coefficient of the term that contains x8 y 18 in the expansion of (3x + 2y 2 )17 .

Q.3 The middle term in the expansion of (2x − 3y)50 . What is its coefficient?
2
Q.4 Find the coefficient of x10 in the expansion of (2 − x 5 )200 .

12
1.5 Lesson 5: Multinomial Theorem 1 UNIT 1 : COUNTING TECHNIQUES

1.5 Lesson 5: Multinomial Theorem

The coefficient in the binomial theorem involves two terms that are being expanded. The
coefficient of expansion can also be found when there are more than two terms. For instance, it
may be asked to find the coefficient of x2 y 3 z 4 in the expansion of (x + y + z)9 .
From the question, it is observed that x2 in x2 y 3 z 4 , x’s came from 2 brackets. Thus, 2x’s are
needed. In a similar way y 3 in x2 y 3 z 4 , y’s came from 3 brackets, thus, 3y’s were needed. z 4 in
x2 y 3 z 4 , z’s came from 4 brackets, 4z’s were needed.
2+3+4 9!


Therefore, number of ways of getting x2 y 3 z 4 is 2,3,4
= 2!×3!×4!
x2 y 3 z 4 = 1, 260x2 y 3 z 4 . The
coefficient of x2 y 3 z 4 is 1260.
The example is now generalized in the Theorem 1.7.

Theorem 1.7 Multinomial Theorem

X n

n
(x1 + x2 + x3 + · · · + xn ) = xn1 1 × xn2 2 × · · · × xnp p
ni ≥0
n1 , n2 , · · · , np
where ni ∈ {0} ∪ N and n1 + n2 + n3 + · · · np = n.
NOTE: The expression n1 ,n2n,···,np is called Multinomial Coefficient.

Example 1.8

a) Find the coefficient of x2 y 3 z 4 in (2 + x1/3 − 3y + z) = 20

Solution

We would observe that z 4 in x2 y 3 z 4 ⇒ z’s came from 4 brackets, y 3 in x2 y 3 z 4 ⇒ y’s came

from 3 brackets, x2 = (x1/3 )6 ⇒ x1/3 came from 6 brackets, and so the constant 2 in
(2 + x1/3 − 3y + z)20 must have come from 20 − (4 + 3 + 6) = 7 brackets. Therefore, the
corresponding terms
   
20 20
z 4 (−3y)3 (x1/3 )6 27 = (−3)3 27 x2 y 3 z 4
4, 3, 6, 7 4, 3, 6, 7
| {z }
Multinomial Coefficient
Simplifying the coefficient we get −1.6090 × 1013 which is required.

b) How many non-negative integer solutions has the equation x + y + z = 10 got?

Solution

We could regard this problem as requiring to find the number of ways of placing 10 iden-
tical (indistinguishable) pencils in 3 containers XY Z. One way of doing this could be to
place the 10 pencils on the straight line and split them in 3 groups by two spliters into
x = 4, y = 5, z = 1.
| {z }
possible solution

13
1.5 Lesson 5: Multinomial Theorem 1 UNIT 1 : COUNTING TECHNIQUES

Alternatively, regard the two splitters as pencils, to have 10 + 2 = 12 pencils and choose any
two pencils to be splitters. Each choice of 2 pencils from 12 gives a unique solution to
12 12!
x + y + z. The total number of non-negative integer solutions is C2 = 2!10!
= 66

c) How many non-negative integer solutions has the equation w + x + y + z = 10 got?

Solution

The solution to this follows the reasoning applied in (b) above. Just add three spitters to 10
13 13!
pencils and consider them as pencils altogether. Thus, we will have C3 = 3!10!
= 286

The last two parts in Example1.8 gives us the generalization stated in this Theorem about
non-negative integer solutions.

Theorem 1.8 Non-negative Integer Solutions

n+p−1
i. Number of non-negative integer solutions to x1 + x2 + x3 + · · · + xp is Cp−1
n+k−1
ii. Number of ways of placing n− indistinguishable items in k boxes is Ck−1

Example 1.9

How many non-negative integer solutions has the equation w + x2 + x3 + x4 = 50 got if w ≥ 2?

Solution
If we let w = 1, x2 = 1, x3 = 1 and x4 = 48, then it is not a solution since w 6≥ 2. Thus, if
w = 2 + x1 , where x1 ∈ {0} ∪ N will be a [Link],

w + x2 + x3 + x4 = 50 ⇒ 2 + x1 + x2 + x3 + x4 = 50
⇒ x1 + x2 + x3 + x4 = 50 − 2
⇒ x1 + x2 + x3 + x4 = 48
| {z }
non-negative integers
48+3 53
Therefore, applying Theorem1.8, the solution is C3 = C3 = 20825

Activity 1.5

Q.1 Calculate the coefficient of x2 c5 d3 in the expansions of:

i. (x2 − d + c)10 ii. (x2 + d − c + 2)12 iii. (2 + xd1.5 + c2.5 )10

Q.2 Find the total number of integer solutions of u + v + w + x = 40.

Q.3 Find the total number of integer solutions of u + v + w + x = 40 if u ≥ 15 or x ≥ 10

14
1.6 Lesson 6: Sum Rule 1 UNIT 1 : COUNTING TECHNIQUES

1.6 Lesson 6: Sum Rule

Suppose Box 1 has 10 Mangoes and Box 2 has 15 Oranges. A person is offered to pick 2 fruits
of the same type. How many ways can he/she do that?
It is true that Mangoes and Oranges are altogether different fruits. Thus, there is no intermediate
fruit between them. Let x be number of all possible ways of picking a pair of Mangoes from
Box 1 and y be number of possible ways of picking a pair of Oranges from Box 2. Then the
10
total number of ways of picking a pair of fruits is x + y = C2 +15 C2 = 150. In general, the
following theorem applies:

Theorem 1.9 Sum Rule

Let P and Q be two disjoint sets.

Then n(P ∪ Q) = n(P ) + n(Q).

Example 1.10

a) Suppose there are 10 football coaches and 7 netball coaches participating in certificate of
fitness test under AFCON trials at Bingu International Stadium. If you are part of the
10
trainers and are asked to choose the best three coaches, any coach can be chosen in C3 +
7
C3 = 155 ways.

b) If a bookshelf in the departmental library has 5 calculus texts, 3 algebra texts, 6 differential
equations texts and 4 statistics texts. Find the number of ways a student can select one of
the texts. Here again, using the sum rule, a text book can be chosen in 5 + 3 + 6 + 4 + 9 = 18
ways.

Nevertheless, using same principals, the rule can be extended to three or more disjoint events
as shown in Example1.10(b).

Theorem 1.10 n Cr = n−1

Cr−1 (Pascal’s Triangle )

The proof to the theorem is simple.

Let x be an item among the n available items. To choose r items from n, we have to either

i. Include x among the r− chosen items OR

ii. Exclude x among the r−chosen items.

15
1.6 Lesson 6: Sum Rule 1 UNIT 1 : COUNTING TECHNIQUES

Case (i)
If we want to include x, we choose item x−first. Since we want to choose r− items and x is
already chosen, then we only need to choose r − 1 items from the remaining n − 1 items. Thus,
n−1
we can do this in Cr−1 ways.
Case (ii)
If we want to exclude item x, then we want to discard item x and choose all r items from the
n−1
remaining n − 1 items. Thus, we can do this in Cr ways of doing this. Since one can choose
r−items from n via case(i) or case(ii), then the number of ways of choosing r−items will be

n n−1
Cr = Cr or n−1 Cr−1
n n−1 n−1
Cr = Cr + Cr−1
n  
n
X n p n−p
Recall: (x + y) = xy .
p=0
p

Thus, if n = 1, then (x + y)1 = 10 x0 y 1−0 + 1

x1 y 0 = x + y. The coefficient of x and y in
1
(x + y)n when n = 1 is 1 and 1. When n = 2, then (x + y)2 = 20 x0 y 2−0 + 21 x1 y 1 + 22 x2 y 0 =

x2 + xy + xy + y 2 = x2 + 2xy + y 2 . The coefficient of x and y in (x + y)n when n = 2 is 1 , 2

and 1. Hence, we conclude that n Cx = n
Cn−x . In the end, as n increases, the following will be
0
built up and it is named P ascal sT rianle.

Example 1.11

Show, without using binomial expression 2m = m

C0 + m
C1 + m
C3 + · · · + m
Cm
Solution
Let {1, 2, 3} be a set. Then {1, 2} ⊆ {1, 2, 3}, ∅ ⊆ {1, 2, 3} or {1, 2, 3} ⊆ {1, 2, 3}. We would
observe that there 8 subsets altogether. Then, how many subsets can be formed from the set
{1, 2, 3, 4 · · · , m}? We can use product rule and sum rule to solve the problem.
Using product rule, one has to decide whether to “include” or “exclude” each of the m− mem-
× · · · × m} = 2m number of subsets.
bers. The number of ways of doing this is 2| × 2 × 2{z
m times
Using sum rule, a subset has 0 members or 1 member or 2 members or 3 members or · · · or

16
1.6 Lesson 6: Sum Rule 1 UNIT 1 : COUNTING TECHNIQUES

m m m
m members in it. Therefore, number of ways of having these subsets is C0 + C1 + C3 +
m
···+ Cm . Since both of these figures count number of subjects of {1, 2, 3, 4, · · · , m} and hence
2m = m
C0 + m
C1 + m
C3 + · · · + m
Cm .

Lemma 1.1 Generalized Sum Rule Theorem

Let A1 , A2 , A3 , · · · , Ak be finite sets such that Ai ∩ Aj = ∅, ∀i 6= j . Then

|A1 ∪ A2 ∪ A3 ∪ · · · ∪ Ak | = |A1 | + |A2 | + |A3 | + · · · + |Ak |

Example 1.12

Figure 1.6 depicts streets intersecting at right angles. How many shortest routes are there from
A to B via junction C or junction D?

Figure 2: Crossing Streets

Solution
Let A1 be a set of shortest routes from A to B via junction C.
Let A2 be a set of shortest routes from A to B via junction D.
We want number of members in A1 ∪ A2 . Thus, |A1 ∪ A2 |.
Since A1 ∩ A2 = ∅, then:

|A1 ∪ A2 | = |A1 | + |A2 |

     
6 5 5 6
= +
2 1 1 4
= 75 + 75 = 150 routes.

Example 1.13

17
1.6 Lesson 6: Sum Rule 1 UNIT 1 : COUNTING TECHNIQUES

2n n 2 n 2 n 2 n 2






Show that n
= 0
+ 1
+ 2
+ ··· + n
.
Solution
2n


n
means number of ways of choosing n items from 2n items. Visually,

Let Ai be the set of choices of n items from 2n items, so that i items come from the left where
{i = 0, 1, 2, 3, 4, · · · , n}.
NB: Ai ∩ Aj = ∅
n
X
2n


Therefore, by sum rule we get n
= |A1 ∪ A2 ∪ A3 ∪ · · · ∪ An | = |Ai |, since Ai ∩ Aj = ∅.
i=1

But, by product rule, |Ai | = ni n−i

n
n

n


. Since by Theorem 2.3, n Cx = n
Cn−x , then, i n−i
=
n 2

2
2
2
2
. Therefore, 2n = n0 + n1 + n2 + · · · + nn .



i n

Activity 1.6

Q.1 You need to travel in between Blantyre and Lilongwe. You can either fly, hire a car from
car rentals, or go by public transport like a bus. There are 8 different flights in between
Blantyre and Lilongwe, 20 different cars to hire and 10 buses. How many options do you
have to get from Blantyre to Lilongwe?

Q.2 A student dance committee is to be formed consisting of 2 boys and 3 girls. If the member-
ship is to be chosen from 4 boys and 8 girls, how many different committees are possible?

Q.3 The minimum password length is 6 and the maximum is 8. The password can consist of
either an uppercase letter or a digit. There must be at least one digit in the password.
How many passwords are possible?

Q.4 Figure12 depicts streets intersecting at right angles. How many shortest routes are there
from A to B via junction D or junction C? How do you compare the result found here and
the one found in Example1.12?

18
1.7 Lesson 7: Inclusion-Exclusion Principle 1 UNIT 1 : COUNTING TECHNIQUES

Figure 3: Crossing Streets

1.7 Lesson 7: Inclusion-Exclusion Principle

The sum rule we have looked at so far, focuses on disjoint sets. Thus, sets whose intersection is
empty. But now, the question one may ask is, what if the intersection of the sets is not empty,
thus, what if Ai ∩ Aj 6= ∅? Will the sum rule still hold?
Investigation
Consider two sets A and B such that A∩B 6= ∅. Will n(A∪B) = n(A)+n(B) when A∩B 6= ∅?.
Visually, we shape our problem as:

We would observe that in A ∪ B, x is counted once, z is also counted once, and y is counted
twice. Then, there is need to consider taking away (excluding) the number that has been
counted twice. It is from this background of exclusion that the following Theorem is deduced.

Theorem 1.11 Simplest Form of Inclusion-Exclusion Principle.

n(A ∪ B) = n(A) + n(B) − n(A ∩ B), ∀A, B finite

Example 1.14

How many integers are divisible by 4 or 6 in the list {1, 2, 3, 4, 5, · · · , 7000}?

Recarp:
bxc is the largest integer ≤ x. For instance, b5.1c = 5 and b 21
4
c = 5.
Solution

19
1.7 Lesson 7: Inclusion-Exclusion Principle 1 UNIT 1 : COUNTING TECHNIQUES

Let A1 be a set of integers divisible by 4. Let A2 be a set of integers divisible by 6

We nee to find:

|A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 |

7000 7000 7000
= b c+b c−b c
4 6 LCM(4, 6)
= 1750 + 1167 − 583
= 2, 334

Example 1.15
How many non-negative integer solution has the equation x + y + z + w = 10 got if x ≥ 2 or
w ≥ 3?.
Solution
Let A1 be a set of all solutions to the equation x + y + z + w = 10 where x ≥ 2. For instance,
A1 = {(x = 2, y = 3, z = 2, w = 3) · · ·}.
Let A2 be a set of all solutions to the equation x + y + z + w = 10 where w ≥ 3.
We want number of members that are in A1 and A2 . Thus, A1 ∪ A2 . Since members in
|A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 |, then we can look at each of the sets separately.
For |A1 |:
Let x = 2 + x1 , x1 ∈ {0} ∪ N. Therefore;

x + y + z + w = 10 ⇒ 2 + x1 + y + z + w = 10
⇒ x1 + y + z + w = 8
 
8+4−1 11
∴ Number of solutions required = C4−1 = = 165
3
For |A2 |:
Let w = 3 + w1 , w1 ∈ {0} ∪ N. Therefore;

x + y + z + w = 10 ⇒ x + y + z + 3 + w1 = 10
⇒ x + y + z + w1 = 7
 
7+4−1 10
∴ Number of solutions required = C4−1 = = 120
3
For |A1 ∩ A2 |:
A1 ∩ A2 is a set of solutions where x ≥ 2 AND x ≥ 3. Let x = 2 + s and w = 3 + t where
s, t ∈ {0} ∪ N. The equation now becomes

x + y + z + w = 10 ⇒ 2 + s + y + z + 3 + t|A1 | = 10
⇒ s+y+z+t=5
 
5+4−1 8
∴ Number of solutions required = C4−1 = = 56
3

20
1.7 Lesson 7: Inclusion-Exclusion Principle 1 UNIT 1 : COUNTING TECHNIQUES

Therefore, |A1 ∪ A2 | = 165 + 120 − 56 = 341.

We have seen that when two sets have an intersection region, to count the total number of
elements in it, we first add the elements in each of the sets and take away elements of the
intersection. How about when we have three sets whose intersection is not empty?
Investigation
What about |A ∪ B ∪ C|?
Consider Figure4

Figure 4: Venn Diagram

From the Figure, any member of the regions a, b and c is correctly counted once by the formula.
So are members of the regions d, e and f . Members of the region g have not been counted at
all or counted 1 + 1 + 1 − 1 − 1 − 1 = 0. This leads us to the following extended Theorem on
the inclusion-exclusion principle

Theorem 1.12 1st Extension: Inclusion-Exclusion Principle

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

Further extensions, we get the generalized inclusion-exclusion principle which is stated in the
following Theorem.

Theorem 1.13 Generalized Inclusion-Exclusion Principle.

line 1
z }| { line 2 line 3
Xk zX }| { zX }| {
|A1 ∪ A2 ∪ · · · ∪ Ak | = |Ai | − |Ai1 ∩ Ai2 | + |Ai1 ∩ Ai2 ∩ Ai3 | + · · · +
i=1 i1 <i2 i1 <i2 <i3
line N
z X }| {
(−1)k+1 |Ai1 ∩ Ai2 ∩ · · · ∩ Ak |
i1 <i2 <···<ik

Let us now scrutinize the Theorem bit by bit.

Consider LHS:
Let x be any member of Ai1 ∩ Ai2 ∩ · · · ∩ Ak . Then from College Algebra, x is counted once
in |Ai1 ∩ Ai2 ∩ · · · ∩ Ak |. Thus, LHS has counted x once. Since x is chosen arbitrarily, the
justification of the Theorem is now apparent.

21
1.7 Lesson 7: Inclusion-Exclusion Principle 1 UNIT 1 : COUNTING TECHNIQUES

Consider RHS:
Let x appear in r of the k sets. Thus, r = 1, 2, 3, 4, · · · , k. We are assuming that:

Ai1 , Ai2 , Ai3 , · · · , Air , Air+1 , Air+2 , Air+3 , · · · , Aik

| {z } | {z }
x is in these x is not in these

k
X
Line 1: |Ai |
i=1
Here x has been counted r times since x− appears in r of the k sets.
X
Line 2: − |Ai1 ∩ Ai2 |
i1 <i2

There are two situations for x in this second line. The first is when x is in both sets Ai1 and
Ai2 while the other is when x is in either set Ai1 or set Ai2 .
Suppose x ∈ Ai1 and x ∈ Ai2 . Then |Ai1 ∩ Ai2 | contains x once. Suppose x ∈ Ai1 and x 6∈ Ai2 ,
then |Ai1 ∩ Ai2 | has counted x zero times. This means that the number of times x has been
subtracted is xr from choosing two sets among sets with x’s to intersect. Thus, in lines 1 and

2, x is counted r − 2r


X
Line 3: + |Ai1 ∩ Ai2 ∩ Ai3 |
i1 <i2 <i3
r


Applying the same line of arguments as in line 2, x is included 3
times.
Continuing with same arguments for the intermediate sets, the last line will have the following:
r sets
X z }| {
Line r: | Ai1 ∩ Ai2 ∩ · · · ∩ Air |
i1 <i2 <···<ir
r


In this line, x is counted (−1)r+1 r
Recall: 1 ≤ r ≤ k .
This implies that all intersections of more than r sets do not have x in them, since x appears
in only r sets. Therefore, the RHS of the theorem has counted x in:
       
r r r r+1 r
r− + − + · · · + (−1)
2 3 4 r

NB: n Pn = n!, 0 P0 = 0! = 1.
The RHS of the theorem counts x in:
           
r r r r r+1 r r
= − + − + · · · + (−1) since = r.
1 2 3 4 r 1
         
r r r r r+1 r
= 1+ − + − + · · · + (−1) −1 introducing a zero
1 2 3 4 r
             
r r r r r r+1 r r
= + − + − + · · · + (−1) −1 since = 1.
0 1 2 3 4 r 0
            
r r r r r r+1 r
= + −1 + − + − + · · · + (−1) grouping
0 1 2 3 4 r

22
1.7 Lesson 7: Inclusion-Exclusion Principle 1 UNIT 1 : COUNTING TECHNIQUES

            
r r r r r r+1 r
= −1 1− + − + − · · · + (−1) factoring -1
0 1 2 3 4 r
r  
X r
= 1− (−1)k
k=0
k
r  
X r
= 1− (−1)k 1r−k
k=0
k
= 1 − (−1 + 1)r Binomial expansion
= 1−0
= 1

Activity 1.7

Q.1 How many bitstrings of length 8 start either with a bit 1 or end with 00?

Q.2 What is the number of bit strings of length 4 that do not have two consecutive ones? [Hint:
You can visualize using a tree diagram beginning with empty string ]

Q.3 How many integers are divisible by 5 or 7 or 10 in the list {1, 2, 3, 4, 5, · · · , 12000}?

Q.4 How many non-negative integer solution has the equation x + y + z + w = 15 got if x ≤ 6
or w ≥ 3?

23
 2 UNIT 2 : DIFFERENCE EQUATIONS

2 Unit 2 : Difference Equations

Introduction
Many problems in Probability give rise to difference equations. Difference equations also called
recurrence equations relate to differential equations as discrete mathematics relates to continu-
ous mathematics. Anyone who has made a study of differential equations will know that even
supposedly elementary examples can be hard to solve. By contrast, elementary difference equa-
tions are relatively easy to deal with. A difference equation defines a sequence recursively: each
term of the sequence is defined as a function of the previous terms of the sequence.

Objectives/Learning Outcomes
By the end of this Unit, you should be able to:

(a) Solve counting problems using generating Functions

(b) Formulate relations

(c) Solve equations by iterative, generating function and root methods

Key Terms
Iteration, Relation, Differencing, Recurrent relation, Root of a function, Generating a function.

24
2.1 Lesson 1: Generating Functions 2 UNIT 2 : DIFFERENCE EQUATIONS

2.1 Lesson 1: Generating Functions

Generating functions are one of the most surprising and useful inventions in Discrete Math.
Roughly speaking, generating functions transform problems about sequences into problems
about functions. This is great because we have got piles of mathematical machinery for manip-
ulating functions. Thanks to generating functions, we can apply all that machinery to problems
about sequences. In this way, we can use generating functions to solve all sorts of counting
problems. There is a huge chunk of mathematics concerning generating functions, so we will
only get a taste of the subject. In this module, we will put sequences in angle brackets to more
clearly distinguish them from the many other mathematical expressions floating around.
The ordinary generating function for the infinite sequence hg0 , g1 , g2 , g3 · · ·i is the power
series:
G(x) = g0 + g1 x + g2 x2 + g3 x3 + · · ·

This module considers only ordinary generating functions, despite have non-ordinary ones. A
generating function is a “formal” power series in the sense that x is usually regarded a place-
holder rather than a number. Only in rare cases will x be evaluated in generating function as a
real number value, so as to ignore the issues of convergence. Throughout the module, indication
of the correspondence between a sequence and its generating function will be indicated by a
double-sided arrow as follows:

hg0 , g1 , g2 , g3 · · ·i ←→ g0 + g1 x + g2 x2 + g3 x3 + · · ·

For instance, here are some sequences and their generating functions:

h0, 0, 0, 0 · · ·i ←→ 0 + 0x + 0x2 + 0x3 + · · · = 0

h1, 0, 0, 0 · · ·i ←→ 1 + 0x + 0x2 + 0x3 + · · · = 1
h3, 2, 1, 0 · · ·i ←→ 3 + 2x + 1x2 + 0x3 + · · · = 3 + 2x + x2

The pattern observed is simple: the ith term in the sequence (indexing from 0) is the coefficient
of xi in the generation function.
Revision: Geometric Progression
Let Sn = a + ar + ar2 + · · · + arn−1 be the sum of the geometric series. Then the nth term of
the series is found by the formulae:
 
 
 a(rn − 1) a(1 − rn ) 
 
Sn = ,

 r−1 1−r 
| {z } | {z } 
r>0 r<0

where a is the first term, r is the common ratio and n is the number of terms in the series.

25
2.1 Lesson 1: Generating Functions 2 UNIT 2 : DIFFERENCE EQUATIONS

Suppose g(x) = 1+x+x2 +· · ·+xn−1 be our geometric series, then a = 1, r = x and n = nterms.
Then, the sum of the nth term of this geometric series will be
1 − xn
f (x) =
1−x
Suppose |x| < 1, eg : x = 17 , then xn → as n → ∞. Thus 1


7
→ as n → ∞. The generating
function of h1, 1, 1, 1 · · ·i ←→ 1 + 1x + 1x2 + 1x3 + · · · without end. This is equivalent to

lim 1 + 1x + 1x2 + 1x3 + · · · + xn−1

n→∞

Theorem 2.1 Geometric Series

∞
X 1
2 3
1 + 1x + 1x + 1x + · · · = 1
1−x
, |x| < 1. Thus, xk = = f (x) The equation
k=0
− x}
|1 {z
Closed form
| {z }
Series form
does not hold when |z| ≥ 1. This formula gives closed-form generating functions for a whole
range of sequences. For example:
1
h1, 1, 1, 1, · · ·i ←→ 1 + x + x2 + x3 + · · · =
1−x
1
h1, −1, 1, −1 · · ·i ←→ 1 − x + x2 − x3 + x4 − · · · =
1+x
1
h1, a, a2 , a3 , · · ·i ←→ 1 + ax + a2 x2 + a3 x3 + · · · =
1 − ax
1
h1, 0, 1, 0, 1, 0 · · ·i ←→ 1 + x2 + x4 + x6 + · · · =
1 − x2

2.1.1 Counting with Generating Functions

Generating functions are particularly useful for solving counting problems. In particular, prob-
lems involving choosing items from a set often lead to nice generating functions by letting the
coefficient of xn be the number of ways to choose n items.
The generating function for binomial coefficients for instance, follows directly from the Binomial
Theorem:
                
k k k k k k k 2 k k
, , ,···, , 0, 0, 0, · · · ←→ + x+ x + ··· + x
0 1 2 k 0 1 2 k
= (1 + x)k

Thus, the coefficient of xn in (1 + x)k is the number of ways to choose n distinct items from
a set of size k. For example, the coefficient of x2 is k2 , the number of ways to 2 choose items

from a set k elements. In a similarly way, the coefficient of xk+1 is the number of ways to choose
k + 1 items from size k set, which is zero.

Example 2.1

26
2.1 Lesson 1: Generating Functions 2 UNIT 2 : DIFFERENCE EQUATIONS

How many non-negative integer solutions has the equation x + y + z = 10 got?

Solution
x can have the powers of x1 , x2 , x3 , x4 · · ·
y can have the powers of y 1 , y 2 , y 3 , y 4 · · ·
z can have the powers of z 1 , z 2 , z 3 , z 4 · · ·
We can choose any powers for x, y and z provided the powers add up to ten(10)
bfRecall: am · an = am+n . Look for those terms with power 10.
1 1 1
(w0 , w1 , w2 · · ·) (w0 , w1 , w2 · · ·) (w0 , w1 , w2 · · ·) = × ×
| {z }| {z }| {z } 1−w 1−w 1−w
x-value y-value z-value
1
= in closed form.
(1 − w)3
∞
X
If 1
(1−w)3
= an wn , then the coefficient of w10 is the number of non-negative integer solutions.
n
1
In other words, (1−x)3
= a0 + a1 w + a2 w2 + a3 w3 + · · · + a10 w10 .
Expressing Functions as Series Skill
∞
X
We have seen that f (x) = 1
1−x
1 2
= 1+x +x +x +x ··· = 3 4
xn , |x| < 1. How about if there
n=0
is another function f (x) = ex = a0 + a1 x + a2 x2 + · · ·, what is the series form of f (x)?

If we let x = 0 in f (x) = ex , then f (0) = e0 = 1 = a0 ⇒ a0 = 1.

Differentiating f (x) n times and substituting x = 0, for each derivative we have:

f 0 (x) = ex = a1 + 2a2 x + 3a3 x3 + · · · + nan xn−1 + · · ·

f 0 (0) = e0 = 1 = a1 ⇒ a1 = 1
f 00 (x) = ex = 2 × 1a2 + 3 × 2a3 x + 4 × 3a4 x3 + · · · + n(n − 1)an xn−2 + · · ·
1
f 00 (0) = e0 = 1 = 2 × 1a2 ⇒ a2 =
2×1
..
.
f n (x) = ex = n(n − 1)(n − 2)(n − 3) × · · · × 3 × 2 × 1an + ()x + ()x2 + · · ·
1
f n (0) = e0 = 1 = n! + 0 ⇒ an =
n!
2 3 4
x x x xn
∴ ex = 1 + x + + + + ··· + ···
2! 3! 4! n!
The following theorem follows:

Theorem 2.2
x2 x3 x4 xn
ex =1+x+ + + + ··· + ···.
|{z} 2! 3! {z 4! n!
Closed f orm | }
Series f orm
1
Let k ∈ N. Let f (x) = (1−x)k
. What is the series form of f (x)

27
2.1 Lesson 1: Generating Functions 2 UNIT 2 : DIFFERENCE EQUATIONS

Solution
Let f (x) = 1
(1−x)k
= (1 − x)−k = a0 + a1 x + a2 x2 + · · · + an xn + · · ·. Therefore, f (0) = 1
(1−0)k
=
1 = a0 ⇒ a0 = 1. The interest is the find the coefficient an of our function. Before we handle
the problem, recall the following stated Theorem. Proof is left as an exercise to the learner.

Theorem 2.3 Maclaurin Series/ Taylor Series

x x2 x3 x4 xn xn
f (x) = f (0) + f 0 (0)
+ f 00 (0) + f 000 (0) + f 4 (0) + · · · f n (0) + · · · ⇒ an = f n (0)
1! 2! 3! 4! n! n!
Using Theorem 2.3 to find the series form of f (x), we have
1
f (x) = = (1 − x)−k
(1 − x)k
f 0 (x) = −k(1 − x)−k−1 (−1) = k(1 − x)−k−1
f 00 (x) = k(−k − 1)(1 − x)−k−2 (−1) = k(k + 1)(1 − x)−k−2
f 000 (x) = k(k + 1)(−k − 2)(1 − x)−k−3 (−1) = k(k + 1)(k + 2)(1 − x)−k−3
..
.
f n (x) = (k + n − 1) · · · (k + 2)(k + 1)k(1 − x)−k−n · · ·
= n!an + ()x + ()x2 + · · ·
(k − 1) (k − 2) 3 × ×2×
∴ f n (0) = (k + n − 1)(k + n − 2)(k + n − 3) × · · · × (k + 2)(k + 1)k × × ×
(k − 1) (k − 2) 3 × 2 × 1
n
   
f (0) n+k−1 (n + k − 1)! n n!
∴ an = = = since =
n! k−1 (k − 1)!n! x x!(n − x)!
Taylor’s Theorem has enabled us to generate the following counting Theorem:

Theorem 2.4
∞  
1 X n+k−1 n
= x
(1 − x)k n=0
k−1

Example 2.2

Calculate the number of non-negative integer solutions to the equation x + y + z∗ = 10 where

x≤3
Solution
x is generated by powers of z in z 0 + z 1 + z 2 + z 3
y and z∗ is generated by powers of z in z 0 + z 1 + z 2 + z 3 + · · ·.
The sum x + y + z∗ is generated from powers of z in:

z0 + z1 + z2 + z3 z0 + z1 + z2 + · · · z0 + z1 + z2 + · · ·




  
0 1 2 3

1 1
= z +z +z +z
1−z 1−z
2
1 z z z4
= + + +
(1 − z)2 (1 − z)2 (1 − z)2 (1 − z)2

28
2.1 Lesson 1: Generating Functions 2 UNIT 2 : DIFFERENCE EQUATIONS

1 z z2 z4
Let g(z) = (1−z)2
+ (1−z)2
+ (1−z)2
+ (1−z)2
. Then number of solutions to x + y + z∗ = 10 is the
10
coefficient of z in the series expansion of g(z).
Notation
C[xn ] means “Coefficient of xn of”
For example, C[x2 ](1 − 3x2 + 4x3 ) = −3 and C[x2 ](1 + 3x2 + 7x3 + 5x2 ) = 8
We want C[z 2 ]g(x). Therefore,
(∞  ∞  ∞ 
X n + 2 − 1 X 
n+2−1 n X n+2−1 n

10 10 n 2
C[z ]g(z) = C[z ] z +z z +z z
n=0
2−1 n=0
2−1 n=0
2−1
∞   )
3
X n+2−1 n
+ z z
n=0
2−1
      
10 + 2 − 1 9+2−1 8+2−1 7+2−1
= + + n decreases due to outside z’s
2−1 2−1 2−1 2−1
= 38

Example 2.3

How many non-negative integer solutions has the equation x + y + z = 10 got if x is an even
number?
Solution
x is generated by w0 + w2 + w4 + w6 · · ·.
y and z are generated by w0 + w1 + w3 + w4 · · ·.
Therefore, x + y + z is generated by, |w| < 1 :
     
0 2 4 6 1 1  2 2 2 2 3
 1 1
(w + w + w + w · · ·) = 1 + [w ] + [w ] + [w ] + · · ·
1−w 1−w 1−w 1−w
   2
1 1
= × = h(w) say
1 − w2 1−w
∴ Number of solutions = C[w10 ]h(w)
   2
10 1 1
= C[w ] ×
1 − w2 1−w
X∞ ∞
X n − 2 − 1
10 2 k
= C[w ] (w ) × wn
k=0 n=0
2 − 1

∞
X n
X n
X
0 2 4 6 0 2 4 6 1 k
w + w + w + w ··· = p + p + p + p ··· = 1−p2
= p . Since Cai = C ai , then
k=0 i=1 i=1

∞ X ∞  
X n + 2 − 1 2k+n
h(w) = w
k=0 n=0
2 − 1

29
2.1 Lesson 1: Generating Functions 2 UNIT 2 : DIFFERENCE EQUATIONS

Since (w2 )k = w2k and (w2 )k wn = w2k+n . Therefore, number of solutions these coefficients of
w10 have will be
2k + n = 10 ⇒ n = 10 − 2k ≡ C[w10 ]h(w)

Now, for the possible values of k, we get the following values of n

k n = 10 − 2k
0 10
1 8
2 6
3 4
4 2
5 0

Therefore, the number of solutions is:

           
10 + 2 − 1 8+2−1 6+2−1 4+2−1 2+2−1 0+2−1
+ + + + + = 36
2−1 2−1 2−1 2−1 2−1 2−1

Example 2.4

How many ways can one partition an integer n? (n ∈ N)

Solution
 


 3 


Lets consider n = 3, then 3 can be partitioned in: 2+1 ways. If we consider n = 4,

 

 1+1+1 
 

 4 


 

 3+1 
then 4 can be partitioned in ways. You observe that n = 3 has been


 2+1+1 


 
1+1+1+1
 
partitioned in 1’s, 2’s and 3. The same has been observed in n = 4. Therefore, n can be
partitioned using 1’s, 2’s, 3’s 4’s, · · ·, n − 1 and n. Now, the generating functions for 1’s, 2’s,
3’s 4’s, · · ·, is
10 s 20 s 30 s
z }| { z }| { z }| {
(x0 + x1 + x3 + · · ·)((x2 )0 + (x2 )1 + (x2 )3 + · · ·)((x3 )0 + (x3 )1 + (x3 )3 + · · ·) · · ·

Recall:

∞  
−k
X n+k−1 n n+k−1

(n+k−1)(n+k−2)(n+k−3)···(k+1)k
1. (1−x) = x , k ∈ R; |k| < 1. And k−1
= n!
.
n=0
k−1

30
2.1 Lesson 1: Generating Functions 2 UNIT 2 : DIFFERENCE EQUATIONS

∞
X
x 0 1 2
2. e
|{z} = x /0! + x /1! + x /2! + · · · = xk /k!. If we looking at ex × ex × ex × · · · × ex
Closed f orm k=0
| {z }
Serie f orm
(k times) we get the following product in series form
∞ ∞
X X xn1 +n2 +n3 +n4 +···nk
···
n1 =0
n !n !n n ! · · · nk !
n =0 1 2 3 4
k

n1 +n2 +n3 +n4 +···+nk

(n1 +n2 +n3 +n4 +···nk )!
3. n1 ,n2 ,n3 ,n4 ,···,nk
= n1 !n2 !n3 !n4 !···nk !

4. C[x/2](1 + x + 2x2 ) = 2[x/2]

C[x2 /5](1 − 3x2 + 4x3 ) = C[x2 /5](1 − 3 × 5x2 /5 + 4x3 ) = −3 × 5 = −15

Now,

xn1 +n2 +n3 +n4 +···nk x

   n1 +n2 +n3 +n4 +···nk 
x x x
C e × e × ··· × e = C ×
n1 !n2 !n3 n4 ! · · · nk ! n1 !n2 !n3 n4 ! · · · nk !
X (xn1 +n2 +n3 +n4 +···nk )!(xn1 +n2 +n3 +n4 +···nk )
(n1 !n2 !n3 n4 ! · · · nk !)(n1 + n2 + n3 + n4 + · · · + nk )!
ni ≥0,∀i
n1 +n2 +n3 +n4 +···nk
  X n1 + n2 + n3 + n4 + · · · nk 

x
∴C ekx =
n1 !n2 !n3 n4 ! · · · nk ! n ≥0
n1 !n2 !n3 n4 ! · · · nk !
i

 en 
Thus, C n!
= k n ways of partitioning an integer n.

Activity 2.1

Q.1 What is the sequence and closed form of the following 1, 1, 2!1 , 3!1 , · · · , r!1

Q.2 How many non-negative solutions has the equation x + y + z = 10 got if x ≥ 5.

HINT: x can be generated by t5 + t6 + t7 + · · ·

Q.3 How many non-negative solutions has the equation x + y + z = 10 got if x ≥ 5 and z is an
even number?

Q.4 How many ways can one color n circles (each circle with a single color) using 2 colors?

31
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

2.2 Lesson 2: Formulating Relations

Let a(n) be number of ways of coloring n circles with 2 colors. Thus, a(3) is equivalent to
number of ways of coloring 3 circle with 2 colors. Consider now the nth circle. This can be
colored in 2 ways. Considering the first n − 1 circles, there are a(n − 1) ways of coloring them
with 2 colors. Therefore, a(n) = 2a(n − 1) of being colored. The relations that behaves in the
manner that the second integer depends on the previous condition are called iterative relations
/difference relations and their equations are called iterative equations /difference equations.
In simple terms, if n = 1, then a(1) = 2 since once circle can be colored by any of the 2 colors.
We have now that
a(n) = 2a(n − 1); a(1) = 2

∴ a(2) = 2a(1) = 2 × 2 = 22
a(3) = 2a(2) = 2 × 22 = 23
a(4) = 2a(3) = 2 × 23 = 24
..
.
a(n) = 2a(n − 1) = 2 × 2n−1 = 2n reading pattern

Other examples

. Recursive definition of factorial :

i) 0! = 1
ii) n! = n(n-1)!, (n ≥ 1)

. Recursive definition of power

i) a0 = 1
ii) an = n(n−1) , (n ≥ 1)

In general, equations of the form:

a(n) = C1 a(n − 1) + C2 a(n − 2) + · · · + Ck a(n − k); C1 6= 0

are called Recurrence/ Recursive relation.

In all these examples we have:

a) A Basis, where the function is explicitly evaluated for one or more values of its argument.

b) A Recursive Step, stating how to compute the function from its previous values.

32
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

2.2.1 Methods of Solving Recursive Equations

Recurrence equation can be solved using different approaches. Among them, we will look at
iteration method,generating function, and root method .
ITERATIVE METHOD
Iteration approach has has been uterized in the beginning example of circle coloring in this unit.
Here are some further example of iteration method and how it works:

Example 2.5

The game of Hanoi Tower is to play with a set of disks of graduated size with holes in their
centers and a playing board having three spokes for holding the disks.

The object of the game is to transfer all the disks from spoke A to spoke C by moving one disk
at a time without placing a larger disk on top of a smaller one. What is the minimal number
of moves required when there are n disks?
Solution
Let an be the minimum number of moves to transfer n disks from one spoke to another. In
order to move n disks from spoke A to spoke C, one must move the first n − 1 disks from spoke
A to spoke B by an−1 moves, then move the last (also the largest) disk from spoke to spoke C
by one move, and then remove the n − 1 disks again from spoke B to spoke C by an−1 moves.
Thus the total number of moves should be

an = an−1 + 1 + an−1 = 2an−1 + 1

This means that the sequence {an |n ≥ 1} satisfies the recurrence relation

an = 2an−1 + 1, n ≥ 1; a1 = 1

Applying the recurrence relation again and again, we have

a1 = 2a0 + 1
a2 = 2a1 + 1 = 2(2a0 + 1) + 1
= 2 2 a0 + 2 + 1
a3 = a2 + 1 = 2(22 a0 + 2 + 1) + 1
= 2 3 a0 + 2 2 + 2 + 1

33
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

a4 = 2a3 + 1 = 2(23 a0 + 22 + 2 + 1) + 1
= 2 4 a0 + 2 3 + 2 2 + 2 + 1
..
.
an = 2n a0 + 2n−1 + 2n−2 + · · · + 2 + 1
= 2 n a0 + 2 n − 1

Let a0 = 0. The general term is given by

an = 2n − 1, n ≥ 1

Given a recurrence relation for a sequence with initial conditions. Solving the recurrence relation
means to find a formula to express the general term an of the sequence.

Example 2.6

Solve in terms of n the recurrence relation an = 2a(n−1) , a(0)=1 ; n = 1, 2, 3, 4, 5 · · ·.

Solution
We will solve this problem by linking to the knowledge of generating functions learnt so far.
Suppose f (x) = a0 + a1 x1 + a2 x2 + · · · + an xn + · · ·. Then, an = C[xn ]f (x).
Now, an = 2a(n−1) ⇒ an − 2a(n−1) = 0; n = 1, 2, 3, 4, 5 · · ·. Thus, C[xn ]xf (x) = a(n−1)
Therefore,

an − 2a(n−1) ≡ C[xn ]f (x) − 2C[xn ]xf (x) ≡ C[xn ]{f (x) − 2xf (x)}

But f (x) − 2xf (x) is crucial because:

f (x) = a0 + a1 x1 + a2 x2 + · · · + an xn + · · ·
−2xf (x) = −2a0 x − · · · − 2an(n−1) and then
f (x) − 2xf (x) = a0 + 0| +{z
0 + 0} , n ≥ 1
an −2an−1 =0

And so, f (x) − 2xf (x) = 1 ⇒ f (x)[1 − 2x] = 1. Therefore,

∞
1 X
f (x) = = (2x)k
1 − 2x k=0
∞
X
since 1
1−z
2
=1+z+z +z = 3
z k . Therefore,
k=0

an = C[xn ]2k z k = 2n

GENERATING FUNCTION METHOD

As we have seen from the Example2.6 that we have made some relationship between iterative
approach to generating function. The example that follows solves the recursive equations by
generating function.

34
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

Example 2.7

Solve the following recurrence relation an = 5an−1 − 6an−2 , a0 = 2, a1 = 9 by using generation

of function approach.
Solution
Let f (y) = a0 +ay+a2 y 2 +a3 y 3 +· · ·+an y n +· · ·. Our relation is the same as an −5an−1 +6an−2 =
0. Therefore, the generating function for the expression an − 5an−1 + 6an−2 is g(y) − 5yg(y) +
6y 2 g(y). Now,

g(y) = a0 + ay + a2 y 2 + a3 y 3 + · · · + an y n + · · ·
−5yg(y) = −5a0 − 5ay 2 − · · · − 5an−1 y n + · · ·
+6y 2 g(y) = +6a0 + 6ay 2 + · · · + 6an−1 y n + · · ·
∴ g(y) − 5yg(y) + 6y 2 g(y) = a0 + (a1 − 5a0 y) + 0 + 0 + 0
Since an − 5an−1 + 6an−2 = 0 for n ≥ 2
∴ g(y)(1 − 5y + 6y 2 ) = 2 + (9 − 5(2)y)
g(y)(1 − 5y + 6y 2 ) = 2 − y
2−y 2−y A B
∴ g(y) 2
= = + ; for some A, B.
1 − 5y + 6y (1 − 3y)(1 − 2y) 1 − 3y 1 − 2y
1 1
⇒ 2 − y = A(1 − 2y) + B(1 − 3y), ∀y ⇒ B = −3, when y = andA = 5 when y =
2 3
5 3
∴ g(y) = −
1 − 3y 1 − 2y
∞
X X∞
k
= 5 (3y) − 3 (2y)l
k=0 l=0
= C[y ]g(y) = 5 × 3n − 3 × 2n , making k and l = n
n

Homogeneous Equations
The recurrence relation a(n) = C1 a(n − 1) + C2 a(n − 2) + · · · + Ck a(n − k); C1 6= 0 is said to
be homogeneous if a(n) = 0 otherwise it is called non-homogeneous.
The coefficients Ci may depend on n, but here we will assume that they are constant unless
stated otherwise. The basis of the recursive definition is also called initial conditions of the
recurrence.
For instance, in the recursive definition of the Fibonacci sequence,

Fn = Fn−1 + Fn−2

or
Fn − Fn−1 − Fn−2 = 0

with the initial conditions are

F0 = 0, F1 = 1

35
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

is a homogeneous recurrence relation while

a(n) = 2a(n − 1) + 1 ≡ an = 2an−1 + 1

is a non-homogeneous recurrence relation.

As another example, the recursive relation

bn = 4bn−1 − 4bn−2

is homogeneous while recursive relation

am = (m + 1)am−1

is not homogeneous.
A solution of a recurrence relation is a sequence xn that verifies the recurrence. An important
property of homogeneous linear recurrences (an = 0) is that given two solutions xn and yn of
the recurrence, any linear combination of them zn = rxn + syn , where r, s are constant, is also
a solution of the same recurrence, because
k
X k
X k
X
Ci rxn−i + syn−i = r Ci xn−i + s Ci yn−i = r · 0 + s · 0 = 0.
i=0 i=0 i=0

Simplest Homogeneous Equations

The simplest homogeneous equation is of the form

an = kan−1 , k is a constant

Generally,it is presented as:

an = kan−p

Second Simplest Homogeneous Equations

The second simplest form of homogeneous equations is of the form

an = Aan−1 + Ban−2 , A, B are constants

Recall:
For an = 2an−1 , we had an = 2n .
For an = 5aa−1 − 6an−2 , we had an = C1 3n + C2 2n
For bn = 4bn−1 − 4bn−2 , we will have bn = 2n .
From these scenarios, the following Theorem follows:

Theorem 2.5

36
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

Let an = Aan−1 + Ban−2 have an = λn1 and an = λn2 as solution. Then an = C1 λ21 + C2 λ21 is
another solution, C1 and C2 constants.
Proof
Since an = λn1 and an = λn2 are solutions, then an−1 = λn−1
1 and an−1 = λn−1
2 as solution. So is
true for an−2 = λn−2
1 and an−2 = λn−2
2 as a solution to the relation an = Aan−1 + Ban−2 . Thus,
the solutions will be:

an = C1 λn1 + C2 λn2
∴ an−1 = C1 λ1n−1 + C2 λn−1
2 and
an−2 = C1 λ1n−2 + C2 λn−2
2

Considering the right hand side of our relation:

Aan−1 + Ban−2 = A C1 λ1n−1 + C2 λ2n−1 + B C1 λn−2 + C2 λ2n−2

 
   1 

 
 
 

n−1 n−2 n−1 n−2
= C1 Aλ1 + Bλ2 + C2 Aλ2 + Bλ2
|
 {z } |
 {z }
Aan−1 +Ban−2 Aan−1 +Ban−2

= C1 λn1 + C2 λn2 because λ1 and λ2 are solutions

= an

Example 2.8

Find the general solution to the relation an = 5an−1 − 6an−2 .

Solution
Let an = λn

∴ λn = 5λn−1 − 6λn−2
∴ λn − 5λn−1 − 6λn−2 = 0
λn−2 λ2 − 5λ + 6 = 0


∴ Either λn−2 = 0 or λ2 − 5λ + 6 = 0
∴ Either λn−2 = 0 or (λ − 3)(λ − 2) = 0
λ = 0 or λ = 3 or λ = 2
∴ an = 2n or 3n
∴ an = C1 2n + C2 3n is a general solution

Note that if λn−2 = 0 ⇒ λ = 0 ⇒ an = λn = 0m = 0

Example 2.9

37
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

Solve in terms of m

am = 5am−1 − 6am−2 m = 1, 2, 3, 4, · · · a0 = 1; a1 = 0

Solution
Let an = λn

∴ λm = 5λm−1 − 6λm−2
∴ λn − 5λm−1 − 6λm−2 = 0
λm−2 λ2 − 5λ + 6 = 0


∴ Either λm−2 = 0 or λ2 − 5λ + 6 = 0
∴ Either λm−2 = 0 or (λ − 3)(λ − 2) = 0
∴ λ = 0 or λ = 3 or λ = 2
But a0 = 1 6= 0 ∴ λm−2 = 0 does not hold
So that, an = 2m or 3m
∴ am = C1 2n + C2 3n is a general solution

Check
If am = 3m ⇒ a0 = 30 = 1 and a1 = 31 = 3 6= 0. Therefore, am = 3m is not a solution.
Likewise am = 2m ⇒ a1 = 2 6= 0. Therefore, am = 3m is not a solution and 2m is not a
solution as well.
Consider now the general solution am = C1 2m + C2 3m :

a0 = 1 = C 1 + C 2 (30 = 20 = 1)
a1 = 0 = 3C1 + 2C2 (31 = 3, 21 = 2)
⇒ 3 = 3C1 + 3C2 multiplying eqn 1 by 3
∴ 3 − 0 = C2 ⇒ C2 = 3
∴ 1 = C1 + C2 becomes 1 = C1 + 3 ⇒ C1 = −2

Therefore am = −2 × 2m + 3 × 3m is the unique solution.

This example is generally summarized as a root method and is hereby stated:
ROOT METHOD
A root to a homogeneous relation equation is a solution to that relation. Let am = A1 am−1 +
A2 am−2 + · · · + Ap am−p be a homogeneous relation and let λ1 , λ2 , · · · , λp be roots of the
polynomial
λp = A1 λp−1 + A2 λp−2 + · · · + Ap λ + Am−p

where no two λi ’s are equal, then

am = C1 λm m m
1 + C 2 λ2 + · · · + C p λp

38
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

is a general solution.
The equation λp = A1 λp−1 + A2 λp−2 + · · · + Ap λ + Am−p of the roots of a relation am =
A1 am−1 + A2 am−2 + · · · + Ap am−p is called a Characteristic equation
The generalization of the relation ushers into the following Theorem:

Theorem 2.6

Let am = Aam−1 + Bam−2 be such that λ2 = Aλ + B has one repeated root λ = λ1 = λ2 . Then
the general solution is
am = C1 λm + C2 mλm

Example 2.10

Find the general solution to the relation equation an = 4an−1 − 4an−2 .

Solution
Let an = λn ’ Then, λn = 4λn−1 − 4λn−2 .

λn − 4λn−1 − 4λn−2 = 0
λn−2 (λ2 − 4λ + 4) = 0
λn−2 = 0 or λ2 − 4λ + 4 = 0
∴ λ2 − 4λ + 4 = 0 ⇒ (λ − 2)2 = 0
∴ λ = 2 repeated
∴ The general solution is an = k1 2n + k1 n2n

Activity 2.2

Q.1 Find an explicit formula for each of the sequences defined by the recurrence relations with
initial conditions.

i. xn = 5xn−1 + 3, x1 = 3
ii. xn = 2xn−1 + 15xn−2 , x1 = 2, x2 = 4.
iii. xn = 3xn−1 − 2xn−2 , x0 = 2, x1 = 4.

Q.2 Find an explicit formula for each of the sequences defined by the non-homogeneous recur-
rence relations with initial conditions.

39
2.2 Lesson 2: Formulating Relations 2 UNIT 2 : DIFFERENCE EQUATIONS

i. xn = 2xn−1 + 15xn−2 + 2n 3, x1 = 2, x2 = 4.
ii. xn = 4xn−1 + 5xn−2 + 3, x1 = 3, x2 = 5.
iii. xn = 6xn−1 − 9xn−2 + 3n+2 , x0 = 3, x1 = 9.

Q.3 Find an explicit formula of the following sequence defined by the recurrence relations with
its initial condition
x2n = 2xn + 5 − 7n, x1 = 0.

40
 3 UNIT 3 : PIGEON-HOLE PRINCIPLE

3 Unit 3 : Pigeon-hole Principle

Introduction
Pigeonhole principle is a fundamental but powerful tool in combinatorics. Unlike many other
strong theorems, the principle itself is exceptionally simple. Unless you have looked into it
thoroughly, it is hard to have a glimpse of its elegance and useful applications in mathematics.

Objectives/Learning Outcomes
By the end of this Unit, you should be able to:

(a) Understand pigeon-hole principle

(b) Solve problems of simple form of pigeon-hole principle

(c) Solve problems of regular form of pigeon-hole principle

(d) Solve problems of extended form of pigeon-hole principle

Key Terms
Simple form, Regular form, Extended form.

3.1 Lesson 1: Pigeon-hole Principle (PHP)

Assume you have a set of objects and a set of bins used to store objects. The pigeon-hole
principle states that if there are more objects than bins then there is at least one bin with more
than one object. For instance, if we want to store 7 balls in 5 bins, then atleast one bin will
store atleast one ball. Visually, the scenario is presented as:

41
3.2 Lesson 2: Simple Form of PHP 3 UNIT 3 : PIGEON-HOLE PRINCIPLE

Activity 3.1

Q.1 In your own terms, how can you describe pigeon-hole principle.

Q.2 Give 3 practical examples that can be modeled using pigeon-hole principle.

3.2 Lesson 2: Simple Form of PHP

The simplest form of pigeon-hole principle is just the generalization of the understanding we
have had and the following Theorem follows:

Theorem 3.1 Simplest Form of Pigeon-hole Principle

If there are k + 1 objects and k bins. Then there is at least one bin with two or more objects.
Proof
We prove by contradiction. Suppose we have k + 1 objects and every bin has at most one
element. Then the total number of elements is k which contradicts our Theorem. Hence, the
theorem is true.

Example 3.1

In Malawi, there exists atleast 2 persons with the same bank pin number.
Solution
Bank in Malawi use four-digit sequence of numbers,

and by product rule we have 10,000 possible pin-codes. Common judgment is that all banks in
Malawi must issue more than 10,000 ATM cards. Taking any 10, 001 = 10, 000 + 1 customers
as objects and the n = 10, 000 pin-codes as pigeon-holes. By pigeon-hole principle, there exists
atleast a pair with same pin numbers.

Example 3.2

Let A be set of numbers: A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Given that 6 different numbers are
chosen from this set. Show that:

a) among the 6 chosen, there exist a pair of consecutive digits.

42
3.2 Lesson 2: Simple Form of PHP 3 UNIT 3 : PIGEON-HOLE PRINCIPLE

b) among the the 6, there exists a pair whose sum is 11

Solution

a) Let 1, 2, 3, 4 and 5 be five pairing to stand for n = 5 pigeon-holes. Thus, 1 is a pairing (1,2),
2 is a pairing (3,4), 3 is a pairing (4, 5) and so on. Regard the 6 = n + 1 chosen numbers
as letters. By pigeon-hole principle, there exists atleast two numbers to be chosen from the
same block (pairing). Therefore, The pair chosen from the same block is consecutive (by
design).

b) Let 1, 2, 3, 4, 5 be a pairing that gives us a sum of 11. For instance, 1 is a pairing (10, 1), 2
is a pairing (5, 6) and so on. Regard the 6 = n + 1 chosen numbers as letters. By pigeon-
hole principle, there exists atleast two numbers whose sum add up to 11 and they are not
consecutive.

Example 3.3

Let M = 9 and N = 7. Show that there exists an integer of the form 999 · · · 900 · · · 0 that is
divisible by N = 71.
Solution
Let a1 , a2 , a3 , · · · be such that a1 = 9, a2 = 99, a3 = 999, · · · , a71 = 999
| {z· · · 9} , · · ·. When any
71 of them
positive integer is devided by 71 we have the possible remainders as 0, 1, 2, 3, · · · , 70 with 0 as
minimum remainder and 70 as a maximum remainder.
Let R1 be a remainder when a = 9 is divided by 71.
R2 be a remainder when a2 = 99 is divided by 71
R3 be a remainder when a3 = 999 is divided by 71
..
.
R71 be a remainder when a71 is divided by 71
Therefore, R1 , R2 , R3 ·R71 ∈ {0, 1, 2, 3, · · · , 70}. Likewise R1 , R2 , R3 · · · R71 , R72 ∈ {0, 1, 2, 3, · · · , 70}.
| {z } | {z }
72 numbers 71 numbers
By pigeon-hole principle, there exists 2 remainders that get the same value, say, Ri = Rj , (i < j).

| · · ·{z
999 999 · · · 9} = aj = 71n + Rj , n ∈ {0} ∪ N
j times
999
| {z· · · 9} = ai = 71n + Rj , m ∈ {0} ∪ N i<j
i times
i of them
z }| {
∴ 999 · · · 9 000 · · · 0 = 71n − 71m
i of them
z }| {
999 · · · 9 000 · · · 0 = 71(n − m) since n ≥ m, aj > ai

Therefore, 999 · · · 900 · · · 0 is divisible by 71.

43
3.3 Lesson 3: Regular Form of PHP 3 UNIT 3 : PIGEON-HOLE PRINCIPLE

Activity 3.2

Q.1 Show that if one choose five points from a 2 × 2 square, there will be two points that will
√
lie no more that 2 apart.

Q.2 Show that atleast 2 people in a class of 367 students share the same birth date.

Q.3 Let a1 , a2 , a3 , · · · , an+1 be a sequence of non-negative integers. Prove that either a term in
the sequence or sum consecutive terms in the sequence is divisible by n.

Q.4 There are some people (more than 1 person) in a party. Prove that 2 of them have the
same number of friends in the party. (It is assumed that friendship is mutual. That is if A
is a friend of B, then B is a friend of A.)

3.3 Lesson 3: Regular Form of PHP

Simpler form of pigeon hole principle considers that there if there are k + 1 objects and k bins.
Then there is at least one bin with two or more objects. The regular form considers a situation
when there are more than r objects to be placed in k bins. It is stated in the following Theorem.

Theorem 3.2 Regular Form of Pigeon-hole Principle

If rk + 1 objects are placed in k pigeon-holes, then there exists a pigeon-hole with more than
r objects
Proof
We prove by contradiction. Suppose the Theorem does not hold, thus, Theorem is false. Then
each of the n pigeon-holes has at most r objects. Therefore, the total number of objects in the
n pigeon-holes is less than or equal to rk . This contradicts that the total number of objects
was rk + 1 .Therefore, the Theorem is true.

Example 3.4

In a group of 49 people, show that more than four people were born in the same month.
Solution
Regard 49 persons as blocks. Let the 12 months of the year be regarded as pigeon-holes.
Therefore49 = 12 × 4 + 1 where k = 12 and r = 4. Therefore, by regular form of pigeon-hole
principle, there exist a month with more than r = 4 people born in it among the 49 persons.
Therefore, atleast 5 persons are born in that month because number of persons is an integer.

44
3.3 Lesson 3: Regular Form of PHP 3 UNIT 3 : PIGEON-HOLE PRINCIPLE

Example 3.5

Prove that among any group of six persons; there exists 3 persons who are mutual friends or
non-mutual friends. Mutual friends are people who know each other well.
Solution
Consider the following visual aid:

Let a solid line represent mutual friend connection and a dotted be the non-mutual friends.
Isolate the 6th person and consider his or her mutual and non-mutual friends. We have that
5 = 2 × 2 + 1, where k = 2 and r = 2.

Dropping the 5 lines in the 2 boxes, then by regular form form of pigeon principle, there exists
a box with more than 2 lines in it. We would observe that if any two persons, e.g 5 and 4 are
joined by a solid line with respect to the 6th person, we have 3 mutual friends. The opposite
happens when any two persons are joined by a dotted line to have non-mutual friends.

Activity 3.3

Q.1 There are 17 mathematicians and 3 official languages. Every pair of mathematicians com-
municate in one of the official languages. Prove that there are 3 mathematicians commu-
nicating in the same language pairwise.

45
3.4 Lesson 4: Extended Regular Form of PHP3 UNIT 3 : PIGEON-HOLE PRINCIPLE

Q.2 A child drinks at least 1 bottle of milk a day. Given that he has drunk 700 bottles of milk
in a year of 365 days, prove that for he has drunk exactly 29 bottles in some consecutive
days.

Q.3 27 points are aligned so that each row has 9 points and each column has 3 points. (A
column is perpendicular to a row.) Each point is painted in red or blue. Prove that there
exists a monochromatic rectangle (i.e. 4 vertices are of the same colour) with its sides
parallel to the rows and columns.

3.4 Lesson 4: Extended Regular Form of PHP

Understanding this section requires some previous knowledge. Lets revisit the idea.
Revision on Largest Integer Function
bxc is the largest integer function. For instance, b3.4c = 3 and b7c = 7. We also know that
4 8
3
× 3 = 4 and 2
× 2 = 8. What about b xy cy? Example, b 28 c2 = 8 and b 34 c3 = 4 This deduces to
the following fact which introduces the follow-up Theorem:
FACT: b xy cy ≤ x

Theorem 3.3 :Extended Regular Form of PHP

If m objects are placed in the k pigeon-holes, then there exists a pigeon-hole with more than
b m−1
k
c objects.
Proof
Suppose the Theorem is false, thus all the k pigeon-holes have ≤ b m−1
k
c. Therefore, the total
number of objects in all the pigeon-holes will be ≤ b m−1
k
ck ≤ m − 1. This contradicts the fact
that we had m letters in total.

Corollary 3.1 Extended PHP

x1 +x2 +···+xn
Let x1 , x2 , · · · , xn be numbers and x̄ = n
. Then:

a) There exist xi ∈ {x1 , x2 , · · · , xn } such that xi ≤ x̄ and

b) There exist xi ∈ {x1 , x2 , · · · , xn } such that xi ≥ x̄

Proof

a) Assume that part (a) is not true. Therefore, x1 > x̄, x2 > x̄, x3 > x̄, · · ·, xn > x̄

⇒ x1 + x2 + x3 + · · · + xn > x̄ {z· · · + x̄}

| + x̄ +
n times
⇒ x1 + x2 + x3 + · · · + xn > nx̄
x1 + x2 + x3 + · · · + xn
⇒ > x̄ since n > 0
n
⇒ x̄ > x̄. This is a contradiction

46
3.5 Lesson 5: Generalized PHP 3 UNIT 3 : PIGEON-HOLE PRINCIPLE

b) This part follows likewise.

Example 3.6

A Secondary school has 401 students in forms 1, 2, 3 and 4. Show that

a) There exists a form with atleast 101 students in it

b) There exists a form with no more than 100 students in it.

Solution

a) Let m = 401, k = 4 forms. By extended regular form, there exists a form with more than
401 students take away 4 forms. Thus, ∃ a form with > b 401−1
4
c = b 400
4
c = 100 students in
it.

Because the number of the students is an integer, it follows that the nest digit is 101 as per
meaning of atleast.
OR
By applying the corollary:

x1 +x2 +x3 +x4 401

Let xi be number of students in the form i, i = {1, 2, 3, 4}. Therefore, 4
= 4
=
100 14 . Then there exist xi such that xi ≥ 100 14 . Since xi ∈ {0} ∪ N, then (xi ≥ 100 41 ) ≡
(xi ≥ 101)

b) There exists xi ≤ 100 14 (by corollary). Since xi is an integer, then xi ≤ 100.

Activity 3.4

Q.1 Suppose 51 keys are randomly dropped in a boxes labeled {1, 2, 3, 4, · · · , 10}. Let yk
be the keys dropped into boxes {1, 2, 3, 4, · · · 10}. Find the minimum and maximum
{y1 , y2 , y3 , · · · y10 }.

3.5 Lesson 5: Generalized PHP

This is a generalization of all the principles we have covered so far. It is stated in the following
Theorem:

Theorem 3.4 Generalized Pigeon-Hole Principle

47
3.5 Lesson 5: Generalized PHP 3 UNIT 3 : PIGEON-HOLE PRINCIPLE

Let q1 + q2 + q3 + · · · + qr − r + 1 objects be placed in r pigeon-holes, qi ∈ N. Then:

The first pigeon-hole has ≥ q1 objects or
The second pigeon-hole has ≥ q2 objects or
The third pigeon-hole has ≥ q3 objects or
..
.
The rth pigeon-hole has ≥ qr objects

Proof
Suppose the Theorem was false. Remember that ∼ (p ∨ Q) = ∼ P ∧ ∼ Q. Therefore,
The first pigeon-hole has < q1 objects and
The second pigeon-hole has < q2 objects and
The third pigeon-hole has < q3 objects and
..
.
The rth pigeon-hole has < qr objects
But < q1 ≡ ≤ q1 − 1, thus, pigeon-hole i has at most qi − 1 objects in it. Similarly,
< q2 ≡ ≤ q2 − 1 (i > 1, 2, 3, · · · , r)
Therefore, r pigeon-holes will have at most (q1 − 1) + (q2 − 1) + · · · + (qr − 1) = q1 + q2 +
q3 + · · · + qr − r. This contradicts the fact that we had q1 + q2 + q3 + · · · + qr − r + 1 objects.
Therefore, the Theorem cannot be false. Hence the Theorem is true.

Example 3.7

Suppose 10 mangoes are placed in a basket, carton and a basin. Deduce that the basket has
atleast three mangoes or the carton has atleast four mangoes or the basin has atleast five
mangoes.
Solution
Lets regard the basket, the carton and the basin as our three pigeon-holes, thus r = 3. Let
q1 = 3, q2 = 4 and q3 = 5. We see that q1 + q2 + q3 − 3 + 1 = 10. Hence, by generalized
pigeon-hole principal, the result follows.

Example 3.8

A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest
number of pieces of fruit that should be put in the basket in order to guarantee that either there
are at least 8 apples or atleast 6 bananas or at least 9 oranges?
Solution
By generalized pigeon-hole principle, the answer is 8 + 6 + 9 − 3 + 1 = 21

48
3.5 Lesson 5: Generalized PHP 3 UNIT 3 : PIGEON-HOLE PRINCIPLE

Activity 3.5

1. A football match is being arranged out of Chanco FC, Mzuni FC, Big Bullets FC, Won-
drous FC and Chitipa FC. What is the smallest number of goals that should be scored
in order to guarantee that either there are at least 5 goals for Chanco FC or 2 goals for
Mzuni FC or 1 goal for Big Bullets FC or 9 goals for Wondrous FC or 20 goals for Chitipa
FC?

49
 4 UNIT 4: GRAPH THEORY BASICS

4 Unit 4: Graph Theory Basics

Introduction
The field of graph theory began to blossom in the twentieth century as more and more modeling
possibilities were recognized and the growth continues. It is interesting to note that as specific
applications have increased in number and in scope, the theory itself has developed beautifully
as well. In this Unit we investigate some of the major concepts and applications of graph theory.

Objectives/Learning Outcomes
By the end of this Unit, you should be able to define:

(a) Vertex, Edge and Valency/degree

(b) paths’s, trails, chains and cycles

(c) vertex colouring and time tabling

(d) spanning trees:search trees and genetic tree

(e) come up with allocation problem and networks

Key Terms
Vertex, Edge, Path, Trail, Cycle, Tree, Valency, Chains

50
4.1 Lesson 1: Vertex, Edge and Valence 4 UNIT 4: GRAPH THEORY BASICS

4.1 Lesson 1: Vertex, Edge and Valence

Vertex (V) is a set of point(s) that is either the endpoint of an edge or not part of an edge.
The vertex represents a place.
Edge (E) is a set line segment(s) connecting the vertices of a graph. The edge represents a
distance.

Figure 5: Visual representation of a Graph

Graph (G) consists of two finite sets, V and E. Each element of V is called a vertex (plural
vertices). The elements of E, called edges, are unordered pairs of vertices. For instance, the
set V might be {A, B, C, D, E} and E might be {{A, B}, {B, C}, {C, D}, {A, E}}. Together V
and E are a Graph, denoted G(V, E).
Valency/Degree of vertex v a graph, denoted deg(v), is the number of edges incident with v.
For instance, in Figure 5, the degree of Vertex A is 3 while the degree of vertex E is 1.
The maximum degree of a graph G, denoted by 4(G), is defined to be

4(G) = max{deg(v)|v ∈ V (G)}

In a similar way, the minimum degree of a graph G, denoted by δ(G), is defined to be

δ(G) = min{deg(v)|v ∈ V (G)}

For instance, the graph of Figure10 has 4G = 2 and δG = 1. Consequently we have the
following Theorem which is referred to as the First Theorem of Graph Theory.

Theorem 4.1 Valency of a Graph

In a graph G, the sum of the degrees of the vertices is equal to twice the number of edges.
Consequently, the number of vertices with odd degree is even.
Proof
X
Let S = deg(V ). Take note that in counting S, we count each edge exactly twice. Thus,
v∈V
S = 2|E| (the sum of the degrees is twice the number of edges). Since S is even, it must be
that the number of vertices with odd degree is even. This concludes the proof.

51
4.1 Lesson 1: Vertex, Edge and Valence 4 UNIT 4: GRAPH THEORY BASICS

Graphs have natural visual representations. Look at the diagram in Figure 5. Notice that each
element of V is represented by a small circle and that each element of E is represented by a line
drawn between the corresponding two elements of V .
In simple terms, we can just as easily define a graph to be a diagram consisting of small circles,
called vertices, and curves, called edges, where each curve connects two of the circles together.
When we speak of a graph in this chapter, we will almost always refer to such a diagram. We
can obtain similar structures by altering our definition in various ways. Here are some examples

I. By replacing our set E with a set of ordered pairs of vertices, we obtain a directed graph
or digraph. Each edge of a digraph has a specific orientation.

Figure 6: Directed graph

II. if we allow repeated elements in our set of edges, technically replacing our set E with a
multiset, we obtain a multigraph.

Figure 7: Multigraph

III. By allowing edges to connect a vertex to itself (“loops”), we obtain a pseu-dograph

52
4.1 Lesson 1: Vertex, Edge and Valence 4 UNIT 4: GRAPH THEORY BASICS

Figure 8: Pseudograph

IV. Allowing our edges to be arbitrary subsets of vertices (rather than just pairs) gives us
hypergraphs

Figure 9: Hypergraph with 7 vertices and 5 edges

V. By allowing V or E to be an infinite set, we obtain infinite graphs.

Activity 4.1

Q.1 Ten people are seated around a circular table. Each person shakes hands with everyone
at the table except the person sitting directly across the table. Draw a graph that models
this situation.

Q.2 Six colleagues (Adam, Masoambeta, Chimwemwe , Dave, Ken,and Frank) need to pair off
as roommates for the upcoming school year. Each person has compiled a list of the people
with whom he would be willing to share a room.

Adam’s list: Dave

Masoambeta’s list: Adam, Dave
Chimwemwe’s list: Ken, Frank

53
4.2 Lesson 2: Walks, Paths’s, Trails 4 UNIT 4: GRAPH THEORY BASICS

Davie’s list: Masoambeta

Ken’s list: Dave
Frank’s list: Adam, Chimwemwe
Draw a digraph that models this situation.

4.2 Lesson 2: Walks, Paths’s, Trails

Walk : A walk in a graph G is a finite sequence

W ≡ v0 e1 v1 e2 · · · vk−1 ek vk

whose terms are alternately vertices and edges such that for 1 ≤ i ≤ k, the edge ei has ends
vi−1 and vi .
Thus, each edge ei is immediately preceded and succeeded by the two vertices with which it is
incident. We say that W is a v0 − vk walk or a walk from v0 to vk .
Origin and terminus: The vertex V0 is the origin of the walk W , while vk is called the terminus
of W . v0 and vk are not distinct. The vertices v1 , v2 , · · · , vk−1 in the above walk W are called
its internal vertices. The integer k, the number of edges in the walk, is called the length of W ,
denoted by |W |.
Repetition of vertices and edges in a walk W is applicable. Oftentimes, we may meet trivial
walks.
Trivial walk : A trivial walk is one that does not contain any edge. Thus, for any vertex v of
G, W ≡ v gives a trivial walk. Its length is 0.

Figure 10: A graph with five vertices and ten edges

In Figure10, W1 ≡ v1 e1 v2 e5 v3 e10 v3 e5 v2 e3 v5 and v1 e1 v2 e1 v1 e1 v2 are both walks of length 5 and 3,

respectively from v1 to v5 and from v1 and v2 , respectively.

54
4.2 Lesson 2: Walks, Paths’s, Trails 4 UNIT 4: GRAPH THEORY BASICS

Given two vertices u and v of a graph G, a u − v walk is closed or open depending on whether
u = v or u 6= v. The walks W1 and W2 above are both open while W3 ≡ v1 v5 v2 v4 v3 v1 is closed
in Figure10
Trail : If the edges e1 , e2 , · · · , ek of the walk W ≡ v0 e1 v1 e2 v2 · · · · · · ek vk are distinct then W is
called a trail. In other words, a trail is a walk in which no edge is repeated. W1 and W2 are
not trails, since for instance e5 is repeated in W1 , while e1 is repeated in W2 . However, W3 is
a trail.
A trail that begins and ends at the same vertex is called a closed trail , or circuit
Path: If vertices v0 , v1 , · · · vk of the walk W ≡ v0 e1 v1 e2 v2 · · · · · · ek vk are distinct then W is
called a path. Any two paths with the same number of vertices are said to be isomorphic paths.
A path with n vertices is sometimes denoted as Pn . Realize that Pn has length n − 1. In other
words, a path is a walk in which no vertex is repeated . Thus, in a path no edge can be repeated
either, so a every path is a trail. This is not true for the trails. Thus, not every trail is a path.
For instance, W3 is not a path since v1 is repeated. However, W4 ≡ v2 v4 v3 v5 v1 is a path in the
graph G as shown in Figure 10
A closed path, or cycle is a path v1 , · · · · · · vk (where k ≥ 3) together with the edge vk v1 .

Activity 4.2

Q.1 If G is a graph of order n, what is the maximum number of edges in G?

Q.2 Prove that for any graph G of order at least 2, the degree sequence has atleast one pair of
repeated entries.

Q.3 Consider the graph shown in Figure11

Figure 11:

i. How many different paths have c as an end vertex?

55
4.3 Lesson 3: Disconnectedness of Graphs 4 UNIT 4: GRAPH THEORY BASICS

ii. How many different paths avoid vertex c altogether?

iii. What is the maximum length of a circuit in this graph? Give an example of such a
circuit.
iv. What is the maximum length of a circuit that does not include vertex c? Give an
example of such a circuit.

Q.4 Let G be a graph where δ(G) ≥ k.

i. Prove that G has a path of length at least k.

ii. If k ≥ 2, prove that G has a cycle of length at least k + 1.

4.3 Lesson 3: Disconnectedness of Graphs

Before introducing disconnectedness of graphs, let us explore the two operations on graphs:
vertex deletion and edge deletion.
Given a graph G and a vertex v ∈ V , we let G − v denote the graph obtained by removing v
and all edges incident with v from G. If S is a set of vertices, we let G − S denote the graph
obtained by removing each vertex of S and all associated incident edges. If e is an edge of G,
then G − e is the graph obtained by removing only the edge e (its end vertices stay). If T is
a set of edges, then G − T is the graph obtained by deleting each edge of T from G. These
operations are visually elaborated in the Figure 12.

Figure 12: Deletion Operations.

Having paid attention to operations on the graph, lets turn our focus on this unit.
A graph is connected if every pair of vertices can be joined by a path. Informally, if one can pick
up an entire graph by grabbing just one vertex, then the graph is connected. On contrary, if the
graph is not connected, then it is disconnected . Figure13 shows connected and disconnected
graphs.

56
4.3 Lesson 3: Disconnectedness of Graphs 4 UNIT 4: GRAPH THEORY BASICS

Figure 13: Connected and disconnected graphs.

In Figure13, G1 is connected, and both G2 and G3 are disconnected. Each maximal connected
piece of a graph is called a connected component. In Figure 13, G1 has one component, G2 has
three components, and G3 has two components.
If the deletion of a vertex v from G causes the number of components to increase, then v is
called a cut vertex . In the graph G of Figure 12, vertex d is a cut vertex and vertex c is not.
Similarly, an edge e in G is said to be a bridge if the graph G − e has more components than
G. In Figure12, the edge ab is the only bridge.
A proper subset S of vertices of a graph G is called a vertex cut set (or simply, a cut set) if the
graph G − S is disconnected. A graph is said to be complete if every vertex is adjacent to every
other vertex. Consequently, if a graph contains atleast one nonadjacent pair of vertices, then
that graph is not complete. Complete graphs do not have any cut sets, since G − S is connected
for all proper subsets S of the vertex set. Every non-complete graph has a cut set, though, and
this leads us to another definition.

Definition 4.1 Graph Connectivity

For a graph G which is not complete, the connectivity of G, denoted k(G), is the minimum size
of a cut set of G. If G is a connected, non-complete graph of order n, then 1 ≤ k(G) ≤ n − 2. If
G is disconnected, then k(G) = 0. If G is complete of order n, then we say that k(G) = n − 1.
Further, for a positive integer k, we say that a graph is k − connected if k ≤ k(G). You will
realize that “1-connected” simply means “connected”.
Here are several facts that follow from these definitions. You will get to prove a couple of them
in the exercises.

a) A graph is connected if and only if k(G) ≥ 1.

b) k(G) ≥ 2 if and only if G is connected and has no cut vertices.

c) Every 2-connected graph contains at least one cycle.

d) For every graph G, k(G) ≤ δ(G).

57
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

Activity 4.3

Q.1 Draw a connected graph having at most 10 vertices that has at least one cycle of each
length from 5 through 9, but has no cycles of any other length.

Q.2 Let P1 and P2 be two paths of maximum length in a connected graph G. Prove that P1
and P2 have a common vertex.

Q.3 Let G be a graph of order n that is not connected. What is the maximum size of G?

Q.4 Let G be a graph of order n and size strictly less than n − 1. Prove that G is not connected.

Q.5 Prove or disprove each of the following statements.

i. If G has no bridges, then G has exactly one cycle.

ii. If G has no cut vertices, then G has no bridges.
iii. If G has no bridges, then G has no cut vertices.

Q.6 Prove or disprove: If every vertex of a connected graph G lies on at least one cycle, then
G is 2-connected.

Q.7 Prove that every 2-connected graph contains at least one cycle.

Q.8 Prove that for every graph G,

i. k(G) ≤ δ(G);
ii. if δ(G) ≥ n − 2, then k(G) = δ(G)

4.4 lesson 4: Vertex Colouring & Time Tabling

Colouring the vertices in graph G means assigning colours to the vertices such that each edge
in G has ends of two different colours. In other words, its the assignment of colours to vertices
(each vertex with one colour) of the graph such that no pair of adjacent vertices share the same
colour. The paired vertices that joins an edge between them are said to be adjacent to each
other. We are also usually seeking to determine a colouring that uses as few colours as possible.
The smallest number of colours needed to colour the vertices in a graph G is called the chromatic
number of G and is noted as χ(G).

58
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

Figure 14: Graph chromatic number

From the Figure 14, Graph A is a null graph whose χ(D) = 1, Graph B by definition has no
chromatic number while Graph C has χ(D) = 2.
If all colours have been assigned to the vertices of a graph so that no two adjacent vertices have
the same 1- color, the graph is said to be properly coloured . A k −coloring of a graph is a proper
coloring involving a total of k colors. A graph that has a k−coloring is said to be k − colorable.
In other words, the graph G is k − chromatic if χ(G) = k.
In a proper colouring, each colour class is a stable set. Hence a k − colouring may also be seen
as a partition of the vertex set of G into k disjoint stable sets Si = {v|c(v) = i} for 1 ≤ i ≤ k.
Therefore k−colourable are also called k-partite graphs. Moreover, 2−colourable graphs are
very often called bipartite. It is clear now that if H is a subgraph of G then any proper colouring
of G is a proper colouring of H.

Theorem 4.2 Chromatic Number

Let G = (V, E) be any simple graph. Let χ(G) be the chromatic number and 4(G) be the
valency in G, then:
χ(G) ≤ 4(G) + 1

Proof
The proof for this is done via induction approach. Let G = (V, E) be such that |v| = n. We
consider first case where the color is 1.
Case 1: n = 1
This gives us a degree say X such that x = 0 = 4(G). Thus

χ(G) = 1 ≤ 0 + 1 = 1.

Case one holds.

Case 2: n = 2
In here, we have two colours, say (X, y). Two cases arise. Either the graph is connected or the
graph is not connected as portrayed in Figure17

59
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

Figure 15:

When the graph is not connected, the 4(G) = 0 and χ(G) = 1. Hence χ(G) ≤ 4(G) + 1. This
is true.
When the graph is not connected, the 4(G) = 1 and χ(G) = 2. Hence χ(G) ≤ 4(G) + [Link]
is also true.
Therefore, case 2 also holds.
Case 3: For Pn true ⇒ Pn+1 true
This is an inductive stage. Let Pn be the statement that “for a simple graph of n vertices one
has χ(G) ≤ 4(G) + 1”. There is need to show that for Pn true ⇒ Pn+1 is also true.
Let G have n + 1 vertices.

Figure 16:

Let G∗ be the graph after removal of some vertex x together with its adjacent edges. Therefore
G∗ has n vertices. If Pn is true, then χ(G) ≤ 4(G) + 1.

Figure 17:

The number of edges connected (adjacent to x) is ≤ 4(G). This means that we will vertex
colour G∗ with χ(G) colours. Hence χ(G∗ ) ≤ 4(G) + 1. Since Pn is true, it implies ≤ 4(G) + 1
is true. Thus G∗ ≤ G.

60
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

Since we can vertex G∗ with χ(G∗ ), take 4(G) + 1 colours. Remove vertex colouring of G∗ and
re-vertex colour G∗ using 4(G) + 1 colours. Then there exists a colour not adjacent to x (by
pigeon-hole principle). Hence use that colour on x. This means that G has been coloured with
4(G) + 1 colours. Therefore χ(G) ≤ 4(G) + 1. Thus Pn+1 is also true.
The Theorem is so powerful and most useful in our daily lives especially when it comes to
time-tabling.

Example 4.1

Suppose that you are responsible for scheduling times for lectures in a university. You want
to make sure that any two lectures with a common student occur at different times to avoid a
conflict.
Solution
We could put the various lectures on a chart and mark with an X any pair that has students in
common:

Figure 18: Time tabling

A more convenient representation of this information is a graph with one vertex for each lecture
and in which two vertices are joined if there is a conflict between them:

Figure 19: Time tabling graphical presentation

61
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

Now, we cannot schedule two lectures at the same time if there is a conflict, but we would like
to use as few separate times as possible, subject to this constraint. How many different times
are necessary?
We can code each time with a color, for example 08:00-09:00 might be given the color green,
and those lectures that meet at this time will be colored green. The no-conflict rule then means
that we need to color the vertices of our graph in such a way that no two adjacent vertices
(representing courses which conflict with each other) have the same color. So what we seek is
a k − coloring of our graph with k as small as possible. Here is a 4 − coloring of the graph:

Figure 20: 4 - colouring

Question: Is there a proper coloring that uses less than four colors? Clearly we cannot get by
with less than three colors, since G, H, and L are all adjacent to each other. So the question
becomes: Can we find a 3-coloring? The answer is negative. We shall suppose that we can
properly color the graph with only three colors, and show that this leads to a contradiction. We
start by coloring G, H, and L three different colors, as we must. We might as well assume they
are the colors as shown above. Then M must be the same color as H, since M is adjacent to G
and L and there are only three colors available. So we color M blue as shown above. In a like
manner, I must be colored green since it is adjacent to L and M , which we have determined
to be red and blue. Now S is adjacent to G, H, and L, and so it must be a different color from
them all. So we cannot make do with only three colors. So four colors are needed to properly
color the graph. This means that we need to have at least four different times for lectures in
our school.
How do we determine the chromatic number of a graph? In example4.1 , we did it by first finding
a 4-coloring, and then making an intricate argument that a 3-coloring would be impossible. It
may be quite difficult to compute the chromatic number of more complicated graphs. Can we
at least make an upper bound on the number of colors we need, even if we cannot find the
minimum number? There is an algorithm (procedure) for properly coloring vertices that does
not always use as few colors as possible, but at least gives us an upper bound on the number of
colors needed.

62
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

4.4.1 The Greedy Algorithm For Colouring Vertices

The algorithm is called greedy because it is a rather short-sighted way of trying to make a proper
colouring with as few colors as possible. It does not always succeed in finding the minimum
number (the chromatic number), but at least provides some proper coloring. The procedure
requires us to number consecutively the colors that we use, so each time we introduce a new
color, we number it also. Here is the procedure:

1. Color a vertex with color 1.

2. Pick an uncolored vertex v. Color it with the lowest-numbered color that has not been used
on any previously-colored vertices adjacent to v. (If all previously-used colors appear on
vertices adjacent to v, this means that we must introduce a new color and number it.)

3. Repeat the previous step until all vertices are colored.

Clearly, this produces a proper coloring, since we are careful to avoid conflicts each time we
color a new vertex. How many colors will be used? It is hard to say in advance, and it depends
on what order we choose to color the vertices.

Example 4.2

Suppose we decide to color the course conflict graph using the Greedy Coloring. Algorithm, and
we decide to color the vertices in order G, L, H, P, M, A, I, S, C. Then we would color G with
color 1 (green), L with color 2 (red) since adjacency with G prevents it from receiving color
1 (green), and we color H with color 3 (blue) since adjacency with G and L prevents it from
receiving colors 1 and 2 (green and red). So we have

P and M also cannot receive colors 1 and 2 (green and red), so they are given color 3 (blue):

63
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

Then A cannot receive colors 1 and 3 (green and blue), so we give it color 2 (red), while I
cannot receive colors 2 and 3 (red and blue), so we give it color 1 (green).

Vertex S cannot receive color 1, 2, or 3, and so we give it color 4 (say, yellow). Vertex C cannot
receive color 2 or 4 (red or yellow), so we give it color 1 (green). We obtain the same coloring
we had proposed earlier:

On the other hand, we could imagine choosing a different order. Suppose we chose to color the
vertices in the order A, I, P, M, S, C, H, L, G. First we color A with color 1 (green) and also I
and P color 1.

64
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

Then we color M and S with color 2 (red), because they cannot be colored green.

Then we color C and H with color 3 (blue), because they cannot be colored green or red.

We color L with color 4 (yellow), because it cannot be colored with green, red, or blue.

65
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

We color G with color 5 (light blue), because it cannot be colored with any of the four other
colors.

So we see that the quality of our coloring (with fewer colors being considered better) from the
Greedy Coloring Algorithm is dependent on the order in which we color the vertices.
Nonetheless, there is a certain minimum quality we get, which we can determine by the following
theoretical argument: Suppose that d is the largest degree of any vertex in our graph, i.e., all
vertices have d or fewer edges attached, and at least one vertex has precisely d edges attached.
As we go about coloring, when we color any particular vertex v, it is attached to at most d
other vertices, of which some may already be colored. Then there are at most d colors that we
must avoid using. We use the lowest-numbered color not prohibited.
That means that we use some color numbered d + 1 or lower, because at least one of the colors
1, 2, · · · , d + 1 is not prohibited. So we never need to use any color numbered higher than d + 1.
This gives us the following Theorem:

Theorem 4.3 Greedy Coloring Theorem

If d is the largest of the degrees of the vertices in a graph G, then G has a proper coloring with
d + 1 or fewer colors, i.e., the chromatic number of G is at most d + 1.
Proof
The proof to this is discussed already.
This gives an upper bound on the chromatic number, but the real chromatic number may be
below this upper bound. For example, in our course conflict graph above, the highest degree
is d = 6 (vertex L has this degree), so the Greedy Coloring Theorem states that the chromatic
number is no more than 7.
In fact, the chromatic number is 4, and a 4-coloring can be obtained by employing the Greedy
Coloring Algorithm (as we saw above) if one is not too unlucky in picking the order to color
vertices.

66
4.4 lesson 4: Vertex Colouring & Time Tabling 4 UNIT 4: GRAPH THEORY BASICS

4.4.2 Map Colouring

A difficult problem that was addressed by graph theorists is the answer to the following question:
Question: What is the maximum number of colors you need to color a map so that adjacent
territories are given different colors?

67