Permutations
Return to Topics page
Permutations are different ways to arrange some group of things.
The key concept is that the order of the things
in these arrangements is important.
If we start with three things, A, B, and C then we can arrange them
in any of the following ways: ABC, ACB, BAC, BCA, CAB, or CBA.
These are all permutations of the letters A, B, and C.
There are 6 permutations of the three things.
Another example would be to start with four things, say,
cat, dog, eel, and fox, and ask for the permutations of these
four things taken two at a time.
That is, find all the different arrangements of two things
where the two things are taken from the list of the
four things: cat, dog, eel, and fox. This will be
cat dog,
cat eel,
cat fox,
dog cat,
dog eel,
dog fox,
eel cat,
eel dog,
eel fox,
fox cat,
fox dog, and
fox eel.
There are 12 permutations of four things taken two at a time.
Clearly there are two related but different tasks
here. One is to be able to construct the different permutations and the other is
to predict the number of permutations that we will find.
R can help us with both of these.
Unfortunately, that help will take a little bit of extra effort.
This next section presents the "permutations" function. Although it is nice to see it,
this class does not require you to use it. For this class we will
get a smaller, easier to use function, in fact we will get two of them,
to mimic the function available on the TI83/84 calculators. Those functions are presented
later on this page.

Bill Venables, and later Gregory R. Warnes, developed and refined
a special function that constructs permutations. That function
is not part of the base R installation. Instead, that function is
provided in a package that is called "gtools". In order for us to use that
function we must do two things. First we need to actually get the package
and second we need to load it into our R session.
Fortunately the commands to do both of these are quite short.
They are
install.packages("gtools")
library(gtools)
Once we have performed those two statements within our session we will be able to use the
permutations() function. Figure 1 shows the console screen
that reflects doing those two commands.
Figure 1
Following the installation shown in Figure 1 we can give the command
permutations(3, 3, letters[1:3])
which is a call to the
permutations() function, telling it that it should use
the 3 values in the third argument and to use them 3 at a time
to form all of the possible permutations that it can. The third argument,
letters[1:3] provides the letters "a", "b", and "c" for permutations()
to use as the values.
Figure 2 shows the result of that command.
Figure 2
It is always nice to get a confirmation like that. We can try
to confirm the "cat dog eel fox" challenge from earlier.
The command permutations(4, 2, c("cat","dog","eel","fox"))
should do it.
Figure 3
We can make that challenge a bit more difficult if we ask for
all the permutations of the 4 things taken 3 at a time
by using the command permutations(4, 3, c("cat","dog","eel","fox"))
as shown in Figure 4.
Figure 4
As a byproduct of having R construct the various permutations
we also discover the number of permutations. After all, it really
does not matter what values we are using the number of permutations of
3 things taken 3 at a time is 6 (as seen in Figure 2),
the number of permutations of 4 things taken 2 at a time is 12
(as seen in Figure 3), and the number of permutations of
4 things taken 3 at a time is 24 (as seen in Figure 4).
Remember that we get the output that we saw in those figures
because we just use the function permutations() as a statement.
We did not assign the results of the function call to any variable.
We will change that behavior with the command
t<permutations(3,3,c("M","A","T","H","1","6","0"))
shown in Figure 5.
Figure 5
In Figure 5 the result of the permutations() function
is stored in the variable t; the result is not displayed in
the console.
Because the work shown above was done in RStudio, we
can find the variable t in the Environment pane.
There we see the "dimensions" of t as well as the first few values
stored in that variable. This is shown in Figure 6.
Figure 6
The dimensions [1:6, 1:3] specify that t
is structured as 6 rows (numbered 1 through 6) and 3 columns (numbered 1 through 3).
This is exactly what we expect since there are 6 permutations each holding
3 values.
We could issue the command t to have R display the contents of
t. That is done in Figure 7.
Figure 7
The display in Figure 7 shows our 6 rows and 3 columns.
Each row contains a different permutation.
What might be surprising is the values from the
third argument, "M","A","T","H","1","6","0", that
permutations() seems to have chosen. It almost looks like
the function took the last three values instead of the first three that
most people would have expected!
In fact, permutations() selected the lexicographically lowest three values.
We can see this if we rerun the command but change the choice of values as is
shown in Figure 8.
Figure 8
The values shown in Figure 8 are the three lexicographically ordered values
in the third argument of permutations(3,3,c("M","A","T","H","1","6","W"))
.
Lexicographic ordering is an extension of what we would
call alphabetic ordering. The extension means that we are using the coded values of the
characters to sort them. In this case it is enough to point
out that the character "1" has a lower "lexicographic" value than does the
character "6" which in turn has a lower "lexicographic" value than does the
character "A".
One issue with permutations is that it does not take
much to create a situation where the number of permutations
gets to be quite large. For example,
if we use all seven of the characters in MATH160 and ask for the permutations
of 7 things taken 3 at a time, we will get 210 permutations.
We can see this by running the command t<permutations(7,3,c("M","A","T","H","1","6","0"))
as shown in Figure 9.
Figure 9
Because the functional value was assigned to a variable, t,
there is no associated output.
However, the information about t displayed in the Environment
pane now reflects the new contents of t.
Figure 10 shows this diagnostic information.
Figure 10
Indeed, the dimensions of t shown in Figure 10 indicate that there
are 210 permutations of 7 things taken 3 at a time.
Thus, using the diagnostic information in the Environment pane
we have found a way to determine the number of permutations that we
have for whatever number of things we have taken some number of things at a time.
However, we would like to have a more direct way to find that number.
You might notice that when we ask for the number of arrangements of 7 things taken 3 at a time
we are really saying that we have three positions to fill using the 7 values,
We can form a picture to helps us.
Figure 11 shows our three positions and gives them the names first, second,
and third.
Figure 11
Then our process is to fill the three positions with the 7 values. We start by
filling the first position. We have any of seven choices that we
could put into that first position.
Once we have made that choice, however, there are only six remaining values
that we could put into the second position. That means that there are 7*6 or
42 different ways to just fill the first and second positions.
But for each of those 42 arrangements there are still five possible
choices for the third position. Therefore, we have 7*6*5 ways to fill
all three positions using our 7 possible values. But, 7*6*5=210, the number of
permutations of 7 things taken 3 at a time.
This suggests an algorithm for finding the number of
permutations of n things taken r at a time.
We just form the product of r factors,
starting with n and decreasing by one for each new factor.
This algorithm says that the number of permutations of 9 things taken 4 at a time
is equal to the value of the four factor expression 9*8*7*6, or 3024.
Before we go any further we will use our sneaky trick to see if we get the same answer.
Figure 12 shows the command to create, but not display, the permutations.
Figure 12
And, Figure 13 shows the dimensions of the new variable t, confirming
our answer of 3024.
Figure 13
Here is where we develop our own functions
for finding the number of
permutations of n things taken r at a time.

The algorithm of creating the product of r factors,
starting with n and decreasing by one for each new factor,
can be written in R to define a new function as:
num_perm < function( n, r ) # compute the number of permutations
{ # of n things taken r at aa time
if( r == 0 ) # special case if r=0
{return(1)}
p < 1 # initialize the product
for (i in 1:r) # go throgh the r factors
{ p < p*n
n < n1
}
return(p) # send back the result
}
When this text is given to R it just accepts the definition
as shown in Figure 14.
Figure 14
The first confirmation of the acceptability of our new
function is that R did not complain about any errors.
The second confirmation is that the new function,
num_perm() is now shown in the Environment
pane shown in Figure 15.
Figure 15
Once our new function is defined we can run it by
using its name and sending it two values.
For example we can have it find the number of
permutations of 9 things taken 4 at a time
by giving the command num_perm(9,4)
.
R responds with our much anticipated 3024.
Or we could have our function find the number of
permutations of 12 things taken 7 at a time
by giving the command num_perm(12,7)
.
In that case R responds with 3991680.
All of this is shown in Figure 16.
Figure 16
In all of the discussion above we have written out the
challenge in the form "find the number of
permutations of n things taken r at a time."
It would be nice if we has some way to say this in just a few
symbols. Unfortunately, there has not been any
agreement on the most acceptable form for such symbolism.
One form _{n}P_{r} has a small advantage
in that it is the form used by the TI83/84 calculators.
On such a calculator one would enter 12_{n}P_{r}7
to find the number of permutations of 12 things taken 7 at a time.
However, in a textbook or paper, the symbol
for that specific computation would be _{12}P_{7}.
Table 1 gives some the general and specific forms.
Here we will try to consistently use the _{n}P_{r} form.
Now that we have a symbol for permutations, it would be nice to have a
direct way to express the formula without having to
print out our function. The first step in doing this is to note that
_{6}P_{6} = 6*5*4*3*2*1.
In fact, _{n}P_{n} = n*(n1)*(n2)*...*3*2*1.
We have a mathematical symbol for 6*5*4*3*2*1 and that is 6!
which
is read as "6 factorial."
That means that 8! = 8*7*6*5*4*3*2*1 and
n! = n*(n1)*(n2)*...*3*2*1.
It would be nice if we were able to use the factorial symbol to help write the
equation for permutations. However,
_{8}P_{3} = 8*7*6; it only has three factors.
We need to find a way to say that we should stop appending factors at some point.
The general form _{n}P_{r} will have r factors.
It could be written as
_{n}P_{r} = n*(n1)*(n2)*...*(nr+2)*(nr+1).
That is, the general form says that we start the factors at n but stop when we get to the
factor equal to (nr+1). We can verify that for n=8 and r=3
which makes (nr+1) be 6 and, indeed, our factors start at 8 and end at 6
to get 8*7*6.
Unfortunately, there is no symbolic way to say "Start doing 8 factorial but stop after
3 factors are in place." However, we can observe that
This pattern gives us a way to write, in a short space, the value of
the product of three numbers starting at 8 and decreasing by 1 each time.
We know that
_{12}P_{5} = 12*11*10*9*8 but we could write that as
_{12}P_{5} = (12!) / 7!.
In general terms we state this pattern as
This formula, _{n}P_{r} = n! / (nr)!,
is the one generally quoted as the way to find the
number of permutations of n things taken r at a time.
The formula works and if we have some way to find factorials
then this becomes a convenient formula.
Back in Figure 14 we saw a function that we wrote, num_perm().
That function did not use factorials at all. It turns out that R
has a builtin function, factorial() that computes factorials.
Therefore, we could, if we wanted to, create a new function that does the same thing that the old one did but
this time uses factorial(). One possibility for this would be
nPr < function( n,r )
{ return (factorial(n)/factorial(nr))}
Figure 17 shows this function definition in RStudio session.
Figure 17
We can see, in the Environment pane shown in Figure 18, that R
has accepted the function definition.
Figure 18
Now that the function is defined we can use it by entering
commands such as nPr(9,4)
or nPr(12,7)
as demonstrated in Figure 19.
Figure 19
Of course we got the same results as we did from num_perm()
back in Figure 16.
Now we have two functions, num_perm() and nPr(), that do the same
thing. Which should we use? It really does not make a difference; we get the same
answer with either function. Use whichever appeals to you.
Before we leave this topic there is one sticky point that we need to cover.
The factorial() function makes sense for things like factorial(9)
or factorial(3). It even makes some sense that factorial(1)
gives the answer of 1. However, look at Figure 20.
Figure 20
According to Figure 20, 0! is 1. On the surface this may seem strange but it a
a part of the definition of factorial. In fact, we need 0! to be defined
to be 1 so that our formula for the number of permutations works out
in the extreme cases. We already know that the number of
permutations of 6 things taken 6 at a time is the same as 6!.
But our formula says that
_{6}P_{6} = 6! / (66)!.
Simplifying that denominator means that
_{6}P_{6} = 6! / 0!,
so we need to define 0! to be 1.
Return to Topics page
©Roger M. Palay
Saline, MI 48176 December, 2015