Permutations and Combinations
A permutation is an ordered arrangement of every or some elements of a set of objects. Order is important in a permutation; therefore, permutations with the same objects in a different order are considered distinct arrangements. Some of the objects in the set, as well in a permutation, may be indistinguishable from one another.
A permutation of n distinct objects taken r at a time is a subset, with r elements, of the n distinct objects. The number of these subsets, denoted by n Pr , is equal to
EX. Given the letters A, B, C, D, E, F and G, there are
arrangements of these 7 letter taken 4 at a time.
If all n distinct elements of a set are to be arranged, then each arrangement is a permutation of n distinct objects taken n at a time. The number of such permutations is
Therefore, the number of permutations of n distinct objects is n!.
EX. There are 3! = 6 ways of using all three digits 1, 2 and 3 in a numeral. Namely, these are 123, 132, 213, 231, 312, and 321.
Circular permutations are ordered arrangements of objects in a circle. While order is still considered, a circular permutation is not considered to be distinct from another unless at least one object is preceded or succeeded by a different object in both permutations. In the set of objects, one object can be fixed, and the other objects can be arranged in different permutations. Thus, the number of permutations of n distinct objects that are arranged in a circle is (n-1) !.
EX. There are (6 - 1)! = 5! = 120 ways to seat 6 persons at a circular dinner table.
If there are identical or indistinguishable objects in the set, then the number of possible permutations in the set will be less than the number of permutations with distinct objects. This is true because permutations that are exactly alike, except that the identical objects have changed positions (e.g. an object switches position with an identical object), are considered to be the same arrangement.
The number of distinct permutations of n objects, of which n1 are of one kind, n2 are of a second kind, ......, nk are of a kth kind, is given by
where n1 + n2 + ..... + nk = n
EX. The word TENNESSEE has 4 E's, 2 N's, 2 S's and 1 T. The number of 9-letter permutations that can be created from these set of letters is
A partition of n objects into r cells is a division of the n objects into r subsets, such that the intersection of every possible pair of the r subsets is the null space, and the union of all the r subsets is the set of n objects. In this case, the order of the objects within each subset is not important. The number of ways to partition n objects into r cells, with n1 elements in the first call, n2 elements in the second cell, ......, nr elements in the rth cell, is
where n1 + n2 + ..... + nr = n
EX. A deck of cards contains 13 clubs, 13 diamonds, 13 hearts and 13 spades, with 52 cards in all. In a game of bridge, 13 cards are dealt to each of 4 persons. The number of ways to deal 52 cards evenly to 4 bridge players is
Indeed, card games are really games of chance (and luck too)!
A combination of n distinct objects taken r at a time is a subset of the n objects with r elements. A combination essentially creates a partition of the n r objects in the first cell and (n - r) objects in the second cell. Therefore, the number of combinations of n distinct objects taken r at a time is objects into 2 cells, with
EX. In the game of bridge, each of 4 players is dealt 13 cards. The number of 13-card hands that can be dealt from a 52-card deck is
Note that unlike a permutation, a combination does not take order into account; two permutations that have the exact same elements are considered the same combination. For each combination of r objects, there are r! ways of arranging the objects in different orders. In fact,
This equality states that the number of permutation of n distinct objects taken r at a time is equal to the number of combinations of n distinct objects taken r at a time multiplied by the number of permutations of r objects (taken r at a time).
