Counting problems are presented along with their detailed solutions and detailed explanations.
Counting Principle
Let us start by introducing the counting principle using an example.
A student has to take one course of physics, one of science and one of mathematics. He may choose one of 3 physics courses (P1, P2, P3), one of 2 science courses (S1, S2) and one of 2 mathematics courses (M1, M2). In how many ways can this student select the 3 courses he has to take?
Let us use a tree diagram that shows all possible choices. The first column on the left shows the 3 possible choices of the physics course: P1, P2 or P3. Then the second column shows the 2 possible choices of the science course and the last column shows the 2 possible choices for the mathematics course. The different ways in which the 3 courses may be selected are:
(P1 S1 M1), (P1 S1 M2), (P1 S2 M1), (P1 S2 M2)
(P2 S1 M1), (P2 S1 M2), (P2 S2 M1), (P2 S2 M2)
(P3 S1 M1), (P3 S1 M2), (P3 S2 M1), (P3 S2 M2)
The total number of choices may be calculated as follows:
Let n1 be the number of choices of the physics course, here n1 = 3. Let n2 be the number of choices of the science course, here n2 = 2. Let n3 be the number of choices of the mathematics course, here n3 = 2. It is clear from the tree diagram above that the total number N of choices may be calculated as follows:
N = n1 × n2 × n3
= 3 × 2 × 2 = 12
Using the above problem, we can generalize and write a formula related to counting as follows:
"If events E1, E2, E3 ... can occur in n1, n2, n3 ... different ways respectively, the number of ways that all events can occur is equal to
n1 × n2 × n3 ..."
Problem 1
To buy a computer system, a customer can choose one of 4 monitors, one of 2 keyboards, one of 4 computers and one of 3 printers. Determine the number of possible systems that a customer can choose from.
Solution to Problem 1
A customer can choose one monitor, one keyboard, one computer and one printer. The diagram below shows each item with the number of choices the customer has.
Using the counting principle used in the introduction above, the number of all possible computer systems that can be bought is given by
N = 4 × 2 × 4 × 3 = 96
Problem 2
In a certain country telephone numbers have 9 digits. The first two digits are the area code (03) and are the same within a given area. The last 7 digits are the local number and cannot begin with 0. How many different telephone numbers are possible within a given area code in this country?
Solution to Problem 2
The diagram below shows the number of choices for each digit. The first digit of the area code is 0, no choice which is in fact one choice only. The second digit of the area code is 1, no choice or one choice only. The first digit of the local code can be any digit except 0, so 9 choices. The 2nd, 3rd, 4th, 5th, 6th and 7 th digits of the local code can be any digit, hence 10 choices each.
Using the counting principle, the total number of possible telephone numbers is given by
A student can select one of 6 different mathematics books, one of 3 different chemistry books and one of 4 different science books. In how many different ways can a student select a book of mathematics, a book of chemistry and a book of science?
Solution to Problem 3
The total number N of different ways that the students can select his 3 books is given by
N = 6 × 3 × 4 = 72
Problem 4
There are 3 different roads from city A to city B and 2 different roads from city B to city C. In how many ways can someone go from city A to city C passing by city B?
Solution to Problem 4
The total number N of different ways that someone can go from city A to city C, passing by city B is
N = 3 × 2 = 6
Problem 5
A man has 3 different suits, 4 different shirts and 5 different pairs of shoes. In how many different ways can this man wear a suit, a shirt and a pair of shoes?
Solution to Problem 5
The total number N of different ways that this man can wear one of his suits, one of his shirts and a pair of his shoes is
N = 3 × 4 × 5 = 60
Problem 6
In a company , ID cards have 5 digit numbers.
a) How many ID cards can be formed if repetition of the digit is allowed?
b) How many ID cards can be formed if repetition of the digit is not allowed?
Solution to Problem 6
a) In the diagram below, any of the 5 digits of the number are to be formed can be any of the 10 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Hence the 10 choices for each digit of the number to be formed since repetition of the digits from 0 to 9 is allowed. When repetition is allowed, the total number N of ID cards is given by the total numbers of 5 digit numbers that can be formed and is given by:
N = 10 × 10 × 10 × 10 × 10 = 100,000
b) In the diagram below, the first digit of the number to be formed can be any of the 10 digits, hence the 10 choices. The second digit can be any of the 10 digits except the digit used in position 1 since no repetition of the digits is allowed, hence the 9 choices. The third digit can be any of the 10 digits except the two already used in positions 1 and 2 since repetition is not allowed, hence the 8 choices and so on.
The number N of ID cards is given by
N = 10 × 9 × 8 × 7 × 6 = 30,240
Problem 7
In a certain country, licence plate numbers have 3 letters followed by 4 digits. How many different licence plate numbers can be formed? (letters and digits may be repeated).
Solution to Problem 7
26 (all letters in the alphabet) choices are possible for each of the 3 letters to be used to form the licence number. 10 choices (0,1,2,3,4,5,6,7,8,9) are possible for each of the 4 digits. The total number of licence numbers is given by
Using the digits 1, 2, 3 and 5, how many 4 digit numbers can be formed if
a) The first digit must be 1 and repetition of the digits is allowed?
b) The first digit must be 1 and repetition of the digits is not allowed?
c) The number must be divisible by 2 and repetition is allowed?
b) The number must be divisible by 2 and repetition is not allowed?
Solution to Problem 8
a) 1 choice for the first digit. 4 choices for the last 3 digits that form the 4 digit number since repetition is allowed. Hence the number N of numbers that we may form is given by
N = 1 × 4 × 4 × 4 = 64
b) 1 choice for the first digit. 3 choices for the second digit of the number to be formed since repetition is not allowed. 2 choices for the third digit of the number to be formed. 1 choice for the fourth digit of the number to be formed. Hence the number N of numbers that we may form is given by
N = 1 × 3 × 2 × 1 = 6
c) For the number to be formed to be divisible by two, the last digit must be 2, hence one choice for this digit. 4 choices for each of the other digits since repetition is allowed. Hence the number N of numbers that we may form is given by
N = 4 × 4 × 4 × 1 = 64
d) For the number to be formed to be divisible by two, the last digit must be 2, hence one choice for this digit. 3 choices for the first digit, 2 choices for the second digit and 1 choice for the third digit that form the number. Hence the number N of numbers that we may form is given by
N = 3 × 2 × 1 × 1 = 6
Problem 9
A coin is tossed three times. What is the total number of all possible outcomes?
Solution to Problem 9
The first time the coin is tossed, 2 different outcomes are possible (heads,tails). The second time the coin is tossed, another 2 different outcomes are possible and the third time the coin is tossed, another 2 different outcomes are possible. Hence the total number of possible outcomes is equal to
N = 2 × 2 × 2 = 8
Problem 10
Two dice are rolled. What is the total number of all possible outcomes?
Solution to Problem 10
Six possible outcomes for the first die (1,2,3,4,5,6) and 6 other possible outcomes for the second die. The total number of different outcomes is
N = 6 × 6 = 36
Problem 11
A coin is tossed and a die is rolled. What is the total number of all possible outcomes?
Solution to Problem 11
Two possible outcomes for the coin (heads,tails) and 6 possible outcomes (1,2,3,4,5,6) for the die. The total number of different outcomes is
