Counting Methods
Related Topics:
Probability
Uncertainty is part of the process of making decisions and predicting outcomes. Uncertainty is addressed with the ideas and methods of probability theory. Since elementary probability requires an understanding of counting methods, we now turn to a discussion of counting objects in a systematic way before reviewing probability.
When a set of objects is small, it is easy to list the objects and count them one by one. When the set is too large to count that way, and when the objects are related in a patterned or systematic way, there are some useful techniques for counting the objects without actually listing them.
In these lessons, we will learn Sets and Lists, Venn Diagrams, Inclusion-Exclusion Principle, Multiplication Principle, Permutations and Fractorials and Combinations.
Sets and Lists
The term set has been used informally in this review to mean a collection of objects that have some property, whether it is the collection of all positive integers, all points in a circular region, or all students in a school that have studied French. The objects of a set are called members or elements. Some sets are finite, which means that their members can be completely counted. Finite sets can, in principle, have all of their members listed, using curly brackets, such as the set of even digits {0, 2, 4, 6, 8 }
Sets that are not finite are called infinite sets, such as the set of all integers. A set that has no members is called the empty set and is denoted by the symbol Ø. A set with one or more members is called nonempty. If A and B are sets and all of the members of A are also members of B, then A is a subset of B. When the elements of a set are given, repetitions are not counted as additional elements and the order of the elements does not matter.
A list is like a finite set, having members that can all be listed, but with two differences. In a list, the members are ordered; that is, rearranging the members of a list makes it a different list. Thus, the terms first element, second element, etc., make sense in a list. Also, elements can be repeated in a list and the repetitions matter.
Sets can be formed from other sets. If S and T are sets, then the intersection of S and T is the set of all elements that are in both S and T and is denoted by S ∩ T. The union of S and T is the set of all elements that are in S or T, or both, and is denoted by S ∪ T. If sets S and T have no elements in common, they are called disjoint or mutually exclusive.
A useful way to represent two or three sets and their possible intersections and unions is a Venn diagram. In a Venn diagram, sets are represented by circular regions that overlap if they have elements in common but do not overlap if they are disjoint. Sometimes the circular regions are drawn inside a rectangular region, which represents a universal set, of which all other sets involved are subsets.
Sets: Union and Intersection.
Venn Diagrams - An Introduction.
The inclusion-exclusion principle relates the numbers of elements in the union and intersection of two finite sets: The number of elements in the union of two sets equals the sum of their individual numbers of elements minus the number of elements in their intersection.
Let n(S) be the number of elements in a given set S.
The inclusion-exclusion principle states that n(A ∪ B) = n(A) + n(B) - n(A ∩ B)
Law of Inclusion-Exclusion - Counting elements in a set
A pizza place receives 85 orders one day, each of which is for pizza and/or wings. If 63 people ordered pizza, and 27 people ordered both pizza and wings, how many people ordered wings?
Multiplication Principle
Suppose there are two choices to be made sequentially and that the second choice is independent of the first choice. Suppose also that there are k different possibilities for the first choice and m different possibilities for the second choice. The multiplication principle states that under those conditions, there are km different possibilities for the pair of choices.
The multiplication principle applies in more complicated situations as well. If there are more than two independent choices to be made, then the number of different possible outcomes of all of the choices is the product of the numbers of possibilities for each choice.
Multiplication Principle - Counting Techniques.
A fundamental idea to count the number of ways that some event can happen.
- How many different combinations can be made for a briefcase that has a 3-dial lock with each dial having numbers 0-9 available?
- How many license plates can be made if the first three entries must be letters, followed by 3 numbers?
- Suppose you take a multiple choice exam that has 10 questions, each question has 5 answers. How many different ways could the exam be answered?
Multiplication Principle with conditions
a) How many license plates can be made if the first three entries must be letters, followed by 3 numbers?
b) No repeats
c) No consecutive repeats.
Permutations and Factorials
Suppose n objects are to be ordered from 1st to nth, and we want to count the number of ways the objects can be ordered. There are n choices for the first object, n - 1 choices for the second object, n - 2 choices for the third object, and so on, until there is only 1 choice for the nth object.
Thus, applying the multiplication principle, the number of ways to order the n objects is equal to the product
n(n -1)(n - 2) … (3)(2)(1)
Each order is called a permutation, and the product above is called the number of permutations of n objects.
Because products of the form n(n -1)(n - 2) … (3)(2)(1) ) occur frequently when counting objects, a special symbol n!, called n factorial, is used to denote this product.
For example,
1! = 1
2! = 2 × 1 = 2
3! = 3 × 2× 1 = 6
4! = 4 × 3 × 2 × 1 = 24
As a special definition, 0! = 1.
Note that n! = n(n - 1)! = n(n - 1)(n - 2)! = n(n - 1)(n - 2)(n - 3)! and so on.
Suppose that k objects will be selected from a set of n objects, where k ≤ n and the k objects will be placed in order from 1st to kth. Then there are n choices for the first object, n - 1 choices for the second object, n-2 choices for the third object, and so on, until there are n - k + 1 choices for the kth object. Thus, applying the multiplication principle, the number of ways to select and order k objects from a set of n objects is n(n - 1)(n - 2) … (n - k +1)
It is useful to note that n(n - 1)(n - 2) … (n - k +1) = n!/(n - k)!
This expression n!/(n - k)! represents the number of permutations of n objects taken k at a time, that is, the number of ways to select and order k objects out of n objects.
This video gives a mini-lesson on Factorials and Permutations.
Combinations
Suppose that k objects will be chosen from a set of n objects, where k ≤ n, but that the k objects will not be put in order. The number of ways in which this can be done is called the number of combinations of n objects taken k at a time and is given by the formula
Another way to refer to the number of combinations of n objects taken k at a time is n choose k.
Counting Using Combinations - Math Help.
A few numerical examples along with some word problems are shown where combinations are used to count the number of ways some event can occur.
- Suppose 10 horses run a race; you would like to know in how many ways 3 horses can finish in 1st, 2nd, 3rd in any order.
- On a test, a student must select 6 out of 10 questions. In how many ways can this be done?
Try the free Mathway calculator and
problem solver below to practice various math topics. Try the given examples, or type in your own
problem and check your answer with the step-by-step explanations.
We welcome your feedback, comments and questions about this site or page. Please submit your feedback or enquiries via our Feedback page.