COUNTING
Counting problems arise throughout mathematics and
computer science.
• We must count the successful outcomes of experiments and all the possible outcomes of
these experiments to determine probabilities of discrete events
• We need to count the number of operations used by an algorithm to study its time
complexity.
• Suppose that a password on a computer system consists of six, seven, or eight characters.
Each of these characters must be a digit or a letter of the alphabet. Each password must
contain at least one digit. How many such passwords are there?
Basic Counting Principles
THE PRODUCT RULE
Suppose that a procedure can be broken down into a sequence of two tasks:
• If there are m ways to do the first task and for each of these ways of doing the
first task, there are n ways to do the second task, then there are mn ways to do
the procedure.
Example 1:A new company with just two employees, Sanchez and Patel,
rents a floor of a building with 12 offices. How many ways are there to
assign different offices to these two employees?
• The procedure of assigning offices to these two employees consists
of assigning an office to Sanchez, which can be done in 12 ways,
then assigning an office to Patel different from the office
assigned to Sanchez, which can be done in 11 ways. By the product
rule, there are
• 12 · 11 = 132 ways to assign offices to these two employees.
Example 2: The chairs of an auditorium are to be labeled with an uppercase
English letter followed by a positive integer not exceeding 100. What is the
largest number of chairs that can be labeled differently?
• The procedure of labeling a chair consists of two tasks, namely,
assigning to the seat one of the 26 uppercase English letters, and then
assigning to it one of the 100 possible integers.
• The product rule shows that there are 26 · 100 = 2600 different ways
that a chair can be labeled.
• Therefore, the largest number of chairs that can be labeled differently
is 2600.
Example 3: There are 32 microcomputers in a computer center. Each microcomputer
has 24 ports. How many different ports to a microcomputer in the center are there?
• The procedure of choosing a port consists of two tasks:
• first picking a microcomputer and then picking a port on this
microcomputer. Because there are 32 ways to choose the microcomputer
• Secondly24 ways to choose the port no matter which microcomputer has
been selected,
• the product rule shows that there are 32 · 24 = 768 ports.
Example 4: How many different bit strings of length seven are there?
• Each of the seven bits can be chosen in two ways, because each bit
is either 0 or 1.
• Therefore, the product rule shows there are a total of 2^7 = 128
different bit strings of length seven.
Example 5:How many different license plates can be made if each plate contains
a sequence of three uppercase English letters followed by three digits (and no
sequences of letters are prohibited, even if they are obscene)?
• There are 26 choices for each of the three uppercase English letters
ten choices for each of the three digits. Hence, by the product rule
there are a total of 26 · 26 · 26 · 10 · 10 · 10 = 17,576,000
possible license plates.
Example 6:How many functions are there from a set with m elements
to a set with n elements?
• A function corresponds to a choice of one of the n elements in the
codomain for each of the m elements in the domain. Hence, by the
product rule there are n · n · · · · · n = n^m functions
• from a set with m elements to one with n elements. For example,
there are 5^3 = 125 different functions from a set with three elements
to a set with five elements.
Example7: How many one-to-one functions are there from a set with
m elements to one with n elements?
• We suppose that |A|=m and |B|=n. Obviously, m<=n. Otherwise, injection from A to B does
not exist.
• If we take the first elementin A, it can be mapped to any element in B. So there are n ways to
map the element. For the next element , there are n−1 possibilities because one element
in B was already mapped to . Continuing this process, we find that the element
has m−n+1 options. Therefore, the number of injective functions is expressed by the formula.
• So total ways we have:
𝑡h𝑒 𝑙𝑜𝑜𝑝 𝑟𝑢𝑛 𝑖𝑛 𝑛1 ×𝑛2 ×𝑛 3 × … ×𝑛𝑚
THE SUM RULE
• If a task can be done either in one of ways or in one of
ways, where none of the set of ways is the same as any of
the set of ways, then there are + ways to do the task.
Example 1: A student can choose a computer project from one of three lists. The three
lists contain 23, 15, and 19 possible projects, respectively. No project is on more than one
list. How many possible projects are there to choose from?
• The student can choose a project by selecting a project from the
first list, the second list, or the third list.
• Because no project is on more than one list, by the sum rule there
are 23 + 15 + 19 = 57 ways to choose a project.
𝑡h𝑒 𝑙𝑜𝑜𝑝 𝑟𝑢𝑛 𝑖𝑛 𝑛1 +𝑛 2+ 𝑛3 +… +𝑛𝑚
Solutions in Class
There are 18 mathematics majors and 325 computer science majors at a college.
a) In how many ways can two representatives be picked so that one is a mathematics major and the
other is a computer science major?
b) In how many ways can one representative be picked who is either a mathematics major or a
computer science major?
An office building contains 27 floors and has 37 offices on each floor. How many offices are in the building?
A multiple-choice test contains 10 questions. There are four possible answers for each question.
a) In how many ways can a student answer the questions on the test if the student answers every question?
b) In how many ways can a student answer the questions on the test if the student can leave answers blank?
There are four major auto routes from Boston to Detroit and six from Detroit to Los Angeles. How many major
auto routes are there from Boston to Los Angeles via Detroit?
A particular brand of shirt comes in 12 colors, has a male version and a female version, and comes in three
sizes for each gender. How many different types of this shirt are made?
