7.3: Permutations

Let \(A\) be a finite set with \(n\) elements. For \(1\le r\le n\), an \(r\)-permutation of \(A\) is an ordered selection of \(r\) distinct elements from \(A\). In other words, it is the linear arrangement of \(r\) distinct objects \(a_1a_2\ldots a_r\), where \(a_i\in A\) for each \(i\). The number of \(r\)-permutations of an \(n\)-element set is denoted by \(P(n,r)\). It also appears in many other forms and names.

• The number of permutations of \(n\) objects, taken \(r\) at a time without replacement.
• The number of ways to arrange \(n\) objects (in a sequence), taken \(r\) at a time without replacement.

All of them refer to the same number \(P(n,r)\). The keywords are:

1. “Permutation” or “arrangement,” both of which suggest that order does matter.
2. “Without replacement” means the entries in the permutation/arrangement are distinct.

In some textbooks and on some calculators, the notation \(P(n,r)\) is also written as \(P_r^n\) or \(_nP_r\).

Example \(\PageIndex{1}\label{eg:perm-01}\)

The 1-permutations of \(\{a,b,c,d\}\) are

\[\begin{array}{llll} a, & b, & c, & d. \end{array} \nonumber\]

Consequently, \(P(4,1)=4\). The 2-permutations of \(\{a,b,c,d\}\) are

\[\begin{array}{lll} ab, & ac, & ad, \\ ba, & bc, & bd, \\ ca, & cb, & cd, \\ da, & db, & dc. \end{array} \nonumber\]

Hence, \(P(4,2)=12\). What are the 3-permutations and 4-permutations of \(\{a,b,c,d\}\)? Can you explain why the numbers of 3-permutations and 4-permutations are equal?

Computing the value of \(P(n,r)\) is easy. We want to arrange \(r\) objects in a sequence. These \(r\) objects are to be selected from a pool of \(n\) items. Hence there are \(n\) ways to fill the first position. Once we settle with the first position, whatever we put there cannot be used again. We are left with \(n-1\) choices for the second position. Likewise, once it is filled, there are only \(n-2\) choices for the third position. Now it is clear that \(P(n,r)\) is the product of \(r\) numbers of the form \(n\), \(n-1, n-2, \ldots\,\). What is the last number in this list? There are \(r-1\) numbers before it, so it must be \(n-(r-1)=n-r+1\).

\(P(n,r)\) formula

Theorem \(\PageIndex{1}\)

For all integers \(n\) and \(r\) satisfying \(1 \leq r \leq n\), \[P(n,r) = n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}.\]

Although the formula \(P(n,r) = \frac{n!}{(n-r)!}\) is rather easy to remember, the other form \[P(n,r) = \underbrace{n(n-1)\cdots(n-r+1)}_r\] is actually more useful in numeric computation, especially when it is done by hand. We multiply \(n\) by the next smaller integer \(n-1\), and then the next smaller integer \(n-2\), and so forth, until we have a product of \(r\) consecutive factors. For instance, \[P(4,2) = 4\cdot3 = 12, \qquad\mbox{and}\qquad P(9,3) = 9\cdot 8\cdot 7 = 504.\] How about \(P(n,1)\) and \(P(n,2)\)?

Example \(\PageIndex{2}\label{eg:perm-02}\)

How would you compute the value of \(P(278,3)\) by hand, or if your calculator does not have that \(_nP_r\) button?

Solution

We find \(P(278,3) = 278\cdot277\cdot276 = 21253656\).

hands-on Exercise \(\PageIndex{1}\label{he:perm-01}\)

Compute \(P(21,4)\) by hand.

Remark

It follows from the first version of the formula that \(P(n,n)=n!\). The second version reduces to \[n! = P(n,n) = \frac{n!}{0!}.\] Consequently, to make the second version works, we have to define \(0!=1\).

Remark

In your homework assignments, quizzes, tests, and final exam, it is perfectly fine to use the notation \(P(n,r)\) in your answers. In fact, leaving the answers in terms of \(P(n,r)\) gives others a clue to how you obtained the answer.

It is often easier and less confusing if we use the multiplication principle. Once you realize the answer involves \(P(n,r)\), it is not difficult to figure out the values of \(n\) and \(r\). A good start, before jumping into any calculation, is to ask yourself, how would you list the possible arrangements? Also, try constructing some examples. These can give you an idea of how many choices you have in each position.

Example \(\PageIndex{3}\label{eg:perm-03}\)

A police station has 12 police officers on duty. In how many ways can they be assigned to foot patrol in five different districts, assuming that we assign only one police officer per district.

Solution

Imagine you are the officer who schedules the assignments. You have to assign someone to the first district, and then another officer to the second district, and so forth.

district:	first	second	third	fourth	fifth
			another
	any	another	different	…	…
choices:	officer	officer	officer
# of choices:	12	11	10	9	8

There are 12 choices for the first district, 11 for the second, etc. The multiplication principle implies that the answer is \(12\cdot11\cdots\), which is in the form of \(P(n,r)\). Since the product starts with 12, and we need a product of 5 consecutive numbers, the answer is \(P(12,5)\).

hands-on Exercise \(\PageIndex{2}\label{he:perm-02}\)

A school sends a team of six runners to a relay game. In how many ways can they be selected to participate in the \(4 \times 100\) m relay?

Example \(\PageIndex{4}\label{eg:perm-04}\)

From a collection of 10 flags of different patterns, how many three-flag signals can we put on a pole?

Solution

Since the flags are arranged on a flag pole, the order is important. There are 10 choices for the top flag, 9 for the second, and 8 for the third. Therefore, \(10\cdot9\cdot8 = P(10,3)\) different signals can be formed.

\(Z_n\)

\(Z_n\) \(= \{0,1,2,3, \ldots , n - 1 \}.\)

For example, \(Z_6=\{0,1,2,3,4,5\}\)  or \(Z_{22}=\{0,1,2,3, \ldots , 21\}.\)

 

Example \(\PageIndex{5}\label{eg:perm-05}\)

Determine the number of functions \(f:{\{1,3,4,7,9\}}\to{\mathbb{Z}_{22}}\) if

1. There are no restrictions.
2. \(f\) is one-to-one.
3. \(f\) is onto.

Solution

To distinguish one function from another function, we have to compare their images. Hence, a function is completely determined by its images (surprise: not by its formula!). After all, we may not even know the formula behind a function, so we cannot and should not rely on the formula alone.

To determine how many functions there are from \(\{1,3,4,7,9\}\) to \(\mathbb{Z}_{22}\), we have to determine the number of ways to assign values to \(f(1)\), \(f(3)\), \(f(4)\), \(f(7)\) and \(f(9)\).

images:	\(f(1)\)	\(f(3)\)	\(f(4)\)	\(f(7)\)	\(f(9)\)
choices:
# of choices:

(a) If there are no restrictions, we have 22 choices for each of these five images. Hence there are \(22\cdot22\cdot22\cdot22\cdot22 = 22^5\) functions.

(b) If \(f\) is one-to-one, we cannot duplicate the images. So we have 22 choices for \(f(1)\), 21 for \(f(3)\), and so on. There are \(P(22,5)\) one-to-one functions.

(c) There are at most five distinct images, but \(\mathbb{Z}_{22}\) has 22 elements, so at least 17 of them will be left unused. Hence \(f\) can never be onto. The number of onto functions is therefore zero.

hands-on Exercise \(\PageIndex{3}\label{he:perm-03}\)

How many functions are there from \(\{2,4,6,8,10\}\) to \(\mathbb{Z}_{15}\)? How many of them are one-to-one?

Example \(\PageIndex{6}\label{eg:perm-06}\)

Let \(A\) and \(B\) be finite sets, with \(|A|=s\) and \(|B|=t\). Determine the number of one-to-one functions from \(A\) to \(B\).

Solution

How can we come up with a one-to-one function from \(A\) to \(B\)? We have to specify the image of each element in \(A\). There are \(t\) choices for the first element. Since repeated images are not allowed, we have only \(t-1\) choices for the image of the second element in \(A\), and \(t-2\) choices for the third image, and so forth. The answer is \(P(t,s)\).

What if \(t<s\)? We know that in such an event, there does not exist any one-to-one function from \(A\) to \(B\) because there are not enough distinct images. Does \(P(t,s)\) still make sense? The product version of the formula says that \(P(t,s)\) is a product of \(s\) consecutive numbers. Hence, for example, \[P(3,6) = 3\cdot2\cdot1\cdot0\cdot(-1)\cdot(-2) = 0,\] which means there is no one-to-one function from \(A\) to \(B\).

Not all problems use \(P(n,r)\). In many situations, we have to use \(P(n,r)\) together with other numbers. The safest approach is to rely on the addition and multiplication principles.

Example \(\PageIndex{7}\label{eg:perm-07}\)

How many four-digit integers are there that do not contain repeated digits?

Solution

There are 10 choices for each digit, but the answer is not \(P(10,4)\), because we cannot use 0 as the first digit. To ensure that we have a four-digit integer, the first digit must be nonzero. This leaves us 9 choice for the first digit. Then we have 9 choices for the second digit, 8 and 7 for the next two. The answer is \(9\cdot9\cdot8\cdot7\).

Example \(\PageIndex{8}\label{eg:perm-08}\)

Twelve children are playing “musical chairs,” with 9 chairs arranged in a circle on the floor. In how many ways can they be seated?

Solution

The answer is not \(P(12,9)\) because any position can be the first position in a circular permutation. What matters is the relative placement of the selected objects, all we care is who is sitting next to whom. The correct answer can be found in the next theorem.

Theorem \(\PageIndex{1}\label{thm:circperm}\)

The number of circular \(r\)-permutations of an \(n\)-element set is \(P(n,r)/r\).

Proof

Compare the number of circular \(r\)-permutations to the number of linear \(r\)-permutations. Start at any position in a circular \(r\)-permutation, and go in the clockwise direction; we obtain a linear \(r\)-permutation. Since we can start at any one of the \(r\) positions, each circular \(r\)-permutation produces \(r\) linear \(r\)-permutations. This means that there are \(r\) times as many circular \(r\)-permutations as there are linear \(r\)-permutations. Therefore, the number of circular \(r\)-permutations is \(P(n,r)/r\).

Alternate Proof

Let \(A\) be the set of all linear \(r\)-permutations of the \(n\) objects, and let \(B\) be the set of all circular \(r\)-permutations. Define a function from \(A\) to \(B\) as follows. Given any \(r\)-permutation, form its image by joining its “head” to its ”tail.” It becomes clear, using the same argument in the proof above, that \(f\) is an \(r\)-to-one function, which means \(f\) maps \(r\) distinct elements from \(A\) to the same image in \(B\). Therefore \(A\) has \(r\) times as many elements as in \(B\). This means \(|A| = r\cdot|B|\). Since \(|A|=P(n,r)\), we find \(|B|=P(n,r)/r\).

hands-on Exercise \(\PageIndex{4}\label{he:perm-04}\)

A circular cardboard has eight dots marked along its rim. In how many ways can we glue eight beads of different colors, one on each dot?

hands-on Exercise \(\PageIndex{5}\label{he:perm-05}\)

In how many ways can we form a necklace with eight beads of different color?

Remark: When a necklace is flipped around, it is still the same necklace. Thus, the orientation of the necklace does not matter: we can count the beads clockwise, or counterclockwise.

Example \(\PageIndex{9}\label{eg:perm-09}\)

In how many ways can we arrange 20 knights at a round table? What if two of them refuse to sit next to each other?

Solution

Without any restriction, there are \(20!/20 = 19!\) ways to seat the 20 knights. To solve the second problem, use complement. If two of them always sit together, we in effect are arranging 19 objects in a circle. Among themselves, these two knights can be seated in two ways, depending on who is sitting on the left. Hence, there are \(2\cdot 19!/19=2\cdot18!\) ways to seat the 20 knights, with two of them always together. Therefore, the final answer to the second problem is \(19!-2\cdot18!\).

Summary and Review

• Use permutation if order matters: the keywords arrangement, sequence, and order suggest that we should use permutation.
• It is often more effective to use the multiplication principle directly.
• The number of ways to arrange \(n\) objects linearly is \(n!\), and the number of ways to arrange them in a circle is \((n-1)!\).

Exercises 

Exercise \(\PageIndex{1}\label{ex:perm-01}\)

How many eight-character passwords can be formed with the 26 letters in the English alphabet, each of which can be in uppercase or lowercase, and the 10 digits? How many of can be formed if they do not have any repeated characters?

Solution

\(62^8\), \(P(62,8)\).

Exercise \(\PageIndex{2}\label{ex:perm-02}\)

How many functions are there from \(\mathbb{Z}_6\) to \(\mathbb{Z}_{12}\)? How many of them are one-to-one?

Exercise \(\PageIndex{3}\label{ex:perm-03}\)

The school board of a school district has 14 members. In how many ways can the chair, first vice-chair, second vice-chair, treasurer, and secretary be selected?

Solution

\(P(14,5)\).

Exercise \(\PageIndex{4}\label{ex:perm-04}\)

The wrestling teams of two schools have eight and 10 members respectively. In how many ways can three matches be made up between them?

Exercise \(\PageIndex{5}\label{ex:perm-05}\)

Six students in the class will sit in a group in a circle.

(a) How many arrangements are there?

(b) How many arrangements are there if two students insist on sitting next to each other?

Solution

(a) \(\frac{6!}{6}=5!\)
(b) \(2 \cdot \frac{5!}{5}=2 \cdot 4!\)

 

Exercise \(\PageIndex{6}\label{ex:perm-06}\)

A teacher takes her AP calculus class of 8 students to lunch. They sit around a circular dining table.

1. How many seating arrangements are possible?
2. How many seating arrangements are there if the teacher has to sit on the chair closest to the soda fountain?
3. Among the students are one set of triplets. How many seating arrangements are there without all three of them sitting together?

Exercise \(\PageIndex{7}\label{ex:perm-07}\)

Eleven students go to lunch. There are two circular tables in the dining hall, one can seat 7 people, the other can hold 4. In how many ways can they be seated?

Solution

\(P(11,7)\cdot3!/7\).

Exercise \(\PageIndex{8}\label{ex:perm-08}\)

Five couples attend a wedding banquet. They are seated on a long table. How many seating arrangements that alternate men and women? What if the table is circular in shape?