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
B. 18
D. None of these
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.
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.
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.
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.
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
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.
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?
A. 54
B. 11
C. 81
D. None of these
2. How many packages are possible if he already knows that he will order
the chicken wire and can’t order the steel bumpers?
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
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
EXAMPLE 1.4.6
There are 5 guys (including Gomer)
on Gomer's bowling team. After
the beer frame they will each
choose one of the following:
Scud, Scud Lite, or Scud Ice.
How many outcomes are possible?
A. 60
B. 125
C. 15
D. 243
E. None of these
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 Scud, Scud Lite,
or Scud Ice).
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) = 343
EXAMPLE 1.4.6 - 2
Again, there are 5 guys (including Gomer) on
Gomer's bowling team. After the beer
frame they will each choose one of the
following: Scud, Scud Lite, or Scud Ice.
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?
A. 27
B. 108
C. 81
D. None of these
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 Scud, Scud Lite,
or Scud Ice).
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
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.
A. 27,000
B. 24,360
C. 25,230
D. None of these
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).
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.
Solution 1.4.11 #11
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.
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
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.
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
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?
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.
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
“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.
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
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 = 512
“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.
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
Solution
Choosing a Chairperson, Secretary and Treasurer from among these 8
people requires us to make three decisions. However (unlike in all of
the previous examples) 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.
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
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.
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.
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
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.
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
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.
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!
“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
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
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.