|
Permutations and Combinations
Patrick McAtee, Tom Rice, and Jesse Whidden |
|||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
Permutations and CombinationsIntroduction to permutations, r-permutations, and r-combinationsIntroductionA car manufacturer is preparing to release a new model. In order for the manager at the production facility to calculate the possible ways that a car can be put together, he will need to use a branch of mathematics called combinatorics. Combinatorics uses mathematical operations known as permutations and combinations to calculate arrangements of things. In the case of the plant manager here, he might need to consider options like; engine, trim level, color, stereo, body type, or transmission just to name a few. Based on the possible options that a customer has when ordering a car, the manager can figure out how complicated his assembly line will be. He might also be able to tell marketing and development people where to limit those options to prevent chaos at the manufacturing site. Following are explanations of permutations and combinations as well as examples of how to use them. PermutationsPermutations are ordered arrangements of things. Because order is taken into consideration, permutations that contain the same elements but in different orders are considered to be distinct. When a permutation contains only some of the elements in a given set, it is called an r-permutation. For example, the permutations of the set {1, 2, 3} are {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}. This shows that there are six permutations of a set of three distinct objects. Notice that the elements of each permutation are in a different order. Some possible r-permutations from the set {1, 2, 3} are {2, 1}, {1, 2}, {3, 2}, and {1, 3}. Because each of these r-permutations contains only two elements, they are called two-permutations. There are several more that could be listed here, but the idea should be clear. The notation for a permutation of r things from a set of n objects is P(n, r). In order to determine how many permutations will result, one could write them all out. However, that would be very difficult, so instead a theorem can be utilized:
P(n, r) = n(n - 1)(n - 2)…(n - r + 1)
a) P(6, 3) Solutions: a) P(6, 3) = 6 * 5 * 4 = 120 NOTE: Answers ‘b’ and ‘c’ point out that each (n -1)-permutation of n
corresponds to a n-permutation of n. CombinationsCombinations are unordered sets of elements. A combination is taken from a set of distinct elements and can have any number of those elements in it. For this reason, combinations are also referred to as r-combinations. The only combination of the set {1, 2, 3} is {1, 2 ,3}. That is, {1, 2 ,3}, {1 ,3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3 ,2, 1} are all the same as far as combinations are concerned. They are the same because they all contain the same elements when order is not considered (which combinations do not). Some two-combinations of the set {1, 2, 3} are {2, 1}, {1, 2}, {3, 2}, and {1, 3}. The two-combinations {2, 1} and {1, 2} are the same since the elements within the sets are identical. Because order is not considered for combinations, calculating them is not as simple. Combinations ask the question "How many sets of size r can be made when picking from a set of size n?" Combinations also have a notation; C(n, r), and a theorem that helps to compute C(n, r).
C(n, r) = n!/[r!(n – r)]!
Solution: Assume that a combination is called for, not a permutation since the problem asks to select a set rather than arrange a set. This involves choosing four things from 12, so there are C(12, 4) = 495 ways to do so. Notice that the difference between a permutation and a combination is that a permutation recognizes different orderings as distinct. It is possible to have permutations and combinations with repetition. It will depend on the situation as to whether repetition among elements will be allowed. This topic is covered elsewhere in the tutorial. DerangementsIf a permutation is taken from the same a set of objects, and no object in the permutation is in the same place that it was in the original arrangment, it is known as a derangement of the original order. For instance, the permutation 36972 is a derangement of 23697. However, 73926 is NOT a derangment of 23967 because the 3 occupies the same spot.
Let Dn denote the number of derangements of n objects. For instance, D3 = 2, since the derangements of 123 are 231 and 312. We will evaluate Dn, for all positive integers n, using the principle of inclusion-exclusion.
Dn = n![1 - (1/1!) + (1/2!) - (1/3!) + ... + (-1)n(1/n!)] |