Transcript CSNB143 – Discrete Structure

CMPD133 – DISCRETE
STRUCTURE
CHAPTER 3 – Counting Methods
OBJECTIVES



Student should be able to understand all types of
counting techniques.
Students should be able to identify the three
techniques learned.
Students should be able to use each of the counting
techniques based on different questions and
situations.
Permutation



An order of objectswe count no. of sequence
Theorem 1
If there are two tasks T1 and T2 are to be done in
sequence. If T1 can be done in n1 ways, and for
each of these ways T2 can be done in n2 ways, the
sequence T1T2 can be done in n1n2 ways.
Example 1
T1
T2
2 ways
T1T2
3 ways
T2T1
2 x3 = 6 ways
3x2 = 6 ways
Theorem 2
 If there are k tasks T1, T2, T3, …, Tk are to be done in
sequence. If T1 can be done in n1 ways, and for each of these
ways T2 can be done in n2 ways, and for each of these n1n2
ways, T3 can be done in n3 ways, and so on, then the sequence
T1T2T3…Tk can be done in n1n2n3…nk ways.
 E.x 1: A label identifier, for a computer system consists of
one letter followed by 3 digits. If repetition allowed, how
many distinct label identifier are possible?
 26 x 10 x10 x 10 = 26000 possible identifiers.
 Problem 1: How many different sequences, each of length r,
can be formed using elements from set A if:

a) elements in the sequence may be repeated?

b) all elements in the sequence must be distinct?
Theorem 3
For problem 1 (a):
 Let A be a set with n elements and 1  r  n. Then the
number of sequences of length r that can be formed from
elements of A, allowing repetitions, is
n.n.n.n… = nr
that is n is multiplied r times
 Ex 2: If A = {, , , }, how many words that can be build
with length 3, repetition allowed?
 n = 4, r = 3, then nr = 43 = 64 words
Theorem 4
 A sequence of r elements from n elements of A is always said
as ‘permutation of r elements chosen from n elements of A’,
and written as nPr or P(n, r)
 For problem 1 (b):
 If 1  r  n, then nPr is the number of permutation of n
objects taken r at a time, is
 n(n-1)(n-2)… (n-(r - 1))
 When r = n, that is from n objects, taken r at a time from A,
where r = n, it is a nPn or n factorial, written as n!.
 Ex 3: Choose 3 alphabet from A = {a, b, c}
3P 3
= 3! = 3.2.1 = 6, that are abc, acb, bac, bca, cab, cba.
So, if there are n elements, taken r at a time,
nPr
=
n.(n-1).(n-2)….. (n-(r-1)).(n-r).(n(r+1))…..2.1
(n-r).(n-(r-1))….2.1
=
n.(n-1).(n-2)….. (n-(r-1))
=
n!
(n - r)!
Ex 4: If A = {p, q, r, s}, find the number of permutation for 3
elements.
4.3.2.1
4P 3 =
1
=
4.3.2
=
24
(ex: pqr, pqs, prq, prs, psq, psr, …….)
Ex 5: Choose 3 alphabets from A..Z
=
26.25.24.23 …. 3.2.1
26P3
23.22……3.2.1.
=
26.25.24
Theorem 5
 The number of distinguishable permutations that can be
formed from a collection of n objects where the first object
appears k1 times, the second object appears k2 times, and so
on, is:
n!
k1!k2!…ki!
Ex 6: a) MISSISSIPPI
b) CANADA
a) 11!
= 34650
1!4!4!2!
Exercise :
 A bank password consists of two letter of the English
alphabet followed by two digits. How many different
passwords are there?
 A coin tossed four times and the result of each toss is
recorded. How many different sequences of head and tails are
possible?
Combination
 Order does not matter.we count no. of subset
 Theorem 1
 Let A be a set with |A| = n, and let 1  r  n. Then the
number of combinations of the elements of A, taken r at a
time, written as nCr, is given by
n!
nCr =
r! (n - r)!
Ex 7: If A = {p, q, r, s}, find the number of combination for 3
elements.
=
4.3.2.1
4C 3
3.2.1.1
=
4
(ex: pqr, pqs, prs, qrs)
(pqr, prq, rpq, rqp, all are the same)
Exercise:
Compute each of the following:
 7C 7
b) 7C4
c) 16C5
 Suppose that a valid computer password consists of seven
characters, the first of which is a letter chosen from the set
A, B, C, D, E, F, G and the remaining six characters are
letter chosen from the English alphabet or a digit. How many
different passwords are possible?
Pigeonhole
 Pigeonhole Principle is a principle that ensures that the data
is exist, but there is no information to identify which data or
what data.
Theorem 1
 If there are n pigeon are assigned to m pigeonhole, where m <
n, then at least one pigeonhole contains two or more pigeons.
 Ex 9:
if 8 people were chosen, at least 2 people were
being born in the same day (Monday to Sunday). Show that
by using pigeonhole principle.
 Sol: Because there are 8 people and only 7 days per week, so
Pigeonhole Principle says that, at least two or more people
were being born in the same day.
 Note that Pigeonhole Principle provides an existence proof.
There must be an object or objects with certain
characteristic. In the above example, the characteristic is
having born on the same day of the week. The pigeonhole
principle guarantees that they are at least two people with
this characteristic but gives no information on identifying this
people. Only their existence are guaranteed.
 In order to use pigeonhole principle we must identify pigeons
(object) and pigeonholes (categories of the desired
characteristic) and be able to count the number of pigeons and
the number of pigeonholes.
 Ex 10:
Show that if any five numbers from 1 to 8 are
chosen, two of them will add to 9.

Two numbers that add up to 9 are placed in sets as
follows:
 A1 = {1, 8},A2 = {2, 7}, A3 = {3, 6}, A4 = {4, 5}
 Sol: Each of the 5 numbers chosen must belong to one of
these sets. Since there are only four sets, the pigeonhole
principle tells us that two of the chosen numbers belong to
the same set. These numbers add up to 9.
The Extended Pigeonhole Principle
 If there are m pigeonholes and more than 2m pigeons, three
or more pigeons will have to be assigned to at least one of the
pigeonholes.
 Notation
 If n and m are positive integers, then n/m stands for largest
integer less than equal to the rational number n/m.
 3/2 = 1, 9/4 = 2
6/3 = 2
Theorem 2
 If n pigeons are assigned to m pigeonholes, then one of the
pigeonholes must contain at least

(n-1)/m + 1 pigeons.