6.1 Sets
A set is a collection of objects with a clear definition. We must always be able to tell what belongs to the set. The objects in the set are called elements.
Two ways to clearly define a set are :
1) Roster notation—the elements are listed within brackets
For example A={1,2,3,4,5,6,7,8,9,10} which can also be written A={1,2,3,…,10}.
2) Set builder notation—the elements are described by requirements they must fill.
Example: A above can be written as A={x| x is an integer between 1 and 10 inclusive}
Or as A={x| x is an integer and 1<x<10}
a
means a is an element of set A. a
means a is not an element of set A.
{1} is a singleton set. It has one element, the number 1. {2}, {b}, {A} are also singleton sets, even if A is a set with many elements.
For A as above, 1
A is true. {1}
A is also true because the set {1} is not in the list of
elements of A.
The empty set is the set with no elements denoted by zero with a line through it.
I will use the symbol 
in this text.
A
B means A is contained in B, A is a
subset of B. Every element of A is an element of B.
B
A means the same thing.
A
B means A is properly contained in B. A is contained in B and
B has at least one element not in A.
The number of subsets of an n-element set is
.
Why is this so? The only subset of the empty set is the
empty set. If A
={1}, the subsets of A are the empty
set and {1}. If B= {1,2} the subsets of B are , {1}, {2}, and {1,2}. How many subsets of a 3-element set
are there? If C={1,2,3}, the subsets are , {1}, {2}, {1,2} which are the subsets of B and {3}, {1,3},
{2,3}, and {1,2,3} which are each of the subsets of B with 3 added in. So the
number of subsets doubled. Each time we add a new element we get all the old
subsets and all these with the new element thrown in. So the number of subsets
doubles each time we add a new element.
Example: If A={1,2,3,4,5,6,7,8,9,10} and B={1,2,3,…}={x| x is a positive integer} then
AB and A B are both true. AA is always true.
We say A is a proper subset of B. A is not a proper subset of A.
The universal set, U, is the set of all elements under consideration.
Ex. A={x| x is a math 141 student at TAMU} B={x| x is an accounting major at TAMU}. A suitable universal set is U={x| x is a student at Tamu}.
A={x| xU, x is a math 141 student}
B={x| xU, x is an accounting major}
A
B={x| xA or xB} is the union of A and B. The or allows the possibility
that x is
in both A and B. A union B is the set of x in at least one of A and B.
Ex. A={1,3,5,7} B={1,2,3,4} then AB={1,2,3,4,5,7}. Notice 1 and 3 are included.
A
B={x| xA and xB} is the intersection of A and B. The intersection is the
set of
elements in both A and B.
Ex. For A and B as above AB={1,3}
are all true.
A and B are called disjoint if AB=
If C={4,6} and A is as above then A and C are disjoint.
A
={x| xU, xA} is the complement of A. U is the universal set.
Ex. U={x| x is a positive integer} A={x| x is an even positive integer}
A={x| x is an odd positive integer}
Ex. U={x| x is a letter of the English alphabet} A={a,b,c,d,e,f}
A={g,h,i,…,z}
DeMorgan’s Laws
If x is not in at
least one of A and B then x is not in A and x is not in B.
If x is not in both A and B then x is not in A or x is not in
B.
Describing with words:
“x
is in at least one of A,B, and C”
“x
is in all three of A, B and C”
“x
is in A only”
“x
is in exactly one of A,B and C”
Example:
U is the set of people in
H is the set of people in U who shop at HEB. K is the people in U who shop at Kroger and S is the people in U who shop at Sam’s.
Describe in terms of H, K, and S the set of people who:
shop
at Sam’s only. 
shop
in at least one of the three stores. 
shop
at all three stores. 
shop
at HEB or Sam’s but not Kroger. 
6.2 The number of elements in a finite set. We restrict our discussion to finite sets.
n(A) is the number of elements in A.
Ex. If A={a,b,c,d,e}
n(A)=5. n()=0.
Ex: A={1,3,5,7} B={2,3,4,5,6} n(A)=4 and n(B)=5
AB={1,2,3,4,5,6,7} AB={3,5}
7=5+4-2
If we count A we count 1,3,5and7. If we count B we count 2,3,4,5,and 6.
Now 3 and 5
have been counted twice. AB is counted twice so we have to subtract it once.
the
inclusion- exclusion formula for three sets.
Why is the triple intersection added?
The triple intersection is included in A, B, and C. It is added in 3 times when we count each of these sets. The triple intersection is also included in each double intersection. It is subtracted 3 times when we subtract the numbers for each of these sets. Now we haven’t counted it at all so we have to add it back.
Ex. A company makes apple, banana and cherry fruit spreads. A survey of 250 people finds 140 use apple, 125 use banana, 125 use cherry, 85 use both apple and banana, 80 use both banana and cherry and 75 use both apple and cherry. 50 use none. How many use all three?
250-50=200 use at least one of the three. Using the inclusion-exclusion formula we have
200=140+125+125-85-80-75+n(
so the number who use all three is 50.
Ex. This problem uses a different approach. 250 people were asked if they drink coffee tea or milk. 220 said they drink at least one of the three.
90 said they drink at least two of the three.
130 drink exactly one
50 drink only coffee
100 drink milk
120 drink tea
35 drink coffee and milk
45 drink only tea
Fill in each region of the Venn diagram. How many drink exactly two?
6.3 The Multiplication Principle
Perform a task with two steps. If there are m ways to do step 1 and n ways to do step 2, then there are mxn ways to do both steps. Remember we are doing both steps and each way of doing step 1 can be paired with each way of doing step 2.
Ex. An urn contains 3 balls colored red, blue and green. A coin has two sides, H and T. We draw a ball from the urn and then toss the coin. How many results are possible? 3x2=6
We can list the possible results as ordered pairs with color first and coin side second. They are (red,H), (blue,H), (green,H),
(red,T), (blue,T), (green,T)
Ex. There are 4 science course, 3 electives, and 5 social science courses. A student must choose one from each category. We could list the possible choices as ordered triples but we don’t want to-there would be 4x3x5=60 of them.
Ex. A
two sided coin is tossed n times. How many possible outcomes are there?
Write them down as ordered pairs for n=2 and as ordered triples for n=3.
Ex.
How many 3-letter sequences can be made from the 26 letters of the alphabet if
repetitions are allowed? 
Ex.
How many 3-letter sequences, repeats allowed, contain no a’s? 
How many 3-letter sequences,
repeats allowed, contain at least one a?
Ex.
How many license plates have 3 letters followed by 4 digits if the 1st
digit cannot be 0? 
The difference between adding and multiplying: Suppose we have two urns, A and B.
Urn A has 3 balls colored red, blue and green. Urn B has 5 balls numbered 1 through 5.
How many ways can we choose a ball from urn A and a ball from urn B? 15
How many ways can we choose one ball from either urn A or urn B? 8
6.4 Permutations and Combinations
Permutations: A permutation of a set A is an arrangement, or an ordered list, of the elements of A in which each element occurs exactly once. No repeats allowed. Order matters.
Ex. A={a,b,c} The permutations of A are abc, acb, bac, bca, cab, cba
Why are there six permutations of a 3-element set? We have 3 choices for the 1st letter. We cannot repeat this letter so there are only 2 choices for the 2nd letter. Then we have only one letter left for the 3rd letter. 3x2x1=6
How many permutations of an n-element set are there? We have n choices for the 1st, n-1 choices for the 2nd, n-2 choices for the 3rd and so on until we have only one choice for the last.
There are nx(n-1)x(n-2)…x2x1. This number is called n factorial and is written n!. It is on the calculator under MATH>>PRB. It is consistent to make 0! equal to 1.
Ex. How many different words can be made from the letters in {a, b, c, d, e} if no repeats are allowed? Here a word is any permutation of the letters. 5!=120
Sometimes we do not arrange all the n elements of a set but only r of them where r<n.
Ex. How many 3 letter words can be made from the 26 letters of the alphabet if no repeats are allowed? There are 26 choices for the 1st letter. We cannot repeat this letter so there are 25 choices for the 2nd letter and we cannot repeat either of these letters so there are 24 choices for the 3rd. 26x25x24 This is called P(26,3)=the number of permutations of 26 things taken 3 a time.
P(n,r)=n(n-1)(n-2)…(n-r+1)=n!/(n-r)!
Ex. P(7,3)=7x6x5=7!/4! On the calculator enter 7 Math>>PRB select nPr enter 3
Ex. How many ways can a secretary, treasurer, vice president and president be chosen from a committee of 10 people?
Think of assigning the positions as arranging the four people in order. This is P(10,4)=5040
Ex. How many distinct arrangements of the word banana are there?
Banana has six letters, 1-b, 3-a’s, and 2-n’s. If we could distinguish all the letters there would be 6! Permutaions. But since we can’t distinguish the 3! permutations of the a’s and the 2!=2 permutaions of the n’s, 6! counts each word 3!x2! times. There are 6!/(3!2!) distinguishable permutations.
Ex.
How many arrangements of
Combinations: A combination is a subset. How many ways can we choose r element subset from an n-element set, r<n. Order does not matter. No repeats.
Ex. How many 3-element subsets of the 26 letter alphabet are there?
Ex. There are 10 people on a committee. How many ways can we choose 4 of them to serve on a special project? Compare these examples to the permutations done previously.
How do we answer these questions? Let’s start with the 3-element subset of the 26 letter alphabet. We know there are P(26,3)=26!/23! different ways to arrange three out of 26 letters.
How many times does this count
the combination {a,b,c}? {a,b,c} has been counted 3! times, once for each different ordering. So also {r,b,l} has been counted 3! times . Every 3-element subset has been counted 3! times, once for each arrangement of its letters. The number
we want is P(26,3)/3!=
=2600
C(n,r)=
the number of combinations of n things taken r at a time=the
number of
r-element subsets of an n-element set. This is under MATH>>PRB select nCr on the calculator
Ex. The number of ways to choose a subcommittee of 4 from a committee of 10 is C(10,4)=210
Here are some examples of permutations and combinations:
Permutation Combination
Form a line of 5 people from a room of 50. P(50,5) Choose a committee of 5 people out of 50 C(50,5)
Paint 4 different objects with any of 10 different colors,
no repeats. P(10,4) Choose 4 of 10 colors. C(10,4)
Choose 3 out of 15 building sites for a 1,500 sq ft home, Choose 3 out of 15 lots for 3 new homes. C(15,3)
2.000 sq ft home and a 3,000 sq ft home. Decide which
home goes on which lot. P(15,3)
Examples:
- A landscaper has 15 species of flowers in 3 colors. There are 6 blue species, 5 white species, and 4 gold species. How many ways can they be arranged if like colors must be together? A) Choose the color arrangement. 3! ways
B) Arrange the species in each color, 6!, 5!, 4!
C) Apply the multiplication principle 3!6!5!4!=12441600
- A crate of oranges has 47 good oranges and 3 bad ones. How many ways can you select 7 oranges so that 5 are good and 2 are bad? Select 5 good ones in any of C(47,5)ways and select 2 bad ones in any of C(3,2) ways. Use the multiplication principle. C(47,5)C(3,2)
- How many ways can you arrange 10 boys and 6 girls so that no two girls are next to each other? Arrange the 10 boys in any of 10! ways. The girls have to stand in the 11 spaces left by the boys. How many ways can we assign 6 girls to any of 11 spaces? P(11,6). Now apply the multiplication principle. 10!P(11,6).