CSM 166

Lecture One

Topic:
The Fundamental Counting
Principles
 Introduction
 Counting means determining the number of different ways of

arranging objects in certain patterns or the number of ways of

carrying out a sequence of tasks.
 Example1.1,
 Suppose we want to count the number of ways of making a bit string of
length two.
 Such a problem is small enough that the possible arrangements can be
counted by brute force.
 We can simply make a list of all the possibilities: 00, 01, 10, 11.

 Therefore having an answer of four (4).

 If the problem were to determine the number of bit strings of length fifty,

the brute force counting becomes an unreasonable alternative.

 In this case, two basic principles can apply to aid in the counting.

 These are the Sum Rule and the Product Rule.

Emmanuel Kpeglo KNUST 4-2
 The Sum Rule
 The sum rule says that if the sets A and B are disjoint, then
A B = A + B
 All sets mentioned will be finite sets, and if A is a set, A will denote the number
of elements in A.

 I other words, if we can do task 1 in a ways and task 2 in b ways, where none of

the set of a ways is the same as any of the set of b ways (the tasks are

independent), then there are a + b ways to do one of the two tasks.

 Example1.2,
 “In how many different ways we can select either a queen or a six from an
ordinary deck of 52 cards?”
 That task of selecting queen can be done in 4 ways. The 2nd task of selecting a
six can be done in 4 ways. These 2 tasks are independent, hence there are 4 + 4 =
8 ways of selecting one card from a deck, and having that card to be either a
queen or a six.
 Compare this question… “In how many ways can we select either a queen
or a diamond from a deck of 52 cards?” Not 4 + 13 = 17,why?
Emmanuel Kpeglo KNUST 4-3
 Extended sum rule
 If A1 , A2 , A3 ,  , An is a collection of pairwise disjoint sets, then
A1  A2  A3    An = A1 + A2 + A3 +  + An

 Example 1.3,
 How many ordered pairs of integers (x, y) are there such that 0 < xy ≤ 5 ?
 { }
Solution: Let E k = ( x, y ) ∈ Ζ 2 : xy = k for k = 1, ,5. Then the desired number is
E1 + E 2 + E3 + E 4 + E5 .
We can compute each of these as follows :
E1 = {(− 1,−1), (− 1, 1), (1,−1), (1, 1)}
E 2 = {(− 2,−1), (− 2, 1)(− 1,−2), (− 1, 2), (1,−2), (1, 2), (2,−1), (2, 1)}
E3 = {(− 3,−1), (− 3, 1)(− 1,−3), (− 1, 3), (1,−3), (1, 3), (3,−1), (3, 1)}
E 4 = {(− 4,−1), (− 4, 1)(− 2,−2), (− 2, 2), (− 1,−4 ), (− 1, 4 ), (1,−4 ), (1, 4 ), (2,−2 ), (2, 2 ), (4,−1), (4, 1)}
E5 = {(− 5,−1), (− 5, 1)(− 1,−5), (− 1, 5), (1,−5), (1, 5), (5,−1), (5, 1)}
The desired number is therefore 4 + 8 + 8 + 12 + 8 = 40.

Emmanuel Kpeglo KNUST 4-4

 The Product Rule
 The product rule says: A × B = A ⋅ B
 An explanation of this is that A × B consists of all ordered pairs (a, b) where a ∈ A
and b ∈ B. There are A choices for a and then B choices for b.

 Generally, let A1 , A2 , A3 ,  , An , be finite sets. Then

A1 × A2 × A3 ×  × An = A1 ⋅ A2 ⋅ A3 ⋅  ⋅ An

 If you need to accomplish some task that takes n steps, and there are a1 ways
of accomplishing the first step, a2 ways of accomplishing the second step, etc.,
and an ways of accomplishing the n th step, then there are a1 ⋅ a 2 ⋅  ⋅ a n ways of
accomplishing the task.

Emmanuel Kpeglo KNUST 4-5

 The Product Rule
 Example 1.5
 Suppose we are buying a car with five choices for the exterior color and three
choices for the interior color.
 There is a total of 3(5) = 15 possible color combinations that we can choose from.
 First task, select an exterior color. There are 5 ways to do that.
 Second task, select an interior color. There are 3 ways to do that.
 So the product rule says there are 15 ways total to do both tasks.
 Note:
 there is no requirement of independence of tasks when using the product rule.
 the number of ways of doing the second task must be the same no matter what choice is made for
doing the first task.
 Example 1.6
 How many different 2-digit numbers could we form using the digits 1, 2, 3, 4, 5, 6,
7, 8, and 9?
 Task 1, fill in the left digit, There are 9 ways to do the first task. and
 Task 2, fill in the right digit. No matter how we do the first task, there are 9 ways
to do the second task as well.
 By the product rule, there are 9(9) = 81 possible such two-digit numbers.
 COMPARE: Suppose we wanted 2-digit numbers made up of those same nine digits,
but we do not want to use a digit more than once in any of the numbers.
Emmanuel Kpeglo KNUST 4-6
 Using both the sum and product rules
 Example 1.7

Suppose we wanted to count the number of different possible bit

strings of length five that start with either three 0’s or with two 1’s.
In how many ways can we do that?

 Solution:

 There are 1 x 1 x 1 x 2 x 2 = 4 bit strings of length five starting with three 0’s.

 Using the same reasoning, there are 1 x 1 x 2 x 2 x 2 = 8 bit strings of length five

starting with two 1’s.

 A bit string cannot both start with three 0’s and also with two 1’s, (in other words,

starting with three 0’s and starting with two 1’s are independent).

 Hence, 4 + 8 = 12 bit strings of length five starting with either three 0’s or two 1’s.

Emmanuel Kpeglo KNUST 4-7

 Using both the sum and product rules
 Example 1.8

Count the number of strings on license plates which either consist

of three capital English letters, followed by three digits, or consist of
two digits followed by four capital English letters.

 Solution:

 Let A be the set of strings which consist of three capital English letters followed

by three digits, and

 B be the set of strings which consist of two digits followed by four capital

English letters.

 By the product rule A = 26 3 ⋅ 10 3 and B = 10 2 ⋅ 26 4

 Since A  B = φ , by the sum rule the answer is A  B = 263 ⋅103 + 10 2 + 26 4 = 63,273,600

Emmanuel Kpeglo KNUST 4-8

 Using both the sum and product rules
 Example 1.9
 Each user on a computer system has a password, which is six to eight
characters long, where each character is an uppercase letter or a digit. Each
password must contain at least one digit. How many possible passwords are
there?

 Solution:
 Let P be the total number of possible passwords, and let P6, P7, and P8 denote the number of
possible passwords of length 6, 7, and 8, respectively. By the sum rule, P = P6 + P7 + P8.
 To find P6 it is easier to find the number of strings of uppercase letters and digits that are six
characters long, including those with no digits, and subtract from this the number of strings
with no digits.
6
 By the product rule, the number of strings of six characters is 36 , and the number of strings
with no digits is 26 6 .
366 − 26 = 1,867,866,560.
6
 Hence, P6 =
Similarly, we have
P7 = 36 7 − 26 7 = 70,332,353,920 and
P8 = 368 − 268 = 2,612,282,842,880.
Consequently,
P = P6 + P7 + P8 = 2,684,483,063,360.

Emmanuel Kpeglo KNUST 4-9

 The Subtraction Rule and The Division Rule
 The Subtraction Rule
If a task can be done in either a1 ways or a2 ways, then the number
of ways to do the task is a1 + a2 minus the number of ways to do the
task that are common to the two different ways. Thus

A B = A + B − A B

 The Division Rule

There are n/d ways to do a task if it can be done using a procedure
that can be carried out in n ways, and for every way w, exactly d of
the n ways correspond to way w.
Emmanuel Kpeglo KNUST 4-10
 The Subtraction Rule and The Division Rule
 Example 1.11
A computer company receives 350 applications from college graduates for a job
planning a line of new web servers. Suppose that 220 of these applicants majored in
computer science, 147 majored in business, and 51 majored both in computer
science and in business. How many of these applicants majored neither in computer
science nor in business?

 Solution:
 Finding the number of applicants who majored neither in computer science nor in business, subtract the
number of students who majored either in computer science or in business (or both) from the total number
of applicants.

 Let A be the set of students who majored in computer science and B the set of students who majored in
business. Then A ∪ B is the set of students who majored in computer science or business (or both), and

A ∩ B is the set of students who majored both in computer science and in business. By the subtraction rule
the number of students who majored either in computer science or in business (or both) equals

|A ∪ B| = |A| + |B| − |A ∩ B| = 220 + 147 − 51 = 316.

 We conclude that 350 − 316 = 34 of the applicants majored neither in computer science nor in business.

Emmanuel Kpeglo KNUST 4-11

 The Subtraction Rule and The Division Rule

 Example 1.12
How many different ways are there to seat four people around a circular table, where
two seatings are considered the same when each person has the same left neighbor
or the same right neighbor?

 Solution:
 We arbitrarily select a seat at the table and label it seat 1.

 We number the rest of the seats in numerical order, proceeding clockwise around the table.

 Note that are four ways to select the person for seat 1, three ways to select the person for
seat 2, two ways to select the person for seat 3, and one way to select the person for seat 4.
Thus, there are 4! = 24 ways to order the given four people for these seats.

 However, each of the four choices for seat 1 leads to the same arrangement, as we
distinguish two arrangements only when one of the people has a different immediate left or
immediate right neighbor. Because there are four ways to choose the person for seat 1, by
the division rule there are 24 ∕4 = 6 different seating arrangements of four people around the
circular table.
Emmanuel Kpeglo KNUST 4-12
 The Pigeonhole Principle
 If there are more items than containers, then at least one container

must contain more than one item.

 For example, if a mother has three children, at least two of them have the same

sex.
 Theorem 1.1 (The Generalized Pigeonhole Principle).
If n objects are placed into k boxes, then there is at least one box
that contains at least ⌈n/k⌉ objects.
 Proof: We will use a proof by contraposition. Assume not. Then each of the k

boxes contains no more than ⌈n/k⌉−1 objects. Notice that ⌈n/k⌉ < n/k + 1 (convince
yourself that this is always true). Thus, the total number of objects in the k boxes
is at most k (⌈n/k⌉ − 1) < k(n/k + 1 − 1) = n,

contradicting the fact that there are n objects in the boxes.

Therefore, some box contains at least ⌈n/k⌉ objects.

Emmanuel Kpeglo KNUST 4-13
 The Pigeonhole Principle
 Remark

 A common type of problem asks for the minimum number of

objects such that at least r of these objects must be in one of k

boxes when these objects are distributed among the boxes.

 When we have n objects, the generalized pigeonhole principle

tells us there must be at least r objects in one of the boxes as

long as ⌈n/k⌉ ≥ r.

 The smallest integer n with n/k > r − 1, namely, n = k(r − 1) + 1,

is the smallest integer satisfying the inequality ⌈n/k⌉ ≥ r.

Emmanuel Kpeglo KNUST 4-14

 The Pigeonhole Principle
 Example 1.13

 What is the minimum number of students required in a discrete mathematics

class to be sure that at least six will receive the same grade, if there are five
possible grades, A, B, C, D, and F?

 Solution:
 Remember n = k(r − 1) + 1, is the smallest integer satisfying the inequality ⌈n/k⌉ ≥ r.

 The minimum number of students needed to ensure that at least six students

receive the same grade is the smallest integer n such that ⌈n/5⌉ = 6. The smallest
such integer is n = 5 ⋅ 5 + 1 = 26.

 If you have only 25 students, it is possible for there to be five who have received

each grade so that no six students have received the same grade.

 Thus, 26 is the minimum number of students needed to ensure that at least six

students will receive the same grade.

Emmanuel Kpeglo KNUST 4-15
 The Pigeonhole Principle
 Example1.14

 A drawer contains an infinite supply of white, black, and blue

socks. What is the smallest number of socks you must take from
the drawer in order to be guaranteed that you have a matching
pair?
 Solution:

 Clearly I could grab one of each color, so three is not enough.

But according the Pigeonhole Principle, if I take 4 socks, then I

will get at least ⌈n/3⌉ ≥ 2 of the same color (the colors correspond
to the boxes). Thus n = k(r − 1) + 1 = 3 ⋅ 1 + 1 = 4

 So 4 socks will guarantee a matched pair.

Emmanuel Kpeglo KNUST 4-16
 The Pigeonhole Principle
 Example1.15
 How many cards must be selected from a standard deck of 52 cards to
guarantee that at least three cards of the same suit are selected?
 Solution:
 Using the generalized pigeonhole principle, we see that if n cards are
selected, there is at least one box containing at least ⌈n/4⌉ cards.
 Consequently, we know that at least three cards of one suit are selected
if ⌈n/4⌉ ≥ 3.
 The smallest integer n such that ⌈n/4⌉ ≥ 3 is n = 2 ⋅ 4 + 1 = 9, so nine
cards suffice.
 Note that
 if eight cards are selected, it is possible to have two cards of each suit, so more
than eight cards are needed.
 Consequently, nine cards must be selected to guarantee that at least three cards
of one suit are chosen.
 One good way to think about this is to note that after the eighth card is chosen,
there is no way to avoid having a third card of some suit.
Emmanuel Kpeglo KNUST 4-17
 The Pigeonhole Principle
 Example1.16

 How many must be selected from a standard deck of 52 cards to

guarantee that at least three hearts are selected?

 Solution:

 We do not use the generalized pigeonhole principle to answer this

question, because we want to make sure that there are three hearts, not
just three cards of one suit.

 Note that in the worst case, we can select all the clubs, diamonds, and

spades, 39 cards in all, before we select a single heart.

 The next three cards will be all hearts, so we may need to select 42

cards to get three

Emmanuel Kpeglo KNUST 4-18

 Exercise 1
1. To meet the science requirement a student must take one of the following
courses: a choice of 5 biology courses, 4 physics courses, or 6 chemistry
courses. In how many ways can the one course be selected?

2. A multiple choice test contains 10 questions. There are four possible answers for
each question.
(a) How many ways can a student complete the test if every question must be
answered?
(b) How many ways can a student complete the test if questions can be left
unanswered?

3. How many license plates can be made using either three digits followed by three
uppercase English letters or three uppercase English letters followed by three
digits?

4. In how many ways can a photographer at a wedding arrange 6 people in a row

from a group of 10 people, where the bride and the groom are among these 10
people, if
(a) the bride must be in the picture?
(b) both the bride and groom must be in the picture?
(c) exactly one of the bride and the groom is in the picture?
Emmanuel Kpeglo-KNUST 4-19
 Exercise 1
5. Every student in a discrete mathematics class is either a computer science or a
mathematics major or is a joint major in these two subjects. How many students
are in the class if there are 38 computer science majors (including joint majors),
23 mathematics majors (including joint majors), and 7 joint majors?

6. A bowl contains 10 red balls and 10 blue balls. A woman selects balls at random
without looking at them.

(a) How many balls must she select to be sure of having at least three balls of the
same color?

(b) How many balls must she

7. There are six professors teaching the introductory discrete mathematics class at a
university. The same final exam is given by all six professors. If the lowest
possible score on the final is 0 and the highest possible score is 100, how many
students must there be to guarantee that there are two students with the same
professor who earned the same final examination score?
Emmanuel Kpeglo-KNUST 4-20