SETS
1) Describe what a set is and
how sets are denoted.
2) Give examples of
collections that are sets.
3) Give examples of
collections that are not sets.
4) Describe the empty set, the associated symbols, and
give examples of sets that are empty.
5)
Describe subsets and give examples.
6) Define cardinality of a set, its
symbol, and give examples.
7)
Define power set and its cardinality.
8) Write the members of the power set
of the sets (i.e., list all possible subsets of):
a) {A, B} b) {A, B, C} c) {A, B, C, D} d) {A, B, C, D, E}
9) Fundamental
multiplication principle of mathematics
a) AN EXAMPLE:
Consider the sets E = {a, b, c} and F = {1, 2}. Write out all possible pairs of elements in
such a way that the first element is from set E and the second element is from
set F. Construct a tree diagram and a
matrix.
root
F
MATRIX 
E 














b) Statement
of the Principle (for
two successive events _{}, _{})
10) A person wants to purchase a
cellular phone and a calling plan.
Suppose that there are two choices of cellular phones (the Motorola and
the Nokia) and three choices of calling plans (one for $29.99 which allows 300
minutes of airtime per month, a second for $39.99 which allows 600 minutes of
airtime per month, and a third for $49.99 which allows 1000 minutes of airtime
per month). In how many different ways
can this person purchase a cellular phone and a calling plan? Show all possibilities using a matrix and
using a tree diagram.
11) A game consists of tossing a coin and then rolling
a die. How many different outcomes are
possible? Show all possible outcomes
using a matrix and a tree diagram.
SOLUTION: Coin: {Heads, Tails}. Cardinality = 2
Die: {1, 2, 3, 4, 5, 6}. Cardinality = 6
Total = (2)(6) = 12
possible outcomes.
a) MATRIX DIE OUTCOMES
COIN 
1 
2 
3 
4 
5 
6 
Heads (H) 
(H, 1) 
(H, 2) 
(H, 3) 
(H, 4) 
(H, 5) 
(H, 6) 
Tails (T) 
(T, 1) 
(T, 2) 
(T, 3) 
(T, 4) 
(T, 5) 
(T, 6) 
b)
POSSIBLE
OUTCOMES
1 (H,
1)
2 (H,
2)
3 (H,
3)
Heads
4 (H, 4)
5 (H,
5)
6 (H,
6)
1 (T,
1)
2 (T,
2)
3 (T,
3)
Tails 4 (T,
4)
5 (T,
5)
6 (T,
6)
In both cases, we can view the 12 possible
outcomes.
12) A particular code consists of two digits, each
from the set {0,
1, 2, 3, 4, 5, 6, 7, 8, 9}. How many
different twodigit codes are possible?
13)
State the general multiplication principle.
14) At a particular restaurant,
customers can order a meal consisting of one choice of {steak, chicken, fish},
plus one choice of {baked potato, mashed potatoes}, plus one choice of {water,
soda, juice}. In how many different ways
can a customer order a meal?
SOLUTION
(3)(2)(3) = 18 different ways.
POSSIBLE MEALS
Water (Steak, Baked Potato, Water)
Baked Potato
Soda (Steak, Baked Potato,
Soda)
Juice
(Steak, Baked Potato, Juice)
Steak
Water (Steak, Mashed Potatoes, Water)
Mashed Potatoes
Soda (Steak, Mashed
Potatoes, Soda)
Juice
(Steak, Mashed Potatoes, Juice)
Water (Chicken, Baked Potato, Water)
Baked Potato
Soda (Chicken, Baked Potato,
Soda)
Juice
(Chicken, Baked Potato, Juice)
Chicken
Water (Chicken, Mashed Potatoes, Water)
Mashed Potatoes
Soda (Chicken, Mashed
Potatoes, Soda)
Juice
(Chicken, Mashed Potatoes, Juice)
Water (Fish, Baked Potato, Water)
Baked Potato Soda
(Fish, Baked Potato, Soda)
Juice
(Fish, Baked Potato, Juice)
Fish
Water (Fish, Mashed Potatoes, Water)
Mashed Potatoes
Soda (Fish, Mashed Potatoes,
Soda)
Juice
(Fish, Mashed Potatoes, Juice)
15) A certain model of vehicle is
available in twelve different colors, four different styles {hatchback, sedan,
SUV, or station wagon}, {manual or automatic transmission}, and {twodoor or
fourdoor}. How many different possible
choices of this vehicle are there?
16) A pizza can be ordered with four
choices of size {small, medium, large, superlarge}, four choices of crust
{thin, thick, crispy, regular}, and ten choices of toppings {extra cheese,
beef, chicken, ham, bacon, sausage, pepperoni, mushrooms, onions, green
peppers}. How many different onetopping
pizzas can be ordered?
17) A restaurant offers five
appetizers, six main courses, seven beverages, four desserts. If exactly one item is selected from each
group, in how many ways can a person order a meal?
SOLUTION
{appetizer}{main course}{beverage}{dessert} = (5)(6)(7)(4) = 840 different ways
18) Five candidates must be assigned to the positions
of president, vicepresident, treasurer, secretary, and receptionist of a club,
with one candidate assigned to exactly one position and one position assigned
to exactly one candidate. In how many
different ways can the positions be filled?
19) Six horses compete in a horse race. If there are no ties and all six horses
finish the race, in how many different ways can the race end?
20) Define FACTORIAL NUMBERS. Examples.
0! = 1
1! = 1
2! = (2)(1) = 2
3! = (3)(2)(1) = 6
4! = (4)(3)(2)(1) = 24
5! = (5)(4)(3)(2)(1) = 120
6! = (6)(5)(4)(3)(2)(1) = 720
7! = (7)(6)(5)(4)(3)(2)(1) = 5040
8! = (8)(7)(6)(5)(4)(3)(2)(1) = 40,320
9! = (9)(8)(7)(6)(5)(4)(3)(2)(1) = 362,880
10! = (10)(9)(8)(7)(6)(5)(4)(3)(2)(1)
= 3,628,800
11! = (11)(10)(9)(8)(7)(6)(5)(4)(3)(2)(1) = 3,991,680
12! = (12)(11)(10)(9)(8)(7)(6)(5)(4)(3)(2)(1) =
47,900,160
21) Interpret factorial numbers using elements of
sets.
22) a) A voting system consists of
candidates, {A, B}. In how many ways can
voters rank these two candidates? List
all the possibilities.
b) A voting system consists of three candidates, A, B, C. In how many ways can voters rank these three
candidates? List all the possibilities.
c) A voting system consists of four candidates, {A, B, C, D}. In how many ways can voters rank these four
candidates? List all the possibilities.
23)
Define PERMUTATIONS of elements of a set.
24) How many permutations of candidates A,B,C,D are there?
List the possible permutations.
25) Suppose that three candidates {Amal,
Marie, Sy} are available to
fill in the positions of President, Vicepresident, and Secretary of a
particular club. If exactly one
candidate must be assigned to each position and exactly one position to each
candidate, list all possible permutations of the three candidates.
26) Assuming no ties, in how many
different ways can a swimming race with of eight contestants end?
27) In how many different ways can five
people lineup to get on a bus (one at a time)?
28) Define the number of permutations
of the n elements of a set taken k at a time.
29) Suppose that there are ten
candidates for three offices: President, Vicepresident, and Secretary with
exactly one person in each office and exactly one office for a person. In how many different ways can the three
offices be filled?
30) A particular kind of competition awards $200,000
to the first place, $100,000 to the second place, and $50,000 to the third
place. If there are twelve competitors,
in how many different ways can the three prizes be awarded?
31) Evaluate:
a) _{} b) _{} c) _{} d) _{}
32) In how many ways can the eight
members of a committee select a chairman and a vicechairman?
33) Define COMBINATIONS.
34) a) Compute
the number of combinations of all the n
elements of a finite set.
b)
Compute the number of combinations of all n
elements of a finite set taken k at a
time (k Ł n).
35) How many different subsets of two elements can be
formed from {A, B, C, D}? List the 2element subsets.
36) How many different 3element subsets can be formed
from the set {A, B, C, D, E}? List the
3element subsets.
37)
Define DUALITY :
_{}
38) How many 3member committees can be
formed from a group of 10 individuals?
39) At a local hospital, there are
seven open nursing jobs. If 30 registered nurses apply for the jobs, in how
many ways can 7 nurses be selected from the 30 applicants?
40) In the Florida Lotto game, in how
many ways can a player match three of the six winning numbers?
41) How many committees of four women
and two men can be formed from a group of 35 individuals of which ten are men
and the rest are women?
42) Consider a group of 8 Democrats, 6 Republicans,
and 5 Independents.
a) How many threemember committees can be formed if each party must be
represented?
b) How many sixmember committees can be formed if two members of each
party must be in the committee?
43)
a) An election uses sequential pairwise voting and
there are 4 candidates: A, B, C, D. How many different agendas are
possible?
b)
An election uses sequential pairwise voting and there
are 10 alternatives, how many different agendas are possible?
44)
a) In an election that uses the Condorcet’s method, we
must examine all possible oneonone contests between pairs of candidates. If there are three
candidates,
how many such contests are there?
b) If there are twelve candidates, how
many such contests are there?
45) A group of six girls and five boys
must sit in a straight row.
a) In how many ways can the eleven boys and girls sit in a straight row?
b) If the six girls must sit together, in how many ways can the eleven
boys and girls sit in a straight row?
c) If the six girls must sit together and the five boys must sit
together too, in how many ways can the eleven boys and girls sit in a straight
row?
EXERCISES
COUNTING
PRINCIPLES
[1]
Find the number of subsets of the set {A, B, C}
[2]
Find the number of subsets of the set {A, B, C, D, E}
[3]
Find the number of subsets of the set {A, B, C, D, E, F, G, H, I, J}
[4]
List all possible subsets of the set {A, B, C}
[5]
List all possible subsets of the set {A, B, C, D}
[6]
List all possible subsets of the set {A, B, C, D, E}
[7] A particular code consists of one
digit followed by one letter from the Alphabet.
How many different codes of this kind can be formed?
[8] A woman has 12 different skirts and
16 different blouses. How many different
outfits can she wear?
[9] A restaurant offers nine appetizers
and twelve main courses. In how many
ways can a customer order a meal consisting of one appetizer and one main
course?
[10] A man has 5 shirts, 4 ties, 6 pairs of pants, 8
pairs of socks, and 3 pairs of shoes.
Find the number of different outfits that he can form if an outfit
includes one item from each group of items.
[11] A woman has 5 blouses, 8 skirts, 20 pairs of
shoes, and 10 purses. If an outfit
includes exactly one item from each group of items, how many different outfits
can she wear?
[12] How many
fourdigit numbers can be formed from the set of ten digits {0, 1, 2, 3, 4, 5,
6, 7, 8, 9} if the first digit cannot be zero and digits cannot repeat.
[13] A bank security system requires
customers to choose a fivedigit PIN (personal identification number). If all digits must be different (no
repetitions allowed) and nonzero, how many different fivedigit PINs can be
formed?
[14] How many (threedigit) area codes
exist if the first digit cannot be zero or one, the second digit must be zero
or one, (no restriction on the third digit)?
[15] A truefalse exam consists of six
questions. If an unprepared student
takes this exam, in how many ways can the student answer the six questions?
[16] A multiplechoice exam consists of
six questions, each question having options a, b, c, d, with only one option
being correct. If an unprepared student
takes this exam, in how many ways can the student answer the six questions?
[17] Six performers are to present
their comedy acts on a weekend evening at a comedy club. In how many different ways can they schedule
their appearances?
[18] In how many different ways can
nine books be arranged in a shelf?
[19] Ten singers are to perform on a
weekend evening at a night club. How
many different ways are there to schedule their appearances?
[20] In how many different ways can a
police department arrange eight suspects in a police lineup if each lineup
contains all eight people?
[21] Four candidates are to be assigned to the positions
of President, Vicepresident, Treasurer, and Secretary. Each office must be assumed by exactly one
person and each person must be assigned to exactly one office. In how many different ways can this be done?
[22] There are three routes from
[23] How many different outfits consisting of a coat
and a hat can be chosen from six coats and four hats?
[24] How many different license plates consisting of
three letters followed by three digits are possible?
[25] The Spoiled & Rotten Restaurant offers 8
choices of entrees, five choices of salads, ten choices of beverages, and four
choices of desserts. How many different
meals can a customer order?
[26] a) In how many ways can six people be arranged
in a line to take a picture?
b) In how many ways can they be arranged if
three of the six insist on appearing
one next to the other?
c) In how many ways can they be arranged if two
of the six refuse to appear one
next to the other?
[27] In how many ways can five books be arranged on a
bookshelf?
[28] How many rearrangements of the letters L, S, A, B
are possible? List all possible rearrangements.
[29] Twelve participants enter an Olympic event. In how many ways can they be awarded the Gold
Medal to the first place, the Silver Medal to the second place, and the Bronze
Medal to the third place?
[30] In how many
ways can a 24member team select a captain and an assistant captain?
[31] A group of 12 investors wants to elect a
president, a vicepresident, a secretary, and a treasurer from the twelve
members. In how many ways can this be
done?
[32] In a particular state, one type of license plate
consists of three uppercase letters followed by three digits. (a) If
repetitions are allowed, how many license plates can be formed? (b) If
repetitions are not allowed, how many license plates can be formed?
[33] A restaurant offers four soups, twelve
entrees, nine beverages, and nine desserts.
In how many ways can a customer order a meal if three
of the desserts are pies and customers never order pies?
[34] A group of 12 investors wants to
form a needs a fourperson committee. How many fourperson
committees can be formed from the 12 members?
[35] A group of 12 people consists of five Republicans
and the rest are Democrats. A
fiveperson committee must be formed from these 12.
a)
How many fiveperson committees can be formed?
b) How
many of these committees consist of two Republicans?
c) How
many of these committees consist of at least two Republicans?
d) How
many of these committees consist of at most two Republicans?
[36] The Florida Lotto Game consists of choosing six
numbers in any order from the set {1, 2, 3, …,
53}. Any player who matches the six
winning numbers in any order wins the jackpot.
a)
How many different choices of six numbers exist?
b) In
how many ways can a player match three of the six winning numbers?
[37] A group of five girls and three boys must sit on
a straight row. In how many ways can
they sit if: A) no restrictions are imposed? B) the
three boys must sit together one next to the other? C) the
girls must sit together (one next to the other) and the boys too.
[38] A group of nine faculty members consists of 3
members from the English department, 4 from Business, and the rest from
Mathematics. A threemember committee
must be formed from the group of 9. Find
the number of threemember committees if:
a) no restrictions are imposed
b) each
department must have a representative
c) no restrictions are
imposed except that one member must be the chairperson, another member must be
the vicechair, and the third must be the notetaker.
[39] Six performers are to present their comedy acts on a weekend evening at a comedy club. How many different ways are there to schedule
their appearances?
[40] A pizza can be ordered with three choices of size
(small, medium, or large), four choices of crust (thin, thick, crispy, or
regular), and six choices of toppings (ground beef, sausage, pepperoni, bacon,
mushrooms, or onions). How many
onetopping pizzas can be ordered?
[41] A medical researcher needs 6 people to test the
effectiveness of an experiment drug. If
16 people have volunteered for the test, in how many ways can 6 people be
selected?
[42] Suppose you are taking a multiplechoice test
that has six questions. Each of the
questions has four answer options, with exactly one correct answer per
question. If you select exactly one of
these four choices for each question and leave nothing blank, in how many ways
can you answer the questions?
[43] If threedigit codes are formed from the set {0,
3, 4, 5, 6, 7},
a) how many codes can be formed if repetitions are allowed?
b) how many codes can be formed if no repetitions are
allowed?
c) how codes are threedigit odd numbers?
d) how many codes are threedigit numbers greater than 414?
[44] In how many
different ways can a police department arrange eight suspects in a police lineup
if each lineup contains all eight people?
[45] A club with
ten members is to choose four officers – president, vicepresident, secretary,
and treasurer. If each office is to be
held by exactly one person and no person can hold more than one office, in how
many ways can those offices be filled?
[46] In how many ways can a committee of five women
and four men be formed from a group of 18 people in which ten are women and the
rest are men?
[47] In a medical study patients are classified by
blood type and blood pressure. If the
blood types include {AB^{+}, AB^{}, A^{+}, A^{}, B^{+}, B^{}, O^{+}, O^{}} and the blood pressures could be {normal, low,
high}, find the number of ways in which a patient can be classified.
[48] a) How many distinct permutations can be made from the
letters of the word exam?
b) How many of these permutations end with the
letter x?
[49] a) A voter has to
rank 4 alternatives. How many different
preference list ballots can s/he make?
b)
If there are seven candidates in an election, how many different
preference list ballots can each voter make?
[50]
Simplify each of the following:
a)
8! b) _{} c)
_{} d) _{} e) _{}
[51]
How many permutations are there of the letters ABCDE?
[52] Evaluate:
a)_{ }b)_{ } c) _{ }d) _{}
[53] Prove that _{}
[54]
a) How many subsets does {a, b, c, d, e} have?
b) How many subsets of {a, b, c, d, e}
contain exactly three elements?
[55] a) How many
subsets does {a, b, c, d} have?
b) How many subsets of {a, b, c, d}
contain exactly two elements?
[56] How many subsets of size 4 does
a set with cardinality 10 have?
[57]
a) From a committee of 8 members, 3 must be chosen to
form a subcommittee. In how many
different ways can this be done?
b) From a committee of 8 members, 3
must be chosen for the positions of chair, vicechair, and recording
secretary. In how many different ways
can this be done?
[58]
a) If an election uses the sequential pairwise voting method and there are 4 alternatives: A, B,
C, and D, how many different agendas are possible?
b) If an election uses the sequential pairwise voting method and there are 6 alternatives: A, B,
C, D, E, and F, how many different agendas are possible?
c) If an election uses the sequential pairwise voting method and the alternatives are A, B, C, D, and
E, how many different agendas are possible?
[59]
a) In an election that uses the Condorcet’s method, we
must examine all possible oneonone contests between pairs of candidates. If there are four candidates, how many such
contests are there?
b) In an election that uses the
Condorcet’s method, we must examine all possible oneonone contests between
pairs of candidates. If there are six
candidates, how many such contests are there?
c) In an election that uses the
Condorcet’s method, we must examine all possible oneonone contests between
pairs of candidates. If the candidates
are A, B, C, D, and E, how many such contests are there?
ANSWERS
[1] _{} = 8
subsets; [2] _{} = 32
subsets; [3] _{} = 1024
subsets
[4] f, {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C}
[5] f, {A}, {B}, {C}, {D}, {A, B}, {A, C}, {A, D}, {B, C},
{B, D},
{C, D}, {A, B, C}, {A, B, D}, {A, C,
D}, {B, C, D}, {A, B, C, D}
[6] f, {A}, {B}, {C}, {D}, {E}, {A, B}, {A, C}, {A, D}, {A,
E}, {B, C},
{B, D}, {B, E}, {C, D}, {C, E}, {D, E},
{A, B, C}, {A, B, D},
{A, B, E}, {A, C, D}, {A, C, E}, {A, D,
E}, {B, C, D}, {B, C, E},
{B, D, E}, {C,
D, E}, {A, B, C, D}, {A, B, C, E}, {A, B, D, E},
{A, C, D, E},
{B, C, D, E}, {A, B, C, D, E,}
[7] (10)(26)
= 260 codes; [8] (12)(16) = 192
outfits; [9] (9)(12) = 108 meals
[10] (5)(4)(6)(8)(3) = 2880 outfits; [11]
(5)(8)(20)(10) = 8000 outfits;
[12] (9)(9)(8)(7) = 4536 4digit
numbers; [13] (9)(8)(7)(6)(5) = 15120
PINs;
[14] (8)(2)(10) = 160 area codes; [15] _{} = 64 ways; [16] _{} = 4096 ways
[17] 6! = 720 ways; [18] 9! = 362,880 ways; [19] 10! = 3,628,800 ways
[20] 8! = 40,320 ways; [21] 4! = 24 ways; [22] (3)(5) = 15 routes;
[23] (6)(4) = 24 outfits; [24]
(26)(26)(26)(10)(10)(10) = 17,576,000 plates
[25] (8)(5)(10)(4) = 1600 meals; [26]
a) 6! = 720 ways; b) (4!)(3!) = 144
ways; c) 6! – (5!)(2!) = 480 ways;
[27] 5!
= 120 ways;
[28] 4! = 24 ways; LSAB, LSBA, LASB,
ASBL, ABLS, ABSL, BLSA, BLAS, BSLA,
BSAL, BALS, BASL;
[29] _{} = 1320 ways; [30]
_{} = 552 ways; [31]
_{} = 11,880 ways;
[32] a)
(26)(26)(26)(10)(10)(10) = 17,576,000 plates;
b)
(26)(25)(24)(10)(9)(8) =
11,232,000 plates;
[33] (4)(12)(9)(6) = 2592 meals; [34]
_{} = 495 committees;
[35] a)
_{} = 792 fiveperson
committees; b) _{} = 350 committees;
c)
_{} = 596 committees;
d)
_{} = 546 committees;
[36]
a) _{} = 22,957,480
possibilities; b) _{} = 324,300 ways
[37]
a) 8! = 40,320 ways; b) (6!)(3!) = 4,320 ways; c)
(2)(5!)(3!) = 1440 ways
[38]
a) _{} = 84 ways; b)
(3)(4)(2) = 24 ways; c) _{} = 504 ways
[39]
6! = 720 ways; [40]
(3)(4)(6) = 72 onetopping pizzas;
[41] _{} = 8008
[42] _{} = 4096 ways; [43] a)
(6)(6)(6) = 216 codes; b) (6)(5)(4) = 120 codes;
c) (6)(6)(3) = 108; d)
(1)(5)(6) + (3)(6)(6) = 138;
[44] 8! = 40,320 ways;
[45] _{} = 5040 ways;
[46] _{} = 17,640 ways; [47] (8)(3) = 24 ways;
[48]
a) 4! = 24; b) (3)(2)(1)(1) = 6; [49]
a) 4! = 24 ballots; b) 7! = 5040 ballots
[50] a) 40,320; b) 43,680; c) 210; d) 24,024; e) 495; [51] 5! = 120 permutations
[52]
a) 5040; b)
210; c) 30;
d) 15; [53] _{}
[54] a) _{} = 32 subsets; b) _{} = 10; [55]
a) _{} = 16 subsets; b) _{} = 6
[56] _{} = 210 subsets of size
4; [57] a) _{} = 56 ways; b) _{} = 336 ways;
[58] a) 4! = 24 agendas; b)
6! = 720 agendas;
c) 5! = 120 agendas;
[59] a) _{} = 6 contests; b) _{} = 15 contests; c) _{} = 10 contests