English-based-Course-Counting_Problems.ppt

English based Course Counting Problems (ppt)

1. COUNTING PROBLEMS

2. A counting problem: “how many ways”
some events can occur.
Example 1: How many ways to form codes with three-letters using
letters a, b, c, and d such that no letter can be repeated?
Solution:
Note: Does the order matter?
One way to solve, by giving list all possibilities: abc, acb, bac, bca,
cab, cba.
Another way: by using product rule.

3. Fundamental Counting Principle:
Product Rule
Suppose that a certain procedure P can be
broken into n successive ordered steps, i.e.,
S
1
and S
2,
and
. . .
S
n,
and suppose that
S
1
can occur in

r
1
ways.
S
2
can occur in

r
2
ways.
S
n can occur in
r
n ways.
Then the number of ways that P can occur is
n
rrr 
21

4. Fundamental Counting Principle:
Addition Rule
Suppose that a certain procedure P can be
broken into n steps: S
1
, or S
2….
or
, . . .
S
n,
and
suppose
S
1
can occur in

r
1
ways.
S
2
can occur in

r
2
ways.
S
n can occur in
r
n ways.
Then the number of ways P can occur is
1 2 n
r r r 

5. Example 1: How many ways to form codes with three-letters
using letters a, b, c, and d such that no letter can be repeated?
By using product rule:
S
1
: a code with the first letter a. This step can occur in

2

ways.
S
2
: a code with the first letter b. This step can occur in

2

ways.
S
3
: a code with the first letter c. This step can occur in

2

ways.
Then the number of ways that P can occur is 2.2.2=6 ways
Example

6. Example2: How many committees of three people can be
selected from four people?
Use P, Q, R, and S to represent the people.
The order of people does not matter
S
1
: a committee with the person PQR. This step can occur in

1

way.
S
2
: a committee with the person PQS. This step can occur in

1

way.
S
3 : a committee with the person PRS. This step can occur in
1
way.
S
4 : a committee with the person QRS. This step can occur in
1
way.
Then the number of ways that P can occur is 1+1+1+1=4 ways
Example

7. Calculate the value k through the following procedure
k:=0.
For T1=1 to n1 do
k:=k+1.
end
For T2=1 to n2 do
k:=k+1.
end………………..
For Tm=1 to n
m do
k:=k+1.
end
By using addition rule, k = n1+n2+n3+…+ n
m
Example

8. Example

9. Calculate the value k through the following procedur
k:=0.
For T1=1 to n1 do
For T2=1 to n2 do
For T3=1 to n3 do
k:=k+1.
end
end
end
Example
By using product rule, k = n1.n2.n3… n
m

10. Example

11. Let A={a,b,c,d,e} and B={1,2,3}.
How many ways to determine of elements of
A x B?
Example
Solution: the pairs of elements A x B:
S
1
: The first position is an element of A: (x,y) where xA.
This can be done in 5 ways.
S
2 : The first position is an element of B: (x,y) where xB.
This can be done in 3 ways.
Thus, the number of elements A x B is 5.3=15 elements

12. Permutations
An r-permutation of a set of n elements is an
ordered selection of r elements from the set of
n elements

!
!
n r
n
P
n r


Order must be
considered

13. Example 1:How many three-letter codes are there
using letters A, B, C, and D if no letter can be
repeated?
Note: The order does matter
4 3
4!
24
1!
P 

14. Combinations
The number of combinations of n
elements taken r at a time is

!
! !
n r
n
C
r n r


Where n & r are nonnegative integers & r < n
Order does
NOT matter

15. Example 3: How many committees of three can be
selected from four people?
Use A, B, C, and D to represent the people
Note: Does the order matter?
4
!1!3
!4
34 C

16. Example 3: How many ways can the 4 call
letters of a radio station be arranged if the
first letter must be W or K and no letters
repeat?
2252423 27,600   Solution =

17. Example 4: Given the digits 5, 3, 6, 7, 8, and
9, how many 3-digit numbers can be made if
the first digit must be a prime number? (can
digits be repeated?)
Solution =354 60

18. Example 5: Suppose there are 15 girls and 18
boys in a class. In how many ways can 2 girls
and 2 boys be selected for a group project?
15
C
2
X
18
C
2
= 16,065

19. Generalization of
permutation

20. Generalization of
permutation
The number of permutations of n objects, where there are
n_1 indistinguishable objects of type 1,
n_2 indistinguishable objects of type 2,
………………
n_t indistinguishable objects of type 1
1 2
!
!. ! !
t
n
n n n

21. Generalization of
Combination
Let X be a set with t elements.
The number of ways to select k elements in X (k may be greater than t
) is
    1, 1 1, .C k t t C k t k     

22. Example 6
1. How many ways to construct a code which is made of alphabet of
MATHEMATICS?
2. How many solution of the equation
1 2 3
20, 0
i
x x x x   

23. Solution
1. Determining the number of ways to construct a code which is made
of alphabet of MATHEMATICS.
(This is an example of generalized permutatation).
Solution: The number of objects = n = 11.
There are: 2 objects M; 2 objects A; 2 objects T; 1 object H; 1 object E; 1
object I; 1 object C; 1 object S.
The number of permutations of n objects
= =
11!
2!.2!2!.1.1.1.1.11 2 8
!
!. ! !
n
n n n

24. Solution
1. Solution of the equation:
(This is an example of generalized combination)
Solution:
The number of different objects = t=3
The number of ways to select 20 elements from 3 elements.
C=
1 2 3
20, 0
i
x x x x   
   1, 1 (22,2)C k t t C   

25. Solution
1. Solution of the equation:
(This is an example of generalized combination)
Solution:
The number of different objects = t=3
The number of ways to select 5 elements from 3 elements.
C=
1 2 3
5, 0
i
x x x x   
   1, 1 (7,2)C k t t C   

26. 26
The pigeonhole principle
Suppose a flock of pigeons fly into a set of
pigeonholes to roost.
If there are more pigeons than pigeonholes, then
there must be at least 1 pigeonhole that has more
than one pigeon in it
If k+1 or more objects are placed into k boxes, then
there is at least one box containing two or more of
the objects (Theorem 1)

27. 27
Examples
1. In a group of 13 people, since there are 12 possible birthdays, there
must be at least two people with the same birthday
2. In a group of 27 English words, since there are only 26 letters, there will be
at least two words must start with the same letter

28. 28
Generalized pigeonhole principle

29. 29
Examples
1. Among 50 people, there are at least 50/12 = 5 people which born
on the same month
2. How many students in a class must there be to ensure that 6
students get the same grade (one of A, B, C, D, or E)?
◦The k represents the number of “boxes” (the grades), i.e., k = 5
◦We should get N/5 = 6
◦Thus, Lowest possible value for N is 26

30. 30
Rosen, section 4.2, question 4
A bowl contains 10 red and 10 yellow balls
a)How many balls must be selected to ensure 3 balls of the same
color?
◦Via generalized pigeonhole principle
◦How many balls are required if there are 2 colors, and one color must have 3 balls?
◦How many pigeons are required if there are 2 pigeon holes, and one must have 3
pigeons?
◦number of boxes: k = 2
◦We want N/k = 3
◦What is the minimum N?
◦N = 5

31. 31
Rosen, section 4.2, question 32
6 computers on a network are connected to at least 1 other
computer
Show there are at least two computers that are have the
same number of connections
The number of boxes, k, is the number of computer
connection: i.e., 1, 2, 3, 4, or 5
The number of pigeons, N, is the number of computers
◦That is 6
By the generalized pigeonhole principle, at least one box
must have N/k objects
◦6/5 = 2
◦Thus, at least two computers must have the same number of
connections

32. Examples
In a group with 6 people, assume that there are two possibilities of a
pair of persons: friend or enemy. Show that there is 3 pairs which are
friends or 3 pairs which are enemies.
Solution
Given the people A,B,C,D,E
Let k be the possibilities of a pair of persons, .i.e. friend or enemy.
Hence, k=2.
Let A be one of the 6 people. Then, there are N = the number of people
that will be friend or enemy with A. Thus N=5.
Therefore, there will be at least 5/2 = 3 pairs which are friends or 3
pairs which are enemies.

33. Exercises
Solve some problems on Rosen (7
th
edition) :
1. Number#9#:
2. Number #17#
3. Number 26

34. Exercises (Counting
problems)
4. Page 396
5. Page 413

35. Exercises
6. How many solution of equation:
7. How many ways to construct a code which is made of alphabet of
DRESSCODE?
1 2 3 4
20, 0
i
x x x x x    