Permutations and Combinations

views updated May 14 2018

Permutations and Combinations

The study of permutations and combinations is at the root of several topics in mathematics such as number theory, algebra, geometry, probability, statistics, discrete mathematics, graph theory, and many other specialties.

Permutations

A permutation is an ordered arrangement of objects. For instance, the fraction is a permutation of two objects, whereas the combination to open a lock—23 L, 5 R, and 17 L—is a permutation of three objects. The ordered arrangements of objects likely dates all the way to the beginning of organizing and recording information.

Sometimes one is interested in knowing the number of permutations that are available from a collection of objects. Suppose a club has two candidates for president: Bob (B) and Janice (J); three candidates for secretary: Katy (K), Rob (R), and Harry (H); and three candidates for parliamentarian: Abe (A), Calvin (C), and Mary (M). In how many different ways could these candidates be elected to the three offices? One way to find out is to simply list the possible permutations: {(B,K,A), (B,K,C), (B,K,M), (B,R,A), (B,R,C), (B,R,M), (B,H,A), (B,H,C), (B,H,M), (J,K,A), (J,K,C), (J,K,M), (J,R,A), (J,R,C), (J,R,M), (J,H,A), (J,H,C), (J,H,M)}. Another way to find the number of permutations is to use the fundamental principle of counting. The fundamental principle of counting states that if an event A can occur in a ways, and is followed by an event B that can occur in b ways, then the event A followed by the event B can occur a × b ways. In our example, the office of president can be filled two ways, the office of secretary can be filled three ways, and the office of parliamentarian can be filled three ways. Therefore, the number of permutations, using the fundamental principle of counting, is 2 × 3 × 3, or 18. This method of finding the number of permutations can be extended to any finite number of events.

There are various permutation situations that are worthwhile exploring. For instance, a company wanting to use the nine nonzero digits for a source of five cell identification (ID) cards where the nonzero digits could be repeated would have 9⁵ possible ID cards, an exponential expression. A company of five employees wanting to assign each employee to an office has 5 × 4 × 3 × 2 × 1 × 5! possible choices, a factorial expression. One way to define factorial notation is: 0! = 1 and n ! = n (n − 1)! for n ≥ 1. A related situation would be the possibility of having 100 employees with five offices and 95 workstations. There would be 100 × 99 × 98 × 97 × 96 = possible choices for the five offices. This situation suggests a fundamental formula for determining the number of permutations of ordering r objects, without replacement, selected from n available objects, P (n, r ), where 0 ≤ r ≤ n, to be P (n, r ) = .

Combinations

A combination is an unordered arrangement of objects. For instance, there may be six ordered arrangements of three lengths, (3 cm, 4 cm, 5 cm) but since each arrangement determines the same unique trigon ("triangle"), any collection of the three lengths {3 cm, 4 cm, 5 cm} will represent the others. An example of a combination is thus {3 cm, 4 cm, 5 cm}. An extended example would be to consider 100 distinct points on a circle and to inquire as to number of unique trigons, a combination, which would be determined with the vertices . Initially one would know that there are permutations, but 3! permutations represent a combination, so there are × combinations. This situations suggests that the number of combinations with r objects, r -combinations, from a collection with n objects, C (n, r ), is, , and this formula suggests, . Notice that = . Another application of combinations might be to suppose that a local pizza parlor has seven different toppings available, besides cheese, which is on every pizza. The number of different combinations available, since putting toppings on a pizza is not an ordered collection, is C (7,0) + C (7,1) + C (7,2) + C (7,3) + C (7,4) + C (7,5) + C (7,6) + C (7,7). For convenience of notation, C (n, r ) is often expressed as . Thus, the fifth power of the sum of a and b, (a + b )⁵, would be expressed as .