Talha Shahab BCSE-17206

Discrete Mathematics
Chapter No. 6: Counting
 Counting
Combinatorics is the mathematics of counting and arranging objects. Counting of objects with certain
properties (enumeration) is required to solve many different types of problem For example, counting is used
to:
1) Determine number of ordered or unordered arrangement of objects.
2) Generate all the arrangements of a specified kind which is important in computer simulations.
3) Compute probabilities of events.
4) Analyze the chance of winning games, lotteries etc.
5) Determine the complexity of algorithms.

 Basic Counting Principles

The Sum Rule
The Product Rule

 The Sum Rule

If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is the same
as any of the set of n2 ways, then there are n1 + n2 ways to do the task.
“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 1
Suppose there are 7 different optional courses in Computer Science and 3 different optional courses in
Mathematics. Then there are 7 + 3 = 10 choices for a student who wants to take one optional course.

Example 2
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?
The student can choose a project from the first list in 23 ways, from the second list in 15 ways, and from the
third list in 19 ways. Hence, there are 23 + 15 + 19 = 57 projects to choose from.

 The Product Rule

Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first
task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1
n2 ways to do the procedure.
“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 1
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.

1|Page
Example 2
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? The procedure of labeling a chair consists of two
events, namely,
1. Assigning one of the 26 letters: A, B, C, …, Z and
2. 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 3
Suppose that an automobile license plate has three letters followed by three digits. How many different
license plates are possible? 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.

Hence, by the product rule, there is a total of 26 × 26 × 26 × 10 × 10 × 10 = 17,576,000 different license plates
possible.

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

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.

Number of license plates that begin with A and end in 0 are 1 × 26 × 26 × 10 × 10 × 1 = 67600

Example 4
(a) How many bit strings consist of from one through four digits?
(b) How many bit strings consist of from five through eight digits?

Solution
(a) Number of bit strings consisting of 1 digit = 2
Number of bit strings consisting of 2 digits = 2·2 = 22 Number
of bit strings consisting of 3 digits = 2·2·2 = 23
Number of bit strings consisting of 4 digits = 2·2·2·2 = 24
Hence by sum rule, the total number of bit strings consisting of one through four digit is
2+22 +23 +24 = 2 + 4 + 8 + 16 = 30

(b) Number of bit strings of 5 digits = 25

Number of bit strings of 6 digits = 26
Number of bit strings of 7 digits = 27
Number of bit strings of 8 digits = 28
Hence, by sum rule, the total number of bit strings consisting of five through eight digit is
25 + 26 + 27 + 28 = 480

2|Page
 Example 5
How many three-digit integers are divisible by 5?
Solution
Integers that are divisible by 5, end either in 5 or in 0.
CASE-I (Integers that end in 0)
There are nine choices for the left-most digit (the digits 1 through 9) and ten choices for the middle
digit.(the digits 0 through 9) Hence, total number of 3 digit integers that end in 0 is 9 × 10 × 1 = 90

CASE-II (Integer that end in 5)

There are nine choices for the left-most digit and ten choices for the middle digit Hence, total number
of 3 digit integers that end in 5 is 9 × 10 × 1 = 90

Finally, by sum rule, the number of 3 digit integers that are divisible by 5 is 90 + 90 = 180

Example 6
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

 The Pigeonhole Principle

“If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box
containing two or more of the objects.” Example 1
Among any group of 367 people, there must be at least two with the same birthday, because there are only 366
possible birthdays. Example 2
In any set of 27 English words, there must be at least two that begin with the same letter, since there are 26
letters in the English alphabet.

 Permutation
A permutation of a set of distinct objects is an ordered arrangement of these objects. We also are interested in
ordered arrangements of some of the elements of a set. An ordered arrangement of r elements of a set is called
an r-permutation.

3|Page
 Example 1
How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from
100 different people who have entered a contest? Solution
Because it matters which person wins which prize, the number of ways to pick the three prize winners is the
number of ordered selections of three elements from a set of 100 elements, that is, the number of 3-permutations
of a set of 100 elements. Consequently, the answer is P (100, 3) = 100 · 99 · 98 = 970, 200

Example 2
How many permutations of the letters ABCDEFGH contain the string ABC?
Solution
Because the letters ABC must occur as a block, we can find the answer by finding the number of permutations
of six objects, namely, the block ABC and the individual letters D, E, F, G, and H. Because these six objects can
occur in any order, there are 6! = 720 permutations of the letters ABCDEFGH in which ABC occurs as a block.

 Combination
An r-combination of elements of a set is an unordered selection of r elements from the set. Thus, an
rcombination is simply a subset of the set with r elements

 Combinational Proof
A combinatorial proof of an identity is a proof that uses counting arguments to prove that both sides of the
identity count the same objects but in different ways or a proof that is based on showing that there is a bijection
between the sets of objects counted by the two sides of the identity. These two types of proofs are called double
counting proofs and bijective proofs, respectively

Example 1
How many ways are there to select five players from a 10-member tennis team to make a trip to a match at
another school? Solution
The answer is given by the number of 5-combinations of a set with 10 elements. By Theorem 2, the number of
such combinations is

Example 2
How many bit strings of length n contain exactly r 1s?
Solution
The positions of r 1s in a bit string of length n form an r-combination of the set {1, 2, 3, . . . , n}. Hence, there
are C(n, r) bit strings of length n that contain exactly r 1s.

4|Page
Example 1
What is the expansion of (x + y)4?
Solution
From the binomial theorem it follows that

Example 2
What is the coefficient of x12y13 in the expansion of (x + y)25?
Solution
From the binomial theorem it follows that this coefficient is

5|Page