

Discrete Mathematics and Combinatorics

Instructor: Solomon Ketema (PhD)

Email :[email protected]
Telegram :0911980245
Chapter 3: Counting Methods
3.1. The Rules of Sum and Product
Combinatorics is the study of arrangements of objects.
The Rule of Sum
 If a first task can be performed in m ways, while a second
task can be performed in n ways, and the two tasks cannot
be performed simultaneously, then performing either task
can be accomplished in any one of
m + n ways.
In general, if , ,…, are k tasks such that no two of these tasks
can be performed at the same time and can be performed in
ways, then any of the k tasks can be performed in

+ +…+ different ways.

Example:
 Suppose there are 29 boys and 21 girls in a class. To select

one class representative how many different ways are

there to perform the task.

Solution:
 There are 29 ways to select a boy and 21 ways to select a

girl. Selecting a boy is never the same as selecting a girl. By

the rule of sum there are 29 + 21= 50 possible ways.
Example:
 Suppose that either an instructor in Software Engineering or a

student in the same department is chosen as a representative to

a university committee. How many different choices are there for
this representative if there are 18 instructors 37 and 350
students.

Solution:
 There are 18 ways to choose an instructor, and there are 350

ways to choose a student. Choosing an instructor is never the

same as choosing a student. By the rule of sum there are

18 + 350 = 368 possible choices.

The Rule of Product
 If a procedure can be broken down into two stages,

and if there are m possible outcomes of the first

stage and if, for each of these outcomes, there are
n possible outcomes for the second stage, then the
total procedure can be carried out in
m ⋅ n ways.
 In general, suppose that a procedure is carried out by

performing the tasks , ,…, in sequence. If task can be done

in ways, regardless of how the previous tasks were done,
then there are

() ()…) ways to carry out the procedure.

Example:
A new company with just two employees, Mesfin and Hirut,
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 assigning an office to Mesfin , which can be done in
12 ways, then assigning an office to Hirut different from the
office assigned to Mesfin , which can be done in 11 ways. By the
product rule, there are 12 · 11 = 132 ways to assign offices to
Example:

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?

Solution:

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:
 How many different license plates can be made if each

plate contains a sequence of three uppercase English

letters followed by three digits (repetition is allowed)?
Solution:
 There are 26 choices for each of the three uppercase

English letters and 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. What is
the answer if repetition is not allowed?
Example:
How many functions are there from a set with m
elements to a set with n elements?

Solution: A function corresponds to a choice of one

of the n elements in the codomain for each of the m
elements of the domain. By the rule of product,
there are n ⋅ n ⋅… ⋅ n = functions.

For example, there are = 125 different functions from

a set with three elements to a set with five elements.
The function represented in the figure is one of the 125
functions
a
1
b
2
c
3
d
e
Permutations
Given a collection of n distinct objects, any (linear)
arrangement of these objects is called a permutation
of the collection. A permutation of size r (0 ≤ r ≤ n) is
any (linear) arrangement of r distinct objects from
the collection of n objects.


 Example:

 In a group of 5 students 3 students are chosen and seated in a row

for a picture. How many such linear arrangements are possible?

1st position 2nd position 3rd position

 Solution

 First, note that the order in which we select students matters. There

are 5 ways to select the first student. Once the first one is selected
we are left with 4 ways to select the second student. After selecting
the first 2 students there are 3 ways to select the third one. By the
rule of product, there are 5 ⋅ 4 ⋅ 3 = 60 ways to select students.
The Number of Permutations

In general, the number P(n, r) of permutations of size r from a

collection of n objects can be found as follows:

We choose r elements out of n and the order matters. There

are n ways to choose the first element, there are n – 1 ways
to choose the second element, there are n – r + 1 ways to
choose element number r. By the rule of product,

P(n, r) = n ⋅ (n - 1) ⋅ (n – 2) ⋅ … ⋅ (n – r + 1).

Definition:

n! = 1 ⋅ 2 ⋅ 3 ⋅ … ⋅ (n – 1) ⋅ n for n≥1 and 0!=1

Therefore the number of permutations is

n! = n ⋅ (n – 1) …⋅ (n – r + 1)(n – r)(n – r – 1) ⋅… ⋅ 2 ⋅1

P(n,r) (

P(n,r) =

For the especial case r=n, we have

P(n,n) =
Example:

How many different strings (sequences) of length 4 can be

formed using the letters of the word FLOWER?

Solution:

As all the six letters in the word are distinct, we have

P(6,4) = ==360 different strings.

Permutations with Repetitions

Theorem
If there are n objects with indistinguishable objects of a

first type, indistinguishable objects of a second type, … ,

and indistinguishable objects of a type r, where, + +…+=n,

then there are (linear) arrangements of the given n

objects. Each arrangement of this type is called a

permutation with repetitions.

Example:
 How many different 4-letter words (not necessarily

meaningful) can be built permuting the letters of the word

COOL?
Solution:
 If all letters were distinct then the answer would be the

number of all permutations of a 4-element set.

However, in the word ‘’COOL’’ we do not distinguish
two O. Therefore using the above theorem the answer
is =12.
Example:
Find the number of permutations of the letters
of the word SUCCESS?
Solution:
=420.
Example:
How many permutations of the letters ABCDEFGH contain the string
ABC?
Solution:
Note that the number of permutations of the letters ABCDEFGH is 8!.
However, if 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.
Since these six objects can occur in any order, there are P(6,6) = 6! =
720 permutations of the letters ABCDEFGH in which ABC occurs as a
block.
Example
In how many different ways can 6 persons can be seated at a
circular table, if arrangements are considered the same
when one can be obtained from the other by rotation?

Solution

Let one of the person be seated anywhere. Then the

remaining 6-1 persons can be seated in (n-1) ways. Thus,
there are 5! = 120 arrangements of 6 persons around the
circular table.
Example

In how many different ways can 6 men and 6 women be

seated in a row

i) if any person may seat next to any other?

ii) If men and women must occupy alternative seats?

Solution

i) If any person seat next to any other, no distinction need to

be made between men and women. Therefore the number
of ways they can be seated is 12 479,001,600.
ii) When men and women occupy alternative seats the six men can
be seated in 6! ways in odd places and the six women can be
seated in 6! ways in even places and corresponding to each
arrangements of the men there is an arrangements of the women.

Therefore the number of ways in which the men occupy the odd
places and the women occupy the even places is

6! 6! =(720)(720)= 518,400.

Similarly, the number of ways in which the women occupy the odd
places and the men occupy the even places is

6! 6! =(720)(720)= 518,400. Accordingly the total number of ways

is 518,400+ 518,400=1, 036,800.
Combination
 If we start with n distinct objects, each selection, or

combination, of r of these objects, with no

reference to order, corresponds to r! permutations
of size r from the n objects. Thus the number of
combinations of size r from a collection of size n
denoted C(n, r) or where 0≤r≤n, satisfies (r!)(C(n,
r))=P(n, r) and
C(n,r) == =.
Example

How many different committees of two students can be formed from a group
of three students?

Solution:

To answer this question, we need only to find the number of subsets with two
elements from the set containing the three students. As is easily seen, there
are three such subsets. Note that the order in which these students are
chosen does not matter.

Example

How many different committees of three students can be formed from a

group of four students?

Solution: Ex!
Example
Find the number of committees of 5 that can be selected from 7 men
and 5 women if the committee is to consist of at least 1 man and at
least 1 woman.
Solution:
From the given 12 persons the number of committees of 5 that can be
formed is C(12, 5).
Among these possible committees, there are C(7,5) committees
consisting of 5 men and C(5,5)=1 committee consisting of 5 women.
Accordingly the number of committees consisting at least one man and
one women is

C(12, 5) C(7,5) 1=0.

Example
 A History examination contains 10 essay questions. How many different

ways a student can answer any seven of ten questions?

Here, there is no concern about order. So the student can answer the
examination in

C(10,7) ==120 ways.

Example
 In the above example, the examination has two parts A and B each

containing five questions. How many different ways a student can answer 3
questions from part A and 4 questions from part B?

Here, 3 questions can be selected from part A in C(5,3)=10 ways. Similarly, the
other 4 from part B can be selected in C(5,4)=5 ways. By the rule of product
the student can answer in C(5,3) C(5,4)=(10) (5)=50 ways.
Example (Ex!)
 A certain examination has three parts A, B and C with 4

questions in part A, 5 questions in part B, and 6 questions

in part C. It is required to answer 7 questions selecting at
least 2 questions from each part. In how many different
ways can a student select his 7 questions for answering?

Example (Ex!)
 Find the number of 5-digit positive integers such that in

each of them every digit is greater than the digit to the

right.
The Binomial Theorem
If x and y are variables and n is a positive integer, then

=+++…++
Note that we can also write
In view of this theorem, the number is the coefficient of
in the expansion of .
The numbers for k=0, 1, 2, …,n are often referred to as
binomial coefficients.
 For the special case n=4, the coefficient of in the

expansion of is the number of ways in which we

can select two x’s from the four x’s, one of which
is available in each factor.
=
1st factor 2nd 3rd 4th factor
When we select two x’s we use two factors leaving
us two other factors from which we can select the
 For example, we can select x from the first two factors
and y from the last two factors or x from the first and
third factors and y from the second and fourth factors.
 Consequently the coefficient of in the expansion of is
=6, which is the number of ways to select two distinct
objects from the collection of four distinct objects.
 Theorem: For any integer n>0,
 i) =
 Ii) =0
Proof: Ex!
Example
1. Find the coefficients of in the expression of
The coefficients of in the expression of is
==21.
2. Find the coefficients of in the expression of
By settinghe coefficients ofin the expression of is .
Ex! 3. Find the coefficients of in the expression of
Ex! 4. Find the coefficients of in the expression of
 The following is the generalization of the

binomial theorem known as the trinomial

theorem.
For positive integers n, t, the coefficient of
)in the expansion of

where each is an integer with 0≤≤n, for all 1≤≤

and =n.
Example
1. Find the coefficients of in the expression of
The coefficients of in the expression of is ==210.
Ex! 2. Find the coefficients of in the expression in
i) ii) )
Ex! 3. Find the coefficients of in the expression of
Hint: Let
Ex! 4. Find the term which contains in the expression
The Pigeonhole Principle
If m pigeons occupy n pigeonholes and m > n, then at
least one pigeonhole has two or more pigeons
roosting in it.

He knows it and chooses a

roommate.
Theorem: (The Pigeonhole Principle)

If more than n objects that are distributed into n

boxes, then some box has at least two objects.
Let A be the set of pigeons, B be the set of holes,

|A| > |B|.

Let f be a function: f maps the set pigeons to the set

holes.
Can f be injection?


Example

Show that in a class of 32 students, at least two of them have

a birthday on the same day of the month.

Solution

The boxes are the days of the month and the objects are the
students. Since any month has at most 31 days, the
Pigeonhole Principle implies that some day of the month is
the birthday of at least two students.
Example
Among any group of 367 (or more) people, there must be
at least two with the same birthday on the same day of
the year, because there are only 366 possible birthdays.

Example
If there is a word with 27 letters, then one of the letter
may appear twice, because there are 26 letter in the
Latin alphabet.
Example

Show that if ten points are inside an equilateral triangle with

side length 1, some pair of them have distance at most 1/3 .

Solution

Divide the triangle into nine smaller equilateral triangles (see

the figure below).
By the Pigeonhole Principle, at least two points are
contained in one of the smaller triangles (including
boundary). Now each smaller triangle has side length 1/3 .
Thus some pair of points have distance at most 1/3 .
Example

At a party attended by n ≥ 2 people, some pairs of people

shake hands. Show that two people shook the same number
of hands.
Solution (Ex!)

Generating Functions

Reading Assignment!