← Previous Summary Next Summary → Review Exercises Textbook Lleveme a la Página Español
 Finite mathematics topic summary: sets and counting

Tools: Pop-up Factorials, Permutations and Combinations Window

Subtopics: Sets and Elements | Sets of Outcomes | Venn Diagrams | Set Operations: Union, Intersection, and Complement | Cartesian Product | Cardinality | Decision Algorithm | Multiplication Principle | Addition Principle | Permutations and Combinations

Sets and Elements

A set is a collection of items, referred to as the elements of the set.

x A means that x is an element of the set A.
x A means that x is not an element of the set A.
B = A means that A and B have the same elements.
B A means that B is a subset of A; every element of B is also an element of A.
B A means that B is a proper subset of A; in other words, B A, but BA.
is the empty set, the set containing no elements. It is a subset of every set.

A finite set is a set that has finitely many elements. An infinite set is a set that does not have finitely many elements.

Top of Page
Examples
b {a, b, c, d}
e {a, b, c, d}
{1, 2, 4, 5} = {2, 1, 5, 4}
{1, 2, 3} {1, 2, 3}
{1, 2, 3} {1, 2, 3, 4}
{1, 2, 3} {1, 2, 3, 4}
{1, 2, 3, ..., 1000} is a finite set.
{1, 2, 3, ...} is an infinite set.
 Any given set is a proper subset of itself is a subset of itself is not a subset of itself The empty set is a proper subset of every set is not a subset of itself is a proper subset of every set except itself

Top of Page

Sets of Outcomes

If we perform some kind of experiment that has one or more outcomes, we can think of the possible outcomes as being the elements of a set of outcomes associated with that experiment. (There is further discussion of sets of outcomes in the topic summary on probability.)

As the examples show, we can often represent the same set of outcomes in different ways.

Top of Page
Examples

1. If we toss a coin and observe which side faces up, the set of outcomes can be written as

or simply
S = {H, T}.

2. If we roll a die with faces numbered 1 through 6, the set of outcomes can be represented as

 S = { , , , , , },
or simply
S = {1, 2, 3, 4, 5, 6}.

3. If we roll two distinguishable dice (for instance, one red and one green) with faces numbered 1 through 6, the set of outcomes can be represented as

 S =

or simply

 S = (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)

4. If we roll two indistinguishable dice (that is, two identical dice) with faces numbered 1 through 6, the set of outcomes can be represented as

 S = (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6), (5, 5), (5, 6), (6, 6)

Top of Page

Venn Diagrams

Each diagram in the following figure represents the relation listed below it.

Neither A nor B a subset of the other

For a proper inclusion, the disk of B must be smaller than the disk of A. For simplicity we usually take the drawing representing B A to also represent B A.

Top of Page
Example

The following Venn diagram illustrates the relationship among the three sets

{March}, {March, April, May}, and {June, July, August}.

Top of Page
Set Operations: Union, Intersection, and Complement

The union of A and B is the set of all elements that are either in A or B (or both).

A B = {x | x A or x B}
We can picture the union in the Venn diagram shown below.

The intersection of A and B is the set of all elements that are common to A and B.

A B = {x | x A and x B}
We can picture the intersection in the Venn diagram shown below.

If A is a subset of S, then A' is the complement of A in S, the set of all elements of S not in A.

We can picture the complement in the Venn diagram shown below.

Top of Page
Examples

Let S be the set of all integers, and let

A = {2, 4, 6, 8}
B = {5, 6, 7, 8}
C = {positive even integers}
D = {1, 2, 3}.

Then

A B = {2, 4, 5, 6, 7, 8}
A B = {6, 8}
A C = A
C' = {0, 1, -1, -2, 3, -3, -4, 5, -5, . . .}
A (B C) = A.

 A D = { } A D = { } D A' = { } A (B D) = { }

We also have De Morgan's Laws, which follow from the definitions:

 De Morgan's Laws (A B)' = A' B' (A B)' = A' B'

Press here and scroll down to the discussion after Example 7 to see the counterparts in propositional logic (and visit the entire logic site while you're at it!).

Top of Page
Cartesian Product

The Cartesian product of two sets, A and B, is the set of all ordered pairs (a, b) with a A and b B.

A × B = { (a, b) | a A and b B }.

In Words

A×B is the set of all ordered pairs whose first component is in A and whose second component is in B.

Top of Page
Examples

1. If A = {a, b} and B = {1, 2, 3}, then

A × B = { (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3) }.

2. Take S = {H, T}.       (H stands for Heads, T stands for Tails)

S × S = { (H,H), (H,T), (T,H), T,T) }.

In other words, if S is the set of outcomes of tossing a coin once, then S×S is the set of outcomes of tossing a coin twice (or flipping a pair of distinguishable coins once).

3. S = {1, 2, 3, 4, 5, 6}    The set of outcomes of rolling a die

S × S =
 (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)

In other words, if S is the set of outcomes of a rolling a die once, then S×S is the set of outcomes of rolling a die twice (or rolling a pair of distinguishable dice once).

4. If A = {Red, Yellow} and B = {Mustang, Firebird} then

A×B = { (Red, Mustang), (Red, Firebird), (Yellow, Mustang), (Yellow, Firebird)},

which we might also write as

A×B = {Red Mustang, Red Firebird, Yellow Mustang, Yellow Firebird}.

Top of Page
Cardinality

If A is a finite set, then n(A), the number of elements A contains, is called the cardinality of A.

If A and B are finite sets, then

n(A B) = n(A) + n(B) - n(A B).
In particular, if A and B are disjoint (that is, A B = ), then
n(A B) = n(A) + n(B).

If S is a finite universal set and A is a subset of S, then

n(A') = n(S) - n(A) and n(A) = n(S) - n(A').

If A and B are finite sets, then

n(A×B) = n(A).n(B)

Top of Page
Examples

1. Let S be the set of all playing cards in a standard deck, and let

 D = set of diamonds;   n(D) = 13 T = set of tens;   n(T) = 4 H = set of hearts   n(H) = 13.

Then

 n(D H) = n(D) + n(H) Since D H = Ø = 13 +13 = 26 n(D T) = n(D) + n(T) - n(D T) = 13+4-1 = 16 n(D') = n(S) -n(D) = 52-13 = 39.

2. Let

 T = set of suites = {Spades, Hearts, Diamonds, Clubs} D = set of denominations = {2, 3, 4, 5, 6, 7, 8, 9, J, Q, K, A}
Then n(T×D) = 4×13 = 52, accounting for all the cards in a standard deck.

Top of Page
Decision Algorithm

A decision algorithm is a procedure with definite rules or instructions for what to do at every step.

We can use decision algorithms to help us count the number of possible elements in any set as follows:

A. Formulate a Decision Algorithm
If you are asked how many possible elements there are, pretend that you are constructing such an element, and come up with a step-by-step procedure -- that is, a decision algorithm -- for doing this. List the steps you would take, showing the number of choices for each step.

B. Apply the following "Acid Test"
Ask yourself the following question: "Suppose that I went through the algorithm twice, but the second time made a different choice at one or more of the steps. Would I then get a different outcome?" If the answer is "yes," then your decision algorithm is a valid one. If your algorithm is not valid, you need to come up with another algorithm.

Top of Page
Example

Here are two decision algorithms to calculate the number of different five-letter strings containing two "s"s, one "i," one "e," and one "d." The first one is not valid -- it fails the "acid test", and the second one is valid.

Decision Algorithm 1 (Not Valid)
Pretend you were constructing such a string by placing the five letters in five slots one-at-a-time:
Possible Outcome
1. Place the first "s."
(5 open slots to choose from)
 s
2. Place the second "s."
(4 remaining open slots to choose from)
 s s
3. Place the "i."
(3 remaining open slots to choose from)
 s i s
4. Place the "e."
(2 remaining open slots to choose from)
 s i e s
5. Place the "d."
(1 remaining open slot to choose from)
 s i d e s

Acid Test
You can obtain the same string "sides" by reversing the choices in steps 1 and 2. Therefore, the acid test fails for this procedure.

Decision Algorithm 2 (Valid)
Pretend you were constructing such a string by assigning groups of slots to the four different letters, starting with the letters that appear once (to make it easier);
Possible Outcome
1. Assign a slot for the "i."
(5 open slots to choose from)
 i
2. Assign a slot for the "e."
(4 remaining open slots to choose from)
 e i
3. Assign a slot for the "d."
(3 remaining open slots to choose from)
 e d i
4. Assign a pair of slots for the "s"s.
(1 remaining pair of slots to choose from)
 e d s s i

Acid Test
Making different choices in any of the steps will result in a different string. Therefore, the acid test passes for this procedure.

Top of Page
Multiplication Principle

If a decision algorithm requires several steps, with Step 1 having n1 outcomes, Step 2 having n2 outcomes, . . . , Step r having nr outcomes, then the number of outcomes of the algorithm is n1 × n2× . . . × nr.

Top of Page
Example

Look at Decision Algorithm 2 above. The number of outcomes of each step is as follows:

Step 1:   5 possible outcomes
Step 2:   4 possible outcomes
Step 3:   3 possible outcomes
Step 4:   1 possible outcome
Therefore, the total number of outcomes is
5×4×3×1 = 60. In other words, there are a total of 60 possible five-letter strings containing two "s"s, one "i," one "e," and one "d."

Top of Page

If a decision algorithm requires a choice among several different alternatives, then the total number of outcomes is obtained by adding the number of outcomes of each alternative.

Top of Page
Example

In this example, we combine the Multiplication and Addition Principles to calculate the number of possible 2-course meals from the following menu:

 Menu Soups Du Joir Creme de la Creme Creme of Tomato Entree Roast Beef with Potatoes or Brussels Sprouts Loin of Pork with Apple, Mango, or Papaya Have a Nice Day

Decision Algorithm

Step 1: Choose a soup: 2 choices
Step 2: Choose an entree:

Alternative 1: Beef: 2 choices of side dish
Alternative 2: Pork: 3 choices of side dish
The Addition Principle gives a total of 2+3 = 5 choices for Step 2 The Multiplication Principle now gives 2×5 = 10 choices for the meal.

Top of Page
Permutations and Combinations

A permutation of n items taken r at a time is an ordered list of r items chosen from a set of n items. The number of permutations of n items taken r at a time is given by

P(n, r)=n × (n-1) × (n-2) × . . . × (n-r+1)
= n!(n-r)!
.
Here,
n! = 1×2×3×...×(n-1)× n

A combination of n items taken r at a time is an unordered set of r items chosen from n. The number of combinations of n items taken r at a time is

C(n, r)= P(n, r)r!
= n!r! (n-r)!
.
= n×(n-1)×...×(n-r+1)r×(r-1) ×...×2×1
.

Note

 0! = 1 Zero factorial equals 1.
 It follows that C(n, 0) = n!0! n! = n!n! = 1
 If a and b add up to n, then     C(n ,a) = C(n, b) See the examples.

Top of Page
Examples
 P(7, 3) = 7×6×5 = 210
C(7, 3)= 7×6 ×53×2×1
=35.

Since 5 and 2 add up to 7, we have

C(7, 5) = C(7, 2) = 7×62×1
=21.

 P(4, 1) = P(4, 4) = C(4, 2) = C(4, 0) = C(4, 4) = C(100, 98) =

Try the Pop-up Factorials, Permutations and Combinations Window for more examples.

Top of Page
Last Updated: August 2007