Transcript PowerPoint Presentation - Unit 1 Module 1 Sets, elements

Part 1 Module 4
The Fundamental Counting Principle
EXAMPLE 1.4.1
Plato is going to choose a
three-course meal at his
favorite restaurant. He must
choose one item from each
of the following three
categories.
First course: Tofu Soup (TS);
Seaweed Salad (SS)
Second course: Steamed Tofu
(ST); Baked Tofu (BT);
Fried Tofu (FT);
Third course: Tofu Cake (TC);
Tofu Pie (TP); Seaweed
Delight (SD)
How many different threecourse meals are possible?
A. 12
C. 8
P1M4
B. 18
D. None of these
1
Part 1 Module 4
The Fundamental Counting Principle
We will list every possible 3-course meal:
1. TS-ST-TC
2. TS-ST-TP
3. TS-ST-SD
4. TS-BT-TC
5. TS-BT-TP
6. TS-BT-SD
7. TS-FT-TC
8. TS-FT-TP
9. TS-FT-SD
10. SS-ST-TC
11. SS-ST-TP
12. SS-ST-SD
13. SS-BT-TC
14. SS-BT-TP
15. SS-BT-SD
16. SS-FT-TC
17. SS-FT-TP
18. SS-FT-SD
There are 18 different 3-course meals.
P1M4
2
The Fundamental Counting Principle
You probably noticed that there is a more
economical way to answer that question.
Choosing a three-course meal requires three
independent decisions:
1. Choose first course item (2 options).
2. Choose second course item (3 options)
3. Chooose third course item (3 options)
2x3x3 = 18 different three-course meals.
P1M4
3
The Fundamental Counting Principle
This illustrates the Fundamental Counting Principle,
which describes a technique for determining the
number of different outcomes in certain complex
processes:
Step 1: Analytically break down the complex
process into a number of distinct stages or
decisions;
Step 2: Determine the number of options for each
decision identified in Step 1;
Step 3: Multiply the numbers from Step 2.
P1M4
4
Why it works
The Fundamental Counting Principle works when
we have an orderly decision process that has an
underlying tree structure. We are counting the
number a branch-tips at the end of the tree.
P1M4
5
Why it works
FIRST
COURSE
SECOND
COURSE
ST
THIRD
COURSE
TC
TS-ST-TC
TP
SD
TS-ST-TP
TC
FT
BT
TS
SS
ST
TP
SD
TC
BT
TS-FT-TP
TS-FT-SD
TS-BT-TC
TP
SD
TS-BT-TP
TC
SS-ST-TC
TP
SD
SS-ST-TP
TC
FT
TS-ST-SD
TS-FT-TC
TP
SD
TC
TP
SD
TS-BT-SD
SS-ST-SD
SS-FT-TC
SS-FT-TP
SS-FT-SD
SS-BT-TC
SS-BT-TP
SS-BT-SD
P1M4
6
Fundamental Counting Principle
The simplest Fundamental Counting
Principle problems are those in which
we are presented with a menu, and
the situation dictates that we must
choose one item from each category
on the menu.
P1M4
7
EXAMPLE 1.4.12
Gomer is considering the purchase of a new super-cheap sport/utility
vehicle, the Skuzuzi Kamikaze. He must choose a vehicle, taking into
account the following options:
i. Transmission: 4-speed standard transmission, 5-speed standard
transmission, or automatic transmission;
ii. Bumper: steel bumpers, vinyl bumpers or 2x4 boards bolted to the
front and back;
iii. Top: hard-top, vinyl top convertible, or chicken wire stapled over the
roll bar;
iv. Funerary accessory: complementary funeral wreath or cremation
urn.
1. How many different vehicle option packages are possible?
2. How many packages are possible if he already knows that he will order
the chicken wire and can’t order the steel bumpers?
P1M4
8
Solution 1.4.12 - 1
1. How many different vehicle option packages are possible?
Gomer must make four independent decisions.
i. Transmission: 3 options (4-speed standard transmission, 5-speed
standard transmission, or automatic transmission};
ii. Bumper: 3 options (steel bumpers, vinyl bumpers or 2x4 boards bolted
to the front and back);
iii. Top: 3 options (hard-top, vinyl top convertible, or chicken wire stapled
over the roll bar);
iv. Funerary accessory: 2 options (complementary funeral wreath or
cremation urn)
According to the Fundamental Counting Principal, the number of outcomes
for this decision process is
(3)(3)(3)(2) = 54
P1M4
9
Solution 1.4.12 - 2
2. How many packages are possible if he already knows that he will order
the chicken wire and can’t order the steel bumpers?
Again, Gomer must make four independent decisions. We must take into
account the effects of the predetermined conditions.
i. Transmission: 3 options (4-speed standard transmission, 5-speed
standard transmission, or automatic transmission};
ii. Bumper: 2 options ( vinyl bumpers or 2x4 boards bolted to the front
and back);
iii. Top: 1 option (chicken wire stapled over the roll bar);
iv. Funerary accessory: 2 options (complementary funeral wreath or
cremation urn)
According to the Fundamental Counting Principal, the number of outcomes
for this decision process is
(3)(2)(1)(2) = 12
P1M4
10
Exercise
Prior to the start of a polo match, the captains of the two teams
gather in the country club lounge. One team has 4 captains, and
the other team has 3 captains.
If each captain of the first team shakes hands with each captain
of the second team, how many handshakes occur?
P1M4
11
Exercise
A quiz consists of 3 true/false questions followed by 4 multiplechoice questions, with 4 options for each multiple-choice question.
In how many ways is it possible to answer the 7 questions?
A. 264
B. 507
C. 2424
D. None of these.
The number of ways to answer the 3 true/false questions is 23 = 8.
The number of ways to answer the 4 multiple-choice questions is 44 = 256.
Thus, the number of ways to answer all 7 questions is (8)(256) = 2048.
The correct answer is 'D. '
P1M4
12
EXAMPLE 1.4.6
There are 5 guys (including Gomer)
on Gomer's bowling team. After
their game they will each choose
one of the following:
Dr. Pauper, Dr. Thunder, or Dr. Special.
How many outcomes are possible?
P1M4
13
SOLUTION 1.4.6
Since there are five guys, each of whom must
make a decision, this counting process
involves five independent decisions. Call the
five guys Al, Bill, Carl, Doug and Gomer.
Al has 3 options (he can choose Dr. Pauper, Dr.
Thunder, or Dr. Special).
Bill has 3 options.
Carl has 3 options.
Doug has 3 options.
Gomer has 3 options.
According to the Fundamental Counting Principle,
the number of outcomes is
(3)(3)(3)(3)(3) = 243
P1M4
14
EXAMPLE 1.4.6 - 2
Again, there are 5 guys (including Gomer) on Gomer's
bowling team. After the game they will each choose
one of the following:
Dr. Pauper, Dr. Thunder, or Dr. Special.
However, Bill and Doug are having a spat, so they never
agree on anything.
How many outcomes are possible, assuming that Bill
and Doug will not order the same product?
P1M4
15
SOLUTION 1.4.6 - 2
This counting process involves five decisions, but
two of the decisions (Bill’s and Doug’s)
influence one another. Call the five guys Al,
Bill, Carl, Doug and Gomer.
Al has 3 options (he can choose Dr. Pauper, Dr.
Thunder, or Dr. Special).
Bill has 3 options.
Carl has 3 options.
Doug has only 2 options (he cannot choose
whatever product was chosen by Bill).
Gomer has 3 options.
According to the Fundamental Counting Principle,
the number of outcomes is
(3)(3)(3)(2)(3) = 162
P1M4
16
72 Dr. Pepper Clones
P1M4
17
72 Dr. Pepper Clones
If each of the five guys in our previous example drank
one of the 72 displayed Dr. Pepper clones at the end
of their bowling game, how many possible outcomes
of choices are there?
Solution: Each of the five guys has 72 choices,
meaning there are 5 independent decisions being
made with 72 options for each decision. According to
the Fundamental counting Principle, the number of
outcomes is
(72)(72)(72)(72)(72) = 1,934,917,632
P1M4
18
Exercise
The dial on a combination lock has numbers ranging from 1 to 30. The
“combination” that opens the lock is a sequence of three numbers.
How many different combinations are possible, assuming that the combination
may have repeated numbers, but the same number will not appear twice
consecutively?
For example,
29-15-8,
7-13-22,
14-2-14,
8-29-15
are four different possible combinations,
but
5-5-12 and
3-16-16 are not acceptable.
P1M4
19
Solution
To create a three-number sequence, such as 15-3-18,
requires three decisions:
i. Choose first number: 30 options
ii. Choose second number: 29 options (whichever one of the
thirty numbers was chosen for the first number is not
available, because the same number cannot be used twice in
a row).
iii.Choose third number: 29 options (whichever one of the
thirty numbers was chosen for the second number is not
available, because the same number cannot be used twice in
a row).
30x29x29 = 25,230 different outcomes (choice C).
P1M4
20
Example 1.4.11 #1
How many different 4-digit numbers can be formed
using the following digits?
{0, 2, 3, 5, 8}
Note: the first digit cannot be 0, or else the number would be a 3-digit number.
P1M4
21
Solution 1.4.11 #1
How many different 4-digit numbers can be formed
using the following digits?
{0, 2, 3, 5, 8}
In order to form a 4-digit number we must make four independent decisions:
i.
Choose first digit: 4 options (the first digit could be 2, 3, 5, or 8).
ii.
Choose second digit: 5 options (the second digit could be 0, 2, 3, 5, or
8).
iii.
Choose third digit: 5 options (the third digit could be 0, 2, 3, 5, or 8).
iv.
Choose fourth digit: 5 options (the fourth digit could be 0, 2, 3, 5, or 8).
According to the Fundamental Counting Principle the number of outcomes
is(4)(5)(5)(5) = 500. There are 500 possible 4-digit numbers.
P1M4
22
Example 1.4.11 #2
How many different 4-digit numbers can be formed
using the following digits, assuming that the 4-digit
number is a multiple of five?
{0, 2, 3, 5, 8}
A. 100
B. 4552
C. 4551
D. 200
E. None of these
P1M4
23
Solution 1.4.11 #2
How many different 4-digit numbers can be formed
using the following digits, assuming that the 4-digit number is a multiple of
five?
{0, 2, 3, 5, 8}
In order to form one of these numbers, again we need to make 4 decisions.
However, in this case the last digit must be either 0 or 5 (in order for the
number to be a multiple of 5).
i. Choose first digit: 4 options (the first digit could be 2, 3, 5, or 8).
ii. Choose second digit: 5 options (the second digit could be 0, 2, 3, 5, or 8).
iii. Choose third digit: 5 options (the third digit could be 0, 2, 3, 5, or 8).
iv. Choose fourth digit: 2 options (the fourth digit must be 0 or 5).
According to the Fundamental Counting Principle the number of outcomes is
(4)(5)(5)(2) = 200. There are 200 possible 4-digit multiples of 5.
P1M4
24
Example
Gomer is going to order a frozen tofu cone from I
Definitely Believe It's Tofu.
The following toppings are available:
1. carob chips
2. frosted alfala sprouts
3. seaweed sprinkles
4. rolled oats
5. rose hips
He may choose all, some or none of these toppings.
How many topping combinations are possible?
A. 5
B. 10
C. 25
D. 32
E. 120
P1M4
25
What are we trying to count?
Five toppings: CC, FAS, SS, RO, RH
Here are several different combinations of items.
1. RO, SS
2. FAS
3. RH, CC, FAS
4. SS, CC
5. CC, FAS, RO, RH
6.
(blank: this means we didn’t choose any of the toppings)
7. CC, FAS, SS, RO, RH
8. SS
How many of these are possible?
P1M4
26
What are we trying to count?
We have a set of five toppings: {CC, FAS, SS, RO, RH}
Here are several different combinations of items.
1. {RO, SS}
2. {FAS}
3. {RH, CC, FAS}
4. {SS, CC}
5. {CC, FAS, RO, RH}
6. { }
(this means we didn’t choose any of the
toppings)
7. {CC, FAS, SS, RO, RH}
8. {SS}
Each combination of toppings is a subset of the five-topping
set, so we are just counting the number of subsets in a
set with five elements, which is 25 = 32.
P1M4
27
Alternative solution, using FCP
We have a set of five toppings: {CC, FAS, SS, RO, RH}
We have shown that the number of different combinations of
toppings is 32, because each combination of toppings is a
subset of this set, and a set with 5 elements has 32
subsets.
We can also get this answer by using the FCP. When we
select a combination of toppings we are actually making
five “yes/no” decisions:
1. carob chips: 2 options (“yes” or “no”)
2. frosted alfalfa sprouts: 2 options (“yes” or “no”)
3. seaweed sprinkles: 2 options (“yes” or “no”)
4. rolled oats: 2 options (“yes” or “no”)
5. rose hips: 2 options (“yes” or “no”)
According to the FCP, the number of outcomes is
2  2  2  2  2 = 32
P1M4
28
“All, some, or none”
If a counting problem involves an “all, some, or none”
situation, then the number of outcomes will always be a
power of 2 (such as 2, 4, 8, 16, 32, 64, 128, 256 and so
on).
This is because the situation involves a series of two-way
(“yes or no”) decisions, so the Fundamental Counting
Principle will have us multiplying a series of twos.
This also due to the fact that such a problem is asking for the
number of subsets in a particular set.
P1M4
29
Exercise
Homerina is having a birthday party for her pet
wolverine, John. John has a list of 9 gifts that he
would like to receive: a duck, a hamster, a puppy, a
mouse, a goldfish, a frog, a toad, a chicken, and a
claw sharpener.
How many combinations of gifts are possible, assuming
that Homerina may buy all, or some, or none of
those items?
A. 81
B. 1280
C. 512
D. 18
E. None of these
P1M4
30
Solution
For each of the nine gifts, Homerina faces a “yes/no”
decision, so this is an FCP problem featuring nine
independent decisions:
1. duck: 2 options (“yes” or “no”)
2. hamster: 2 options
3. puppy: 2 options
4. mouse: 2 options
5. goldfish: 2 options
6. frog: 2 options
7. toad: 2 options
8. chicken: 2 options
9. claw sharpener: 2 options
According to the FCP, the number of outcomes is
2  2  2  2  2  2  2  2  2 =P1M4
512
31
Exercise
Hjalmar, Gomer, Plato, Euclid, Socrates, Aristotle,
Hjalmarina and Gomerina form the board of directors
of the Lawyer and Poodle Admirers Club.
They will choose from amongst themselves a
Chairperson, Secretary, and Treasurer.
No person will hold more than one position.
How many different outcomes are possible?
A. 336
B. 24
C. 512
D. 21
P1M4
32
Solution
Choosing a Chairperson, Secretary and Treasurer from among these 8
people requires us to make three decisions. NOTICE these three
decisions are not independent. For instance, the choice we make when
we select the chairperson affects which options are available when we
go to choose the Secretary, since the person selected to be
Chairperson cannot also be selected to be Secretary.
i. Choose Chairperson: 8 options;
ii. Choose Secretary: 7 options (one person has already been chosen to be
Chairperson);
iii. Choose Treasurer: 6 options (two people have already been chosen to
be Chairperson and Secretary, respectively).
According to the Fundamental Counting Principle the number of outcomes
is:
(8)(7)(6) = 336.
P1M4
33
Exercise
Erasmus is trying to guess the combination to his
combination lock.
The "combination" is a sequence of three numbers,
where the numbers range from 1 to 12, with no
numbers repeated.
How many different "combinations" are possible if he
knows that the last number in the combination is
either 1 or 11?
A. 264
B. 1320
C. 220
D. 288
E. 180
P1M4
34
Solution
Choosing a three-number sequence having no repeated numbers requires that we
make three dependent decisions. One of these decisions, however, has a
special condition attached to it (the third number must be either 1 or 11).
When using the Fundamental Counting Principle in a situation involving
dependent decisions, if one decision has a special condition, that
decision must be treated first, because the special condition overrides the
other decisions.
For example, that fact that the third number must be 1 or 11 means that it is
impossible for the sequence to simultaneously have 1 for the first number and
11 for the second number (since then there would be nothing left for the third
number).
Three dependent decisions:
1. Choose third number (two options);
2. Choose first number (11 options);
3. Choose second number (10 options).
According to the Fundamental Counting Principle the number of possible outcomes
is
(2)(11)(10) = 220.
P1M4
35
Dependent decisions
If a Fundamental Counting Principle problem involves
dependent decisions, and one decision involves a
special condition, the decision with the special
condition takes priority over the others.
P1M4
36
Example
The Egotists' Club has 6 members: A, B, C, D, E, and F. They are
going to line up, from left to right, for a group photo. After lining
up in alphabetical order (ABCDEF), Mr. F complains that he is
always last whenever they do things alphabetically, so they
agree to line up in reverse order (FEDCBA) and take another
picture. Then Ms. D complains that she's always stuck next to
Mr. C, and that she never gets to be first in line.
Finally, in order to avoid bruised egos, they all agree to take pictures
for every possible left-to-right line-up of the six people. How
many different photos must be taken?
A. 14
B. 720
C. 823,543
D. None of these
P1M4
37
Solution
To form a six-person line-up requires six dependent
decisions:
Choose first (leftmost) person: 6 options
Choose second person: 5 options
Choose third person: 4 options
Choose fourth person: 3 options
Choose fifth person: 2 options
Choose last (rightmost) person: 1 option
6  5  4  3  2  1 = 720 different arrangements or
permutations on six people in a row.
P1M4
38
Similar situations
Suppose we had the same situation, but with 8 people
instead of six. Then the number of ways to arrange
them in a row would be
8  7  6  5  4  3  2  1 = 40,320
Likewise, if there were ten people, the number of
arrangements would be
10  9  8  7  6  5  4  3  2  1 = 3,628,800
and so on
P1M4
39
Factorials
Numbers like
654321
87654321
10  9  8  7  6  5  4  3  2  1
are called factorials.
P1M4
40
Factorials
6  5  4  3  2  1 is called “6 factorial”
denoted 6!
8  7  6  5  4  3  2  1 is called “8 factorial”
denoted 8!
10  9  8  7  6  5  4  3  2  1 is called “10
factorial”
denoted 10!
P1M4
41
“n factorial”
If n is a positive integer, then n factorial, denoted n!, is
the number n multiplied by all the smaller positive
integers.
n! = n  (n–1)  (n–2)  …  3  2  1
n! is the number of ways to arrange n objects.
Also,
0! = 1
P1M4
42
Exercise
Macbeth is trying to guess the password for Gomerina's
email account. He knows that the password consists
of 4 letters chosen from this set:
{g,o,m,e,r,i,n,a}.
How many passwords are possible, if a password does
not contain repeated letters and the third letter is a
vowel?
A. 32
B. 256
C. 840
D. 1344
E. None of these
P1M4
43
Solution
Macbeth is trying to guess the password for Gomerina's email account. He
knows that the password consists of 4 letters chosen from this set:
{g,o,m,e,r,i,n,a}.
How many passwords are possible, if a password does not contain
repeated letters and the third letter is a vowel?
In order to guess a password Macbeth has to make four dependent
decisions.
Since the choice of the third letter affects the other choices, that decision
must be made first.
There are four options for the third letter, and then there are seven options
for the first letter, six options for the second letter, and five options for
the last letter.
According to the Fundamental Counting Principle, the number of possible
outcomes is (4)(7)(6)(5) = 840.
P1M4
44
“All, some, or none”
If a counting problem involves an “all, some, or none”
situation, then the number of outcomes will always be a
power of 2.
This is because the situation involves a series of two-way
(“yes or no”) decisions.
This also due to the fact that such a problem is asking for the
number of subsets in a particular set.
P1M4
45