MGF1106 Lecture Outlines – Ms. Harris Sp’2017
Part 1 Module 1 - Sets, elements, subsets

Any collection of objects is a __________________.
The objects contained in a set are called its __________________ or _______________________.
The __________________________defines a particular set by listing its elements, separated by commas, within
curly brackets.

Names for sets
It is conventional to use capital letters for names of sets.
S = {a, b, c}
A = {1, 2, 3, 4, 5}
T = {Moe, Larry, Curly}

B = {cat, dog}

Sets, elements
Referring to the sets
S = {a, b, c} and T = {Moe, Larry, Curly},
we observe, for example, that “a ________________________________ S” and “Larry _______________________ T.”
These statements are denoted symbolically, as follows:

We can also observe that _________________________________________ and __________________________________________
These statements are denoted symbolically, as follows:

Cardinality
The ________________________________ of a set is the number of elements contained in that set.
For example, let S = {a, b, c} and B ={dog, cat}.
Then, the cardinality of S is ____________________and the cardinality of B is ______________________.
These facts are denoted symbolically, as follows:In general, if V is any set, then ___________________ represents the __________________________ in set V.

Set Equality

Two sets are equal if they _________________________________________________________ elements.
For example{1, 2, 3, 4, 5} = {5, 3, 1, 4, 2}{Moe, Larry} = {Moe, Larry}{b, c, a} = S (referring to the set S defined earlier).
However,{1, 2, 3, 4, 5}{a, b, c, d, e}1More formally, if V and W are any sets, then V = W
means that every element of V is ____________________________________W
and every element of W _____________________________________V. Note that the order in which the elements arelisted is not important.

Subsets (informal definition)
Suppose V is a set, and W is a set that is formed using only the elements of V
(that is, W can be formed entirely by including/excluding elements of V).
We say that W _______________________________________________V.
This is conveyed symbolically as follows:

ExampleLet T = {Moe, Larry, Curly}. List all the subsets of T.

{ } This set is known as the ______________________, and it is also a subset of T.
Observe the following, from the previous example.
1. {Moe, Larry, Curly}{Moe, Larry, Curly}
General fact: Every set is _______________________________________________.
2. { }{Moe, Larry, Curly}
General fact: The empty set is a _______________________________________.
Here is a more formal definition of the term subset:
Suppose V and W are sets, and that every element of W is also an element of V.
Then W
V.
This is equivalent to saying that W is a subset of V, if there is no element of W that isn’t also anelement of V.
Examples (True or false)
1. {b, h, r, q}{h, r}
2. {3, 12, 5, 19}{19, 3, 5, 12, 18}
3. {a, 13, d, 2}{13, 2, d, a}2

A. True
A. True
A. True

B. False
B. False
B. FalseProper Subsets
Suppose W is a subset of V, but W is not equal to V.
Then W is a _________________________________________of V.
This is denoted

A proper subset is a subset that is not equal to the set it is a subset of.
A proper subset is a subset that is “smaller than” the set it is a subset of.
A moment ago, we listed all the subsets of the set {Moe, Larry, Curly}. Here they are:1. { }
2. {Moe}
3. {Larry}
4. {Curly}
5. {Moe, Larry}
6. {Moe, Curly}
7. {Larry, Curly}
8. {Moe, Larry, Curly}
Which of these are also proper subsets of {Moe, Larry, Curly}?
Answer: __________________________________________________________

Complements and Universal Sets
Let T = {Moe, Larry, Curly}. List all elements that aren’t in T.

Universal Sets
For a particular discussion or sequence of exercises in set mathematics, a Universal Set (U) is “larger” setthat contains, ________________________________________________________________________________________.
A universal set serves as a frame of reference for the discussion.
ExampleLet U = {Moe, Larry, Curly, Shemp, Curly Joe}.
Let T = {Moe, Larry, Curly}.
List a set containing all the elements that aren’t in T.

We call this set the _________________________________________, denoted

Set-builder notation
So far, we have been using the roster method for defining sets. The roster method defines a set by listing
its elements. An alternative approach is to define a set by _____________________ its elements, rather thanliterally listing them.
Set-builder notation is a way of defining a set by describing its elements, rather than listing them.

3

Example
Let U = {a, b, c, d, e, f}.
The universe for this discussion consists of six letters, four of which are consonants, two of which
are vowels. Within this universe, let C be the set containing all the consonants, and let V be the set
containing all the vowels.
C = {x|x is a consonant}
C is “______________________________________, such that __________________________________________.”
C = {x|x is a consonant} = {}V = {x|x is a vowel}
V is “_____________________________________, such that _________________________________.”
V = {x|x is a vowel} = {}Exercises
Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A = {3, 5}
E = {2, 4, 6, 8, 10}
F = {x|x is an odd number}
True or false:
1. E
F
A. True
2. F
A
A. True
3. {1, 2, 3} {2, 3, 5, 6}
A. True
4. {4, 7} {4, 7}
A. True
5. {4, 7} {4, 7}
A. True
6. {4}{4, 7}
A. True

B. False
B. False
B. False
B. False
B. False
B. False

Let U = {Moe, Larry, Curly, Shemp, Curly Joe}
T = {Moe, Larry, Curly}
True or False:{}{}
A. True B. False

The number of subsets in a finite set

Common sense suggests that the more elements a set has, the more subsets it will have.
As we shall see, there is a precise relationship between the _________________________________________and the_______________________________________it has.
For a set V, suppose n(V) = k. Then V has ________________________ subsets and ___________________________
proper subsets.

4

Part 1 Module 2 - Set operations, Venn diagrams
Set operations
Let U = {x|x is an English-language film}
Set A below contains the five best films according to the American Film Institute.
Set B below contains the five best films according to TV Guide.
Set C below contains the five most passionate films according to the American Film Institute.
A = {Citizen Kane, Casablanca, The Godfather, Gone With the Wind, Lawrence of Arabia}
B= {Casablanca, The Godfather Part 2, The Wizard of Oz, Citizen Kane, To Kill A Mockingbird}
C = {Gone With the Wind, Casablanca, West Side Story, An Affair To Remember, Roman Holiday}.
Form a new set whose elements are those that sets A and B have in common
A = {Citizen Kane, Casablanca, The Godfather, Gone With the Wind, Lawrence of Arabia}
B= {Casablanca, The Godfather Part 2, The Wizard of Oz, Citizen Kane, To Kill A Mockingbird}
This set is called the ___________________________________ of A and B, denoted ____________________________.
A ∩ B = ____________________________________________________________________________________________.
Find B ∩ C

A different operation: form a new set that contains all the elements of A along with all the elements of B.
This set is called the __________________________________________________________, denoted ______________________.
We have encountered three basic set operations (including something from Part 1 Module 1).
Intersection
S ∩ T = ______________________________________Union
S ∪ T = ______________________________________
ComplementSʹ= ______________________________________

Venn Diagrams

A Venn diagram is a drawing in which sets are _______________________________________________________________________________________________________.
Venn diagrams can be used to illustrate _____________________________________, and the effects of set operations.
Venn diagrams are also used in other areas of mathematics, such as counting, probability and logic.

5Intersection
Let S, T represent any sets in a universe U. The Venn diagram below illustrates the effect of___________________. The shaded region corresponds to ___________________.
Union
Let S, T represent any sets in a universe U. The Venn diagram below illustrates the effect of___________________. The shaded region corresponds to ___________________.

Complement
Let S, T represent any sets in a universe U. The Venn diagram below illustrates the effect of___________________. The shaded region corresponds to ____________.
Exercise #1
U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
S = {3, 5, 8, 11}
T = {3, 4, 6, 7, 8, 10, 11}
V = {2, 5, 6, 7, 8}
W = {1, 3, 5, 6}
Find ( Vʹ ∩ Sʹ ) ∩ ( W ∪ T )A. { }
B. {4, 10, 11}
C. {1, 4, 10}
D. None of these

EXAMPLE 1.2.1 Venn diagrams
EXAMPLE 1.2.1 Venn diagrams

From your text:
EXAMPLE 1.2.1 #13
On the Venn diagram below, shade the region corresponding toA ∪ Bʹ.

A

B

U

P1M2

17

Exercise #3
Exercise #2
U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
T = {3, 4, 6, 7, 8, 10, 11}
V = {2, 5, 6, 7, 8}
Find (V ∩ Tʹ)ʹA. {1, 3, 4, 6, 7, 8, 9, 10, 11}
B. {3, 4, 10, 11}
C. {1, 3, 4, 6, 8, 9, 10, 11}
D. None of these

Exercise #3
Select the Venn diagram whose shaded region corresponds toAʹ ∪ Bʹ.

P1M2

20

Exercise #4
Exercise #4
Select the Venn diagram whose shaded region corresponds to(A ∩ B)ʹ.

P1M2

6

22

DeMorgan’s Laws
In the previous two exercises we saw that the shaded figure for (A ∩ B)ʹ is identical to the shaded figure
for Aʹ ∪ Bʹ. This means that Aʹ ∪ Bʹ and (A ∩ B)ʹ are _______________________________________.
This confirms one of the following general facts, known as DeMorgan’s Laws for Set Mathematics.
For any sets S, T
( S ∪ T)ʹ = Sʹ ∩ Tʹ
( S ∩ T)ʹ = Sʹ ∪ Tʹ“The _____________________________________is the intersection of the complements;
the __________________________________________is the union of the complements”.
Exercise #5
Let U = {a, b, c, d, e, f, g}
T = {c, e}
V = {a, d, e}Find ( Tʹ ∪ Vʹ )ʹ
A. {e}
B. {a, c, d, e}
C. {b, f, g}
D. None of these
Exercise #6
Exercise #6
LIKE EXAMPLE 1.2.3 from your text:
On the Venn diagram below, shade the region
corresponding to Bʹ ∩ (A ∪ Cʹ)
A

B

C
U

P1M2

28

Exercise #7
Exercise #7
Select the shaded figure for ( C ∩ Bʹ ) ∪ Aʹ

P1M2

32

7

Part 1 Module 3 - Survey Problems and Venn diagrams
Exercise # 1 (example 1.3.1 from text)
A survey of 64 informed consumers revealed the following information:
45 believe that Elvis is still alive
49 believe that they have been abducted by space aliens
42 believe both of these things
1. How many believe Elvis is still alive or believe that they have been abducted by space aliens?
2. How many believe neither of these things?
We will use Venn diagram to organize this information.

Exercise #2
99 grumpy old people were surveyed regarding things they dislike.
66 dislike puppies 34 dislike kitties
32 dislike children
10 dislike puppies and dislike kitties and dislike children
28 dislike puppies and dislike children
8 dislike kitties and don't dislike children and don't dislike puppies
25 dislike puppies and dislike kitties
How many don't dislike puppies and don't dislike kitties and don't dislike children?
A. 50

8

B. 48

C. 16

D. 21

E. None of theseGuidelines for 3-circle survey problems
1. If a description names __________________________________________________, then that description is pointing at_____________________________________________ of the eight regions of the diagram, so the accompanying number________________________________________________.
This is illustrated in the diagram below. Assume that a number of Neanderthals were surveyed regarding
their favorite possessions. Set S represents those who own a stick, R represents those who own a rock,and B represents those who own a bone.
3 own a rock anda bone but not a stick

R

3

B

5 own a rock anda bone and a stick5

7 own a stick but
don‘t own a rock anddon‘t own a bone

S7

2. If a description names the ____________________________________________, then that description is pointing at_________________________________________________, so the accompanying number gets ____________________________
regions of the diagram.
R

9 own a stickand rock

3 B
4 5 6

11 own a stick anda boneS7

3. If a description ___________________________________, then that description is pointing at__________________________________, so the accompanying number gets _________________________________________ ofthat circle.
20 own a
rock

R

8

1
3 B
4 5 6

15 owna boneS7

4. “And” means “intersection,” or means “union.”
8 own a
rock
AND a
bone

R

8

1
3 B
4 5 6
S7

R

8

26 own a stick OR
a bone(3+1+4+5+6+7 = 26)

3 1B

4 5 6
6

S7

6

9

Exercise #2
A number of young people were surveyed about their friends.
The results are summarized in the Venn diagram below.
How many have friends on MyFace.com and BookFace.com?
A. 19
B. 21
C. 57
D. None of these

15
M 19
1 2 3
A1

M: Have —friends“ on MyFace.com

B
17

B: Have —friends“ on BookFace.com
A: Have actual, real friends
4

Exercise #3
Using the same Venn diagram as above, how many have exactly one of the three kinds of friends?
A. 23
B. 33
C. 2
D. None of these
Exercise #4
Using the same Venn diagram as above, how many have actual, real friends, but don’t have friends on
Bookface.com?
A. 1
B. 5
C. 2
D. None of these
Exercise #5
Using the same Venn diagram as above, how many have actual real friends, or have friends on
MyFace.com?
A. 38
B. 16
C. 3
D. None of these10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 fromeach 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?

The Fundamental Counting Principle
We will list every possible 3-course meal:
1. TS-ST-TC

10. SS-ST-TC

2. TS-ST-TP

11. SS-ST-TP

3. TS-ST-SD

12. SS-ST-SD

4. TS-BT-TC

13. SS-BT-TC

5. TS-BT-TP

14. SS-BT-TP

6. TS-BT-SD

15. SS-BT-SD

7. TS-FT-TC

16. SS-FT-TC

8. TS-FT-TP

17. SS-FT-TP

9. TS-FT-SD

18. SS-FT-SD

There are 18 different 3 course meals.
You probably noticed that there is a more economical way to answer that question.
Choosing a three-course meal requires ________________________________________________:
1. Choose
2. Choose
3. Choose
Then notice that 2 x 3 x 3 = 18
This illustrates the _______________________________________________, which describes a technique fordetermining the number of different outcomes in certain complex processes:
Step 1: Analytically break down the complex process into a number of _____________________________;
Step 2: Determine the __________________________________________ for each decision identified in Step 1;
Step 3: ______________________________________ numbers from Step 2.

11

Why it works
The Fundamental Counting Principle works when we have an orderly decision process that has an________________________________________________. We are counting the number a branch-tips at the end of the
tree.
FIRST
COURSESECONDCOURSE

ST
FT

THIRD
COURSE

TC
TP
SD
TC
TP
SD

BT
TS

TC
TP
SD

SS
ST

TC
TP
SD
TC

FT

TP
SD

BT

TC
TP
SD

TS-ST-TC
TS-ST-TP
TS-ST-SD
TS-FT-TC
TS-FT-TPTS-FT-SD
TS-BT-TC
TS-BT-TP
TS-BT-SD

SS-ST-TC
SS-ST-TP
SS-ST-SD
SS-FT-TC
SS-FT-TPSS-FT-SD
SS-BT-TC
SS-BT-TP
SS-BT-SD

The simplest Fundamental Counting Principle problems are those in which we are presented with amenu, 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 automatictransmission;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?

How many packages are possible if he already knows that he will order the chicken wire and can’t orderthe steel bumpers?
12

Exercise – Prior to the start of a polo match, the captains of the two teams gather in the country clublounge. 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?

Exercise - A quiz consists of 3 true/false questions followed by 4 multiple-choice 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.
EXAMPLE 1.4.6 - 1
There are 5 guys (including Gomer) on Gomer's bowling team. After the frame they will each choose oneof the following: Dr. Pauper, Dr. Thunder, or Dr. Special.
How many outcomes are possible?

EXAMPLE 1.4.6 - 2
Again, there are 5 guys (including Gomer) on Gomer's bowling team. After the frame they will eachchoose 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?
A. 27
B. 108
C. 81
D. None of these

Exercise – 72 Dr. Pepper Clones
If each of the five guys in our previous example drank one of the 72 Dr. Pepper clones at the end of their
bowling game, how many possible outcomes of choices are there?

13

Exercise
The dial on a combination lock has numbers ranging from 1 to 30. The “combination” that opens the lockis 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.

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.

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. 100B. 4552
C. 4551
D. 200E. None of these14

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?
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 we have is actually a ______________________________________________________.
If we write each of the different combination options listed above as a set, we see that
Each combination of toppings is a _______________________________ of the five-topping set, so we are justcounting the ____________________________________ in a set with five elements which is ____________________.
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 ____________________________________.
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 _________________________________________“All, some, or none”
If a counting problem involves an “all, some, or none” situation, then the number of outcomes will always
be a __________________________________ (such as 2, 4, 8, 16, 32, 64, 128, 256 and so on).
This is because the situation involves a series of _________________________________ decisions, so theFundamental Counting Principle will have us _________________________________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.

15

ExerciseHomerina 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

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

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 nonumbers repeated.
How many different "combinations" are possible if he knows that the last number in the combination iseither 1 or 11?
A. 264
B. 1320
C. 220D. 288
E. 180Dependent decisions

If a Fundamental Counting Principle problem involves _____________________________________, and one decision
involves a special condition, the decision with the __________________________________ takes priority over
the others.
ExampleThe Egotists' Club has 6 members: A, B, C, D, E, and F. They are going to line up, from left to right, for agroup photo. After lining up in alphabetical order (ABCDEF), Mr. F complains that he is always lastwhenever they do things alphabetically, so they agree to line up in reverse order (FEDCBA) and takeanother 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 lineup of the six people. How many different photos must be taken?
A. 14
B. 720C. 823,543
D. None of these16

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 _________________________“n factorial”
If n is a positive integer, then ____________________________, denoted_________________________,
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 isa vowel?
A. 32
B. 256
C. 840D. 1344
E. None of theseAll, Some, or None
If a counting problem involves an “all, some, or none” situation, then the number of outcomes will always
be a ______________________________________________. Yes we already covered this. Pay attention.
This is because the situation involves a series of _________________________________________.
This also due to the fact that such a problem is asking for the number of ________________ in a particular set.

17

Part 1 Module 5 - Factorials, Permutations, and Combinations

We want to be able to recognize when a counting problem can be solved directly by using_________________________________________, instead of using the ___________________________________________.
If a counting question asks for the number of ways to arrange (put in order), then the number of outcomes is __________________
Example: Suppose we have a collection of five books.
In how many ways can the five books be arranged in a row?
Answer: The number of ways to arrange five objects in a row is ________________________________
Example #1
Select the situation where the number of outcomes is 5!
A. We can choose any combination (“all, some, or none”) of pizza toppings from a list of five toppings.
B. We will take a list of five job applicants and rank them from “best” to “worst.”
C. We will form a five-digit number using digits chosen from this set: {2, 4, 5, 7, 9}
D. All of theseE. None of these
Example #2
The contestants in this year's Ironic Man Octathlon must compete in all of the following events: wolverine
shearing; tobacco spitting; manatee racing; squid wrestling; unicycle demolition derby; spaghetti
weaving; elephant tipping; cat herding.
The organizers must decide on the order in which the events will be scheduled. How many outcomes are
possible?
A. 40,320
B. 256
C. 30,240
D. None of these

Two special formulas

We are about to encounter two special formulas that can be used to quickly express the number ofoutcomes for certain kinds of counting problems.
These two formulas are called, respectively, the _________________________________________and the ________________________________________The Permutation Formula P(n,r)
Suppose that a counting problem involves selecting and arranging r distinct elements from a set of nelements.
We say that this is a permutation problem, and we say that the number of outcomes is “the number of
permutations of n things taken r at a time”, abbreviated P(n, r).

18

Example: a Permutation problem
Due to time constraints, the organizers of this year's Ironic Man Octathlon are going scale things back,and produce a pentathlon, instead. From the original list of eight events (listed previously) they will
select five events and then decide on the order in which the events will be scheduled.
How many outcomes are possible?

The Combination Formula C(n,r)
Suppose that a counting problem involves just selecting, but not arranging r distinct elements from a
set of n elements. We say that this is a combination problem, and we say that the number of outcomesis “the number of combinations of n things taken r at a time”, abbreviated C(n, r).

“Order doesn’t matter…”
We say that for a combination problem, “order doesn’t matter.”This means that an outcome is determined entirely by which elements are selected, not by the order inwhich the elements are selected or listed.
On the other hand, for a permutation problem, order is important.
That means that for a permutation problem, we care not only about which elements are selected, but also
about the order in which the elements are selected or arranged.
Example: a combination problem
We have following six coins in a jar: a penny, a nickel, a dime, a quarter, a half-dollar, and a silver dollar.
Two of the coins will be randomly selected and their values will be added.
For example, if we select the dime and the penny, the monetary sum is 11¢. If we select the quarter andthe silver dollar, the monetary sum is $1.25.
How many different monetary sums are possible?

Example #3
Select the counting problem in which the number of outcomes is P(7, 3).
A. Using letters from the set {a, b, c, d, e, f, g}, form a three-letter password with no repeatedletters.
B. Using letters from the set {a, b, c, d, e, f, g}, form a three-letter sequence which may haverepeated characters.
C. Using letters from the set {a, b, c, d, e, f, g}, form a three-letter subset.
D. All of these.
E. None of these.

19

Example #4
Select the counting problem in which the number of outcomes is C(5,3).
A. From a group of five waitresses, select three waitresses and tell them that they are fired.
B. From a group of five waitresses, select one waitress to bus tables, a second waitress to foldnapkins, and a third waitress to polish silverware.
C. From a group of five waitresses, assign a waitress to Table #1, a waitress to table #2 and a
waitress to table#3; the same waitress may get more than one assignment.
D. All of these.
E. None of these.

Guidelines
When a problem involves selecting individuals from a group:
1. If it is possible to select the same individual more than once, then it isn’t a P(n,r) problem and it
isn’t a C(n,r) problem. It is a FCP problem.
Otherwise:
2. If the individuals are being treated differently from one other (for instance, if they are being
given different jobs, titles or gifts), then order matters and it is a P(n,r) problem (unless one
selection involves a special condition, in which case it is FCP).
3. If the individuals are being treated the same as one another (for instance, if they are all getting
the same job, title or gift), then order doesn’t matter and it is a C(n,r) problem.

Example #5
A group of ten hobbits gets together to compare rings. Prior to the meeting, each hobbit shakes handswith each of the other hobbits. How many handshakes occur?
A. 10!
B. 100C. 90
D. 45
E. None of these

Example #6
Harpo, Groucho, Chico, Zeppo, Gummo, Karl, and Skid have won three tickets to the opera. They will
randomly choose three people from their group to attend the opera. How many outcomes are possible?
A. 21
B. 35
C. 210D. 343
E. None of these20

Example #7
Here is a similar problem in which ___________________________________________________________________________________________________________.
Harpo, Groucho, Chico, Zeppo, Gummo, Karl, and Skid have won three tickets to the opera. They will
randomly choose three people from their group to attend the opera.
One person gets to ride to the opera in a taxi, another gets to ride to the opera in the bed of a turnip truck,and the third person gets to ride in a rickshaw.
How many outcomes are possible?

Example #8
Select the counting problem where the number of outcomes is C(6,3). Each problem involves making
three selections from this group of six people:
Homer, Gomer, Homerina, Gomerina, Plato, Mrs. Plato
A. Select a president, vice-president, and treasurer. Nobody may hold more than one office.
B. Select a person to receive a pencil, select a person to receive a calculator, select a person to receive asheet of scratch paper. It is possible that the same person might be selected to receive more than one ofthese gifts.
C. Select three people to take the rhinoceros for a walk.
D. Select a president, a vice-president, and a treasurer. Nobody can hold more than one office, but Gomer,
who is bad at math, is not eligible to be treasurer.
E. None of these

Example #9
There are 8 hamsters in a recreational hamster league. They are going to schedule a round-robin
tournament (in which each hamster will race each of the other hamsters one time). How many races will
be held?
A. 256
B. 64
C. 56
D. 28
E. None of these

Example #10
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 isa vowel?
A. 32
B. 256
C. 840D. 1344
E. None of these21Part 1 Module 6 - More counting problems
EXERCISE #1
From The FUNDAMENTALIZER, Part 2
Mrs. Plato is going to order supper at a restaurant. She will choose items from each of the following menu
categories:
Category A: lettuce salad; cole slaw; clam chowder; potato salad; egg salad; vegetable soup; bean soup; macaroni salad.
Category B: lamb; grouper fillet; pork chops; prime rib; shrimp; lobster; roast beef; roast pork; fried chicken; baked
chicken; broiled salmon.
Category C: baked potato; French fries; hash browns; rice; sweet potato; steamed carrots; green beans; pilaf.

How many meal combinations are possible, assuming that Mrs. Plato will choose 3 items from Category A,
3 items from Category B, and 2 items from Category C, and no item will be selected more than once?
A. 595,056

B. 18,627,840

C. 258,720

D. 43,614,208

Exercise #2
From The FUNDAMENTALIZER, Part 2
Mr. Moneybags, while out for a stroll, encounters a group of ten children. He has in his pocket four shiny
new dimes and three shiny new nickels that he will give to selected children. In how many ways maythese coins be distributed among the children, assuming that no child will get more than one coin?
A. 25,200
B. 3,628,800
C. 4,200
D. 604,800

Exercise #3
There are nine waitresses and six busboys employed at the trendy new restaurant The House of
Hummus. From among each of these groups The International Brother/Sisterhood of Table Service
Workers will select a shop steward and a secretary.
How many outcomes are possible?
A. 51
B. 540C. 2160
D. 102
E. None of these22

Would we ever need to add instead of multiply?
In the examples we have looked at so far, we found various numbers, perhaps by using the permutation
formula or the combination formula, and then _______________________________________________
In some situations, however, we may want to _____________________________________________________, at the end ofa calculation.
The following example suggests why we might add, rather the multiply.
EXAMPLE
Suppose we ask, “How many of you are 18 years old?” and, by show of hands, we see that there are 25
people who are 18 years of age.
Next, suppose we ask, “How many of you are 19 years old” and, by show of hands, we see that there are
30 people who are 19 years of age.
Now we want to use those results to answer the question “How many are___________________________________?”
It would make no sense to say that the number of people who are 18 or 19 years old is 25x30 = 750.
If 25 people are 18 years old, and 30 people are 19 years old, then the number of people who are 18 or 19
years old is 25+30 = 55.
This suggests the following fact:
To find the number of outcomes in an “_____________________________” situation, find the number of of
options for each case, and ___________________________________.
More formally, if A, B are mutually exclusive conditions, then__________________________________________.

“OR” means “ADD”
Generally, in counting problems or probability problems,“AND” means _________________“OR” means ____________________
Exercise #3a
There are nine waitresses and six busboys employed at the trendy new restaurant The House of
Hummus. The International Brother/Sisterhood of Table Service Workers will either select a shop
steward and a secretary from among the waitresses, or they will select a shop steward and a secretaryfrom among the busboys. How many outcomes are possible?
A. 51
B. 540C. 2160
D. 102
E. None of these23

EXERCISE #4
A couple is expecting the birth of a baby. If the child is a girl, they will choose her first name and middle
name from this list of their favorite girl’s names: Betty, Beverly, Bernice, Bonita, Barbie.
If the child is a boy, they will choose his first name and middle name from this list of their favorite boy’s
names: Biff, Buzz, Barney, Bart, Buddy, Bert.
In either case, the child's first name will be different from the middle name.
How many two-part names are possible?
A. 50
B. 600
C. 61
D. 900Exercise #5
The mathematics department is going to hire a new instructor. They want to hire somebody who
possesses at least four of the following traits:
1. Honest 2. Trustworthy
3. Loyal 4. Gets along well with others
5. Good at math
6. Good handwriting
In how many ways is it possible to combine at least four of these traits?
A. 360
B. 15
C. 22
D. 48
E. None of these

Exercise #6
Tonight there are 8 bus boys and 7 dishwashers working at the trendy new restaurant Cap'n Krusto's
Crustacean Castle. Because it is a slow night the manager will select either 3 bus boys or 2 dishwashers
and send them home early. How many outcomes are possible?
A. 14112

B. 378

C. 77

D. 1176

E. None of these

Exercise #8
Among a certain group of 28 mules, 23 are stubborn, 19 are obstinate, and 16 are both stubborn andobstinate.
How many are stubborn or obstinate?
A. 26
B. 51
C. 10
D. None of thes

Exercise #9
In the Psychology Department there are 8 faculty members. 2 faculty members will be chosen to design
a new course offering and 3 other faculty members will be chosen to hang out in the faculty parking lot toprevent students from parking there. How many different outcomes are possible?
A. 560
B. 48
C. 240D. None of these.

24New Problem TypeIn the Psychology Department there are 8 faculty members.
They will either choose 2 faculty members to design a new course offering or choose 3 faculty members
to hang out in the faculty parking lot to prevent students from parking there. How many different
outcomes are possible?

25