Permutations (Order Is Important)

 

In how many different ways can we arrange the elements of a set S? If S has n elements, then there are n choices for the first element. For each of these choices there are n - 1 choices for the second element. Continuing in this way, we obtain

 

n! = n× (n - 1) . . . 2 × 1

 

different arrangements of n elements. Any arrangement of n distinct objects is called a permutation of the objects. We'll write down the rule for future use:

 

Permutations

 

There are n! permutations of an n-element set                                                           (2.1)

 

For example, if S = {a, b, c}, then the six possible permutations of S, written as strings, are listed as follows:

 

abc, acb, bac, bca, cab, cba.

 

Now suppose we want to count the number of permutations of r elements chosen from an n-element set, where 1 ≤ r ≤ n. There are n choices for the first element. For each of these choices there are n - 1 choices for the second element. We continue this process r times to obtain the answer,

n (n - 1) . . . (n - r + 1).

 

This number is denoted by the symbol P(n, r) and is read "the number of permutations of n objects taken r at a time." We should emphasize here that we are counting r distinct objects. So we have the formula

 

                                              P(n,r) = n (n - 1) . . . (n - r + 1)                                   (2.2)

 

which can also be written,

 

                                                     .                                                   (2.3)

 

Notice that P(n,1) = n and P(n,n) = n!. If S = {a,b,c,d}, then there are 12 permutations of two elements from S, given by the formula .

The permutations are listed as follows:

 

ab, ba, ac, ca, ad, da, be, cb, bd, db, cd, dc.

 

Permutations can be thought of as arrangements of objects selected from a set without replacement. In other words, we can't pick an element from the set more than once. If we can pick an element more than once, then the objects are said to be selected with replacement. In this case the number of arrangements of r objects from an n-element set is just nr. We can state this idea in terms of bags as follows: The number of distinct permutations of r objects taken from a bag containing n distinct objects, each occurring r times, is nr. For example, consider the bag B = {a, a, b, b, c, c}. Then the number of distinct permutations of 2 objects chosen from B is 32, and they can be listed as follows:

 

aa, bb, cc, ab, ac, ba, ca, bc, cb.

 

Let's look now at permutations of all the elements in a bag. For example, suppose we have the bag B = {a, a, b, b b} . We can write down the distinct permutations of  B as follows:

 

aabbb, ababb, abbab, abbba, baabb, babab, babba, bbaab, bbaba, bbbaa.

 

There are 10 strings. Let's see how to compute the number 10 from the information we have about the bag B. One way to proceed is to place subscripts on the elements in the bag, obtaining the five distinct elements a1, a2, b1,  b2, b3.

Then we get 5! = 120 permutations of the five distinct elements. Now we remove all the subscripts on the elements, and we find that there are many redundant strings among the original 120 strings.

For example, suppose we remove the subscripts from the two strings,

 

alblb2a2b3 and a2blb3alb2.

 

Then we obtain two occurrences of the string abbab. If we wrote them all down, we would find 12 strings, all of which reduce to the string abbab when subscripts are removed. This is because there are 2! permutations of the letters a1 and a2, and there are 3! permutations of the letters b1, b2 and b3. So there are 2!3! = 12 distinct ways to write the string abbab when we use subscripts. Of course, the number is the same for any string of two a's and three b's. Therefore the number of distinct strings of two a's and three b's is found by dividing the total number of subscripted strings by 2!3! to obtain  

This argument generalizes to obtain the following result about permutations that can contain redundant elements.

 

Permutations of a Bag

 

Let B be an n-element bag with k distinct elements, where each of the numbers ml, . . . , mk denotes the number of occurrences of each element. Then the number of permutations of the n elements of  B is

                                                          .                                                         (2.4)

                                                                

Now let's look at a few examples to see how permutations (6.1)-(6.4) can be used to solve a variety of problems.

EXAMPLE 1. In how many ways can 20 people be arranged in a circle if we don't count a rotation of the circle as a different arrangement? There are 20! arrangements of 20 people in a line. We can form a circle by joining the two ends of a line. Since there are 20 distinct rotations of the same circle of people, it follows that there are 20!/20 = 19! distinct arrangements of 20 people in a circle. Another way to proceed is to put one person in a certain fixed position of the circle. Then fill in the remaining 19 people in all possible ways to get 19! arrangements.

EXAMPLE 2. How many distinct strings can be made by rearranging the letters of the word banana? One letter is repeated twice, one letter is repeated three times, and one letter stands by itself. So we can answer the question by finding the number of permutations of the bag of letters {b, a, n, a, n, a}.

Therefore (6.4) gives us the result

 

 

EXAMPLE 3. How many distinct strings of length 10 can be constructed from the digits 0 and 1 with the restriction that five characters must be 0 and five must be 1? The answer is

 

 

because we are looking for the number of permutations from a 10-element bag with five l's and five 0's.