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 three-course meals are possible?
Solve this problem by listing every possible 3-course meal.

SOLUTION

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

We see that there are 18 different three-course meals.

However, there is an easier way to get at this answer. Notice that in order to choose a three-course meal, we need to make three decisions:

1. Choose item for first course: There are 2 options.
2. Choose item for second course: There are 3 options
3. Choose option for third course: There are 3 options.

Now observe that (2)(3)(3) = 18.

This is not a coincidence. It is an illustration of the Fundamental Counting Principle.




The Fundamental Counting Principle (FCP)
To determine the number of different outcomes that are possible in some complex process:
1. Analytically break down the process into separate stages or decisions.
2. Count the number of options that are available at each stage or decision.
3. Multiply together all of the numbers from Step 2 above.









EXAMPLE 1.4.2
How many different three course meals are possible if Plato has already decided that he won't have Baked Tofu and he will have Seaweed Delight?

SOLUTION

We will use the Fundamental Counting Principle.
1. Choose item for first course: 2 options
2. Choose item for second course: 2 options (since he won't choose Baked Tofu)
3. Choose item for third course: 1 option (since it has already been decided that he will choose Seaweed Delight).

(2)(2)(1) = 4 different 3-course meals



The primary advantage to the use of the Fundamental Counting Principle becomes apparent when we have more complicated decision processes. For example:

EXAMPLE 1.4.3

Referring to the situation in the previous example, suppose that the restaurant becomes quite successful and so the operators decide to expand their menu. Now there are 5 items for the first course, 7 items for the second course, 4 items for the third course, and a new fourth course is added (the seltzer course, in which we choose between Bromo- and Alka-). How many four-course meals are possible?


SOLUTION
To choose a 4-course meal requires that we make four decisions. There are 5 options, 7 options, 4 options and 2 options, respectively, for each of these decisions.

(5)(7)(4)(2) = 280 different 4-course meals.

It would be very cumbersome to try to solve this problem by listing every possible outcome, since there are so many different outcomes.



















EXAMPLE 1.4.4
1. A student will schedule her classes next semester by choosing one course from each of the following categories:

i. ARH3130, ARH3150, or ARH4110
ii. STA1013, CGS2030, MGF1107 or MAC1105.
iii. ENC1142, ENC1144, or ENC1145
iv. WOH1023, WOH1030, AMH1000, EUH2100 or AFH1000.

How many different 4-course combinations are possible?

A. 180
B. 27
C. 15
D. 16


2. How many 4-course combinations are possible if she knows that she can't take ARH4110 and she will take STA1013?




see solution



EXAMPLE 1.4.5

Prior to the coin toss for a football game, the captains of the two teams meet at midfield. Team A has 4 captains, and team B has 3 captains. Each captain of team A shakes hands once with each captain of team B. Bill Gates has recently acquired the copyright on handshakes, and so he wants to know how many handshakes occur, in order to collect his royalty. How many handshakes occur?




see solution








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?





see solution







EXAMPLE 1.4.7
In Florida, standard automobile license plate "numbers" used to follow the following scheme: 3 letters -- 2 digits -- 1 letter
Examples: JKP47R
TRR39S
VWN22Y
ZQW05Z


1. How many different license plate codes were possible under this scheme?




see solution

EXAMPLE 1.4.8

Gomer has to take a 5 question true/false quiz, but he hasn't studied. He will guess at each problem. In how many different ways is it possible to answer the quiz questions? How likely is it that he will get a score of 100%?



see solution








EXAMPLE 1.4.9

Gomer has to take a 25 question multiple-choice test, but he hasn't studied. He will guess at each problem. For each problem the possible responses are A, B, C, or D. In how many different ways is it possible to answer the test questions? How likely is it that he will get a score of 100%?


see solution










EXAMPLE 1.4.10

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?





see solution








EXAMPLE 1.4.11

1. How many different 4-digit numbers can be formed using the following digits? (Note: the first digit cannot be 0, or else the number would be a 3-digit number).
{0, 2, 3, 5, 8}

2. How many different 4-digit numbers that are multiples of 5 can we form?


see solution












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.



How many different vehicle option packages are possible?



see solution

































EXAMPLE 1.4.13

Homer, Gomer, Plato, Euclid, Socrates, Aristotle, Homerina 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




see solution


Special terminology: in the previous example, we determined that there were 336 different ways to choose 3 people from a set of 8 people, and arrange the 3 people according to who gets which title. In general, the number of ways to choose and arrange 3 objects from a set of 8 objects is called "the number of permutations of 8 things taken 3 at a time," and this number is always 336.


More special terminology: we say that a series of decisions are independent if the result of one decision does not affect the options that are available for other decisions.
On the other hand, if the result of one decision limits the options that are available for other decisions, we say that the decisions are dependent.






EXAMPLE 1.4.14

A couple is expecting the birth of a baby boy. They will name the child by choosing a first name and middle name from this list of their favorite boys' names: Jacob, Jonah, Joshua, Jeremy, James, Joseph. The first name will be different from the middle name. How many different two-part names are possible? (Example: Joseph Jeremy, Jeremy Joseph, and Joshua James are three different, valid two-part names; Jacob Jacob is not a valid possibility.)
A. 36
B. 12
C. 30
D. 11



see solution


Terminology: in the previous example we saw that there are 30 ways to choose two different names from a list of six names, and arrange the two names according to which one is the "first name" and which one is the "middle name." More generally, the number of ways to choose and arrange 2 objects from a set of 6 objects is called the number of permutations of 6 things taken 2 at a time," and this number will always be 30.






EXAMPLE 1.4.15

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

see solution



















EXAMPLE 1.4.16

Adam, Beth, Charles, Dawn, and Ernie are the five finalists in the fabulous Clearers Publishinghouse sweepstakes. Through a random selection process, one of them will win a pen-and-pencil set, one of them will win a one-year supply of cat food, and one of them will win a brand new Chevy blazer (that is, a vinyl sports jacket with the words "Chevy" embossed on the back). Nobody will win more than one prize.
How many different outcomes are possible?
A. 125
B. 15
C. 12
D. 60










EXAMPLE 1.4.17

AB
dreadfulfiend
unmanner'ddog
murderoushog
wranglingcacodemon
elvish-mark'ddissembler
abortivetoad
rootinghomicide
foulhedgehog
defusedinfection of a man
cursedvillain
devilishlump of foul deformity
detesteddevil
poisonousminister of hell
bunchback'dbeggar
bottled spider
slander of thy mother's heavy womb


Suppose we want to form a three-part Shakespearean insult, such as "Thou dreadful, wrangling, minister of hell" by choosing two adjectives from column A and one noun phrase from column B.
How many different insults are possible? (Assume, for instance, that
"Unmanner'd, elvish-marked, lump of foul deformity" is different from
"Elvish-marked, unmanner'd, lump of foul deformity.")
The vocabulary comes from Act I of King Richard III.









EXAMPLE 1.4.18
Homer is going to buy a 1986 Yugo. He has shopped around, and has found that '86 Yugos are available with any combination of the following options: plush Corinthian vinyl interior, padded steering wheel, tinted windows, bucket seats, motor, windshield. How many different option packages are possible?
















EXAMPLE 1.4.19

How many 5-digit numbers are multiples of 5? (By 5-digit numbers, we mean that the leading digit is not 0. For instance, we consider 02382 to be a 4-digit number, since the leading digit is 0.)
A. 50000
B. 90000
C. 45000
D. 18000










EXAMPLE 1.4.20
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?

see solution






see solution







Download practice exercises (PDF file)