CC 141

Discrete Structures
Department of Computer Science
School of Systems and Technology

University of Management and Technology

Lahore, Pakistan
Section 6.1

Counting
 Combinatorics
Combinatorics is the mathematics of counting and arranging objects.
In combinatorics we generally solved counting problems. Following
are few examples of counting related problems:
How many courses have you taken in current semester?
If a course can consist of three or four credits hours, what is the maximum
credit hours one can clear by passing ten courses.
If Ali has invited five of his friends on his birthday and every guest shakes
hands with every other guest and the host, how many shake hands will take
place?
If we have a bit string consisting of ten bits, how many different ways the
string can be formed with last bit as ‘1’?
Counting problems can be both easy and hard depending upon
different factors.
In counting problem the important step is to realize which
constraints are applied while we are counting, keep that in control
will enable you to solve the actual problem easily.
 BASIC COUNTING PRINCIPLES
The two basic counting principles are:

• Product Rule
• Sum Rule

They can be used to solve many different counting problems.

 EXAMPLE
If a supervisor has two workers each of which can work on
the task and complete it.

How many different ways are available to finish the task?

Solution:
There are two ways to finish the task one through first
worker and the second through the other worker.
 EXAMPLE
• Your institute is offering 7 courses in computer science and 3 courses
in mathematics. You are asked to choose only one course.
• How many choices you have?

• You can select either one computer science course or mathematics.

7 cs courses = 7 choices
3 math courses = 3 choices
Total number of choices = 7 + 3 (basically by applying sum rule)
 THE SUM RULE
• If one event can occur in n1 ways.
• A second event can occur in n2 (different) ways.

Then the total number of ways in which exactly one of the

events (i.e., first or second) can occur is

n1 + n2.
 EXAMPLE
A student can choose a computer project from one of the three lists.
The three lists contain 23, 15 and 19 possible projects, respectively.
• How many possible projects are there to choose from?
SOLUTION:
23 choices are in first list,
15 choices are in second list,
19 choices are in third list. Hence, there are
So, we have total number of choices
= 23 + 15 + 19 = 57 projects to choose from.
 GENERALIZED SUM RULE
If one event can occur in n1 ways,
a second event can occur in n2 ways,
a third event can occur in n3 ways,
……………………………………..
then there are
n1 + n2 + n3 + …

ways in which exactly one of the events can occur.

Practice Questions … Do it by Yourself
• A worker can go to his work place either by train or
by bus. There are three different trains and four
different busses that can take him to his office in
time. How many different ways are available for
him to go to the office?
• Stark Inc. hires a new employee. They have five
vacant cabins on ground floor and three vacant
offices on second floor. How many different ways
are available for office management to assign one
office / cabin for him?
 SUM RULE FOR DISJOINT SETS
• If A1, A2, …, Am are finite disjoint sets, then the number of
elements in the union of these sets is the sum of the number of
elements in them.

• If n(Ai) denotes the number of elements in set Ai, then

n(A1A2 … Am) = n(A1) + n(A2) + … + n(Am)

where
AiAj =  if i  j
 SUM RULE FOR OVERLAPPING SETS

union of these sets is the sum of the number of elements in them minus
• If A1 and A2 are not disjoint sets, then the number of elements in the

the number of ways to do the task that are common to these

sets.

• If n(Ai) denotes the number of elements in set Ai, then

n(A1A2) = n(A1) + n(A2) - n(A1  A2)

To avoid recounting of overlapping values, we use this

principle of inclusion-exclusion.
EXAMPLE … Principle of Inclusion – Exclusion

If A = {a, e, i, o, u} and B={a, b, c, d, e} then |A

 B| = ?
AB=?
Solution:
A = {a, e, i, o, u} |A| = 5
B={a, b, c, d, e}  |B| = 5
A  B = {a, e}  |A  B| = 2

|A  B| = |A| + |B| - |A  B| = 5 + 5 – 2 = 8
EXAMPLE … Principle of Inclusion – Exclusion
How many positive integers not bigger than 20 are divisible by
either 2 or 3?
Solution:
Set of all positive integers not greater than 20 = A = {1, 2, 3,
…, 20}
Numbers divisible by 2 = B = {2, 4, 6, …, 20}
Numbers divisible by 3 = C = {3, 6, 9, …, 18}
Numbers divisible by both 2 and 3 = B  C = {6, 12, 18}
Required Elements = R = |B∪C| = ?
| B∪C| = |B| + |C| - |B  C|
Total numbers = 10+6 -3 = 13
Practice Questions … Do it Yourself
How many bit-strings of length eight either begin with 00 or
end with 101?
How many positive integers up to 1000 are divisible by 7 or
11?
How many positive integers under 500 are not divisible by
either of the numbers 2, 3, 5?
There are a total of 40 students in a class. 18 of the students
have Babar Azam’s pictures, 16 of the students have Shadab
Khan’s pictures and 12 of them have Emad Wasim’s pictures.
7 of them have both Babar Azam and Shadab Khan’s pictures.
5 of them have Babar Azam and Emad Wasim’s pictures. 3 of
them have both Shadab Khan and Emad Wasim’s pictures. 2 of
the students have all three players’ pictures. How many of the
students have no pictures of these players at all.
 EXAMPLE
Suppose
There are 7 different optional courses in Computer Science and
3 different optional courses in Mathematics.

A student who wants to take one optional course of each subject,

there are:

7  3 = 21 choices.
 THE PRODUCT RULE
• If one event can occur in n1 ways and if for each of these n1
ways, a second event can occur in n2 ways.

• Then the total number of ways in which both events occur is

n1· n2
 EXAMPLE
• The chairs of an auditorium are to be labeled with two characters, a letter
followed by a digit.
What is the largest number of chairs that can be labeled differently?
SOLUTION:
The procedure of labeling a chair consists of two events, namely,
Assigning one of the 26 letters: A, B, C, …, Z and
Assigning one of the 10 digits: 0, 1, 2, …, 9

By product rule, there are 26  10 = 260 different ways that a chair can be
labeled by both a letter and a digit.
 EXAMPLE
A new company with just two employees, Ahmed and Saeed, rents a floor of a
building with 12 offices.
How many ways are there to assign different offices to these two employees?
SOLUTION:
The procedure of assigning offices to these two employees consists of two events,
namely,
Assigning an office to Ahmed: 12 ways
Assigning an office to Saeed different from the office assigned to Ahmed: 11 ways

By product rule, there are 12  11 = 132 different ways to assign offices to these
two employees.
 GENERALIZED PRODUCT RULE
• If some event can occur in n1 different ways, and if, following
this event, a second event can occur in n2 different ways, and
following this second event, a third event can occur in n3
different ways, …, then the number of ways all the events can
occur in the order indicated is

n1· n2· n3· …

 PRODUCT RULE IN TERMS OF SETS
• If A1, A2, …, Am are finite sets, then the number of elements in
the Cartesian product of these sets is the product of the
number of elements in each set.

• If n(Ai) denotes the number of elements in set Ai, then

n(A1  A2 … Am) = n(A1)· n(A2)· …· n(Am)

 EXERCISE
• Find the number n of ways that an organization consisting of 15
members can elect a president, treasurer, and secretary. (assuming
no person is elected to more than one position)

SOLUTION:
The president can be elected in 15 different ways;
The treasurer can be elected in 14 different ways;
The secretary can be elected in 13 different ways.
Thus, by product rule, there are
n = 15 x 14 x 13 = 2730
different ways in which the organization can elect the officers.
 EXERCISE
• There are four bus lines between A and B; and three bus lines
between B and C.
• Find the number of ways a person can travel:

(a) By bus from A to C by way of B;

(b) Round trip by bus from A to C by way of B;
(c) Round trip by bus from A to C by way of B, if the person does
not want to use a bus line more than once.
 SOLUTION
(a) There are 4 ways to go from A to B and 3 ways to go from B to C;
hence there are
4 x 3 = 12 ways to go from A to C by way of B.

(b) The person will travel from A to B to C to B to A for the round trip.
i.e (A →B →C →B →A)

The person can travel 4 ways from A to B and 3 way from B to C and back.
i.e., 4 3 3 4
A B  C  B  A

Thus there are 4 x 3 x 3 x 4 = 144 ways to travel the round trip.

(c) The person can travel 4 ways from A to B and 3 ways from B
to C, but only 2 ways from C to B and 3 ways from B to A,

Since bus line cannot be used more than once. Thus

4 3 2 3
i.e.,
A B  C  B  A
Hence there are 4 x 3 x 2 x 3 = 72 ways to travel the round trip
without using a bus line more than once.
 EXERCISE
• How many bit strings of length 8

(i) begin with a “1”?

(ii) begin and end with a “1”?
 SOLUTION
(i) If the first bit (left most bit) is a 1, then it can be filled in only one way.
Each of the remaining seven positions in the bit string can be filled in 2 ways
(i.e., either by 0 or 1).
Hence,
there are 1 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 27 = 128 different bit strings of
length 8 that begin with a 1.

(ii) If the first and last bit in an 8 bit string is a 1, then only the intermediate six
bits can be filled in 2 ways, i.e. by a 0 or 1.
Hence there are 1 x 2 x 2 x 2 x 2 x 2 x 2 x 1 = 26 = 64
different bit strings of length 8 that begin and end with a 1.
 EXERCISE
Suppose that an automobile license plate has three letters followed by three
digits.
a) How many different license plates are possible?
SOLUTION:
Each of the three letters can be written in 26 different ways, and each of the
three digits can be written in 10 different ways.
letters digits

26 ways each 10 ways each

Hence, by the product rule, there is a total of

26 x 26 x 26 x 10 x 10 x 10 = 17,576,000
different license plates possible.
(b) How many different license plates are possible (repetition is not allowed)?
SOLUTION:
The first place can be filled in 26 ways
The second place can be filled in 25 ways
The third place can be filled in 24 ways
The fourth place can be filled in 10 ways
The fifth place can be filled in 9 ways
The sixth place can be filled
letters in 8 waysdigits

26 ways 25 ways 24 ways 10 ways 9 ways 8 ways

Number of license plates with no letter and digit repetition are

(b) How many license plates could begin with A and end on 0?

SOLUTION:
The first and last place can be filled in one way only, while each of second
and third place can be filled in 26 ways and each of fourth and fifth place
can be filled in 10 ways.
letters digits

A 0

one way 26 ways each 10 ways each one way

Number of license plates that begin with A and end in 0 are

1 x 26 x 26 x 10 x 10 x 1 = 67600
(c) How many license plates do not contain any vowel?

SOLUTION:
Alphabets contain 5 Vowels (a, e, i, o, u).
So by excluding the vowels, the remaining letters can be filled in 21 ways
and each digit can be filled in 10 ways.
letters digits

21 ways each 10 ways each

Number of license plates that does not contain any vowel are
21 x 21 x 21 x 10 x 10 x 10 = 9,261,000
(d) How many license plates do not end on even digit?

SOLUTION:
Each of the three letters can be written in 26 different ways,
and each of fourth and fifth place can be filled in 10 ways
while sixth place can be filled in 5 ways (as from 0-9 , 5 digits are even)
letters digits

26 ways each 10 ways each 5 ways

Number of license plates that do not end on even digit are

26 x 26 x 26 x 10 x 10 x 5 = 8,788,000
 EXERCISE
A variable name in a programming language must be either a letter or a letter
followed by a digit.
How many different variable names are possible?
SOLUTION:
• First consider variable names one character in length.
• Since such names consist of a single letter, there are 26 variable names of length 1.
• Next, consider variable names two characters in length.
Since the first character is a letter, there are 26 ways to choose it. The second
character is a digit, there are 10 ways to choose it.
Hence, to construct variable name of two characters in length, there are 26 x10 =
260 ways.
• Finally, by sum rule, there are 26 + 260 = 286 possible variable names in the
programming language.
 EXERCISE
A computer access code word consists of from one to three letters of
English alphabets with repetitions allowed.
How many different code words are possible.
SOLUTION:
Number of code words of length 1 = 261
Number of code words of length 2 = 262
Number of code words of length 3 = 263

Hence, the total number of code words

= 261 + 262 + 263
= 18,278
 Excercise… Do it Yourself
Alice invites her friends Bob, Carl, Dian, Eve, Fred and
George on her birthday party. Every participant is
supposed to shake every other participant’s hand.
How many handshakes?
 Excercise… Do it Yourself
Let X denote a digit that can take any of the values 0 through 9, let N denote a digit
that can take any of the values 2 through 9, and let Y denote a digit that must be a
0 or a 1.
In the old plan, the formats of the area code, office code, and station code are NYX,
NNX, and XXXX, respectively, so that telephone numbers had the form NYX-NNX-
XXXX.
In the new plan, the formats of these codes are NXX, NXX, and XXXX, respectively,
so that telephone numbers have the form NXX-NXX-XXXX.
1. How many different North American telephone numbers are possible under
the old plan and under the new plan?
2. In total how many telephone numbers are possible under the old plan and the
new plan
 Excercise… Do it Yourself
Counting Internet Addresses In the Internet, which is made up of interconnected physical networks of
computers, each computer (or more precisely, each network connection of a computer) is assigned an Internet
address. In Version 4 of the Internet Protocol (IPv4), now in use, an address is a string of 32 bits. It begins with
a network number (netid ). The netid is followed by a host number (hostid ), which identifies a computer as a
member of a particular network. Three forms of addresses are used, with different numbers of bits used for
netids and hostids. Class A addresses, used for the largest networks, consist of 0, followed by a 7-bit netid
and a 24-bit hostid. Class B addresses, used for medium-sized networks, consist of 10, followed by a 14-bit
netid and a 16-bit hostid. Class C addresses, used for the smallest networks, consist of 110, followed by a 21-
bit netid and an 8-bit hostid. There are several restrictions on addresses because of special uses: 1111111 is
not available as the netid of a Class A network, and the hostids consisting of all 0s and all 1s are not available
for use in any network. A computer on the Internet has either a Class A, a Class B, or a Class C address.
(Besides Class A, B, and C addresses, there are also Class D addresses, reserved for use in multicasting when
multiple computers are addressed at a single time, consisting of 1110 followed by 28 bits, and Class E
addresses, reserved for future use, consisting of 11110 followed by 27 bits. Neither Class D nor Class E
addresses are assigned as the IPv4 address of a computer on the Internet.)
The lack of available IPv4 address has become a crisis!
Next Page
 Excercise… Do it Yourself… Continued..
Figure 1 illustrates IPv4 addressing. (Limitations on the number of Class A and Class B netids have
made IPv4 addressing inadequate; IPv6, a new version of IP, uses 128-bit addresses to solve this
problem.)
How many different IPv4 addresses are available for computers on the Internet?
 Practice Questions … Do it Yourself
Bit String Problems
How many unique bit-strings of length 2 are possible?
How many unique bit-strings of length 5 are possible?
How many unique bit-strings of length 10 are possible?
How many unique bit-strings of length N are possible?
How many unique bit-strings of length 10 that start with 00 are possible?
How many unique bit-strings of length 10 that end on 111 are possible?
How many unique bit-strings of length 10 are possible that start on 00
and end on 11?
How many unique bit-strings of length 10 must contain substring 111?
How many unique bit-strings of length 10 do not contain substring 111?
 Practice Questions … Do it Yourself
Password Problems
Each user on a computer system has a password, which is six
characters long. Each character in the password is an uppercase
letter or a digit. How many unique passwords are possible?

Each user on a computer system has a password, which is six

characters long, where each character is an uppercase letter or a
digit. Each password must contain at least one digit. How many
unique passwords are possible?
 Summary
The topics we covered:
• Combinatorics
• Basic Counting Principles
• Sum Rule
• Product Rule
• Practice Questions