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.