Main Page | Everything for Finite Math | Everything for Applied Calc | Everything | Topic Summaries | On Line Tutorials | On Line Utilities | |||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
|
||||||||||
![]() |
Finite mathematics topic summary: sets and counting |
Sets and Elements
A set is a collection of items, referred to as the elements of the 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. |
Examples
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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. |
Examples
1. If we toss a coin and observe which side faces up, the set of outcomes can be written as
2. If we roll a die with faces numbered 1 through 6, the set of outcomes can be represented as
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
or simply
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
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 |
Example
The following Venn diagram illustrates the relationship among the three sets
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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).
![]() The intersection of A and B is the set of all elements that are common to A and B.
![]() 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. ![]() |
Examples
Let S be the set of all integers, and let
Then
We also have De Morgan's Laws, which follow from the definitions:
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!). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Cartesian Product
The Cartesian product of two sets, A and B, is the set of all ordered pairs (a, b) with a ![]() ![]() In Words |
Examples
1. If A = {a, b} and B = {1, 2, 3}, then 2. Take S = {H, T}. (H stands for Heads, T stands for Tails) 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
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 which we might also write as |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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
![]() ![]()
If S is a finite universal set and A is a subset of S, then
If A and B are finite sets, then
|
Examples
1. Let S be the set of all playing cards in a standard deck, and let
Then
2. Let
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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
B. Apply the following "Acid Test"
|
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)
Acid Test
Decision Algorithm 2 (Valid)
Acid Test
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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. |
Example
Look at Decision Algorithm 2 above. The number of outcomes of each step is as follows:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Addition Principle
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. |
Example
In this example, we combine the Multiplication and Addition Principles to calculate the number of possible 2-course meals from the following menu:
Decision Algorithm Step 1: Choose a soup: 2 choices
Alternative 2: Pork: 3 choices of side dish |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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
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
Note
|
Examples
Since 5 and 2 add up to 7, we have
Try the Pop-up Factorials, Permutations and Combinations Window for more examples. |