Unit 2, lesson 10

Permutations

What a permutation is, how factorials count arrangements of distinct objects, why zero factorial equals 1, how to count partial permutations, and what changes for a circular arrangement.

  • Video 10
  • Ordered and Unordered Selections

Six volunteers are available for three speaking roles, opening, demonstration and closing, and nobody may take two roles. A lineup records who is chosen and which role each person fills, so A opening and B demonstrating is a different lineup from B opening and A demonstrating. How many lineups are there, and how many of them include a particular volunteer? This lesson counts ordered arrangements of distinct objects, introduces factorial notation, and shows how seating people around a circle changes which arrangements count as different.

Key terms

Permutation

Definition A permutation of nn distinct objects is an arrangement of all of them in a row, that is, an ordered list in which each object appears exactly once. More generally, an ordered selection of rr of the nn objects without replacement is an rr-permutation, also called a partial permutation. Two permutations are the same exactly when every position holds the same object. The counts on this page assume the objects are distinct. If two objects carry the same label, exchanging them leaves the list unchanged, so these counts are too large whenever at least one object is placed.

In plain words A permutation is an ordering. Order matters whenever the positions or roles can be told apart, so swapping two chosen objects produces a different outcome.

Example The three letters A, B and C have six permutations, ABC, ACB, BAC, BCA, CAB and CBA. The letters A, A and B, with two identical labels, form only three different strings, AAB, ABA and BAA, so a count of six would be wrong for them.

Factorial

Definition For a positive integer nn, the factorial of nn is

n!=n(n−1)⋯2⋅1.n! = n(n - 1) \cdots 2 \cdot 1 .

It is the number of permutations of nn distinct objects. By the product rule, the first position has nn options, the second has n−1n - 1, and so on down to a single option for the last position. Factorials satisfy the recurrence n!=n⋅(n−1)!n! = n \cdot (n - 1)! for every integer n≥2n \ge 2, and also for n=1n = 1 once 0!0! is defined.

In plain words The factorial of a positive whole number multiplies it by every smaller positive whole number. The exclamation mark is only notation. Factorials grow very fast, for example 10!=3,628,80010! = 3{,}628{,}800.

Example Six volunteers can stand in a line in 6!=6⋅5⋅4⋅3⋅2⋅1=7206! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720 orders. Four books can stand on a shelf in 4!=244! = 24 orders.

Zero factorial

Definition Zero factorial is defined as 0!=10! = 1. Two facts support this choice. An empty collection has exactly one arrangement, the empty list, in which no placements are made. Also, the recurrence n!=n⋅(n−1)!n! = n \cdot (n - 1)! at n=1n = 1 reads 1=1⋅0!1 = 1 \cdot 0!, which forces 0!=10! = 1. Factorials of negative integers are not defined.

In plain words There is exactly one way to arrange nothing. Zero factorial is 1, not 0, and that value keeps the counting formulas correct at their edges.

Example Filling 6 ordered roles from 6 volunteers with the partial permutation formula below gives 6!/(6−6)!=6!/0!=7206!/(6 - 6)! = 6!/0! = 720, the number of full lineups. The answer comes out right because 0!=10! = 1. With the value 0 the expression would not even be defined.

Partial permutation

Definition For integers 0≤r≤n0 \le r \le n, the number of ordered selections of rr objects from nn distinct objects without replacement is

nPr=n!(n−r)!.{}_nP_r = \frac{n!}{(n - r)!}.

The symbol nPr{}_nP_r is a count, not a probability. Dividing by (n−r)!(n - r)! cancels the unused factors of n!n! and leaves its first rr factors, the product n(n−1)⋯(n−r+1)n(n - 1) \cdots (n - r + 1). The case r=nr = n gives n!n!, and the case r=0r = 0 gives 1, the single empty selection. If r>nr > n, no such selection exists, because the objects run out, and the factorial formula does not apply since (n−r)!(n - r)! is not defined.

In plain words Fill rr distinguishable positions one at a time from a pool that starts with nn objects and shrinks by one at each step, and stop after rr factors.

Example Three ordered roles from six volunteers give 6P3=6!/3!=6⋅5⋅4=120{}_6P_3 = 6!/3! = 6 \cdot 5 \cdot 4 = 120 lineups. If volunteer A must open, the other two roles can be filled in 5⋅4=205 \cdot 4 = 20 ways. If A must appear in some role, A’s role can be chosen in 3 ways and the other two roles filled in 5⋅4=205 \cdot 4 = 20 ways, giving 60 lineups. A complement count agrees, since 5P3=60{}_5P_3 = 60 lineups omit A and 120−60=60120 - 60 = 60. Now suppose a lineup is chosen uniformly from the 120. Let OO be the event that A opens and II the event that A appears in some role. Then

P(O)=20120=16,P(I)=60120=12.\begin{gathered} P(O) = \frac{20}{120} = \frac{1}{6}, \\[0.4em] P(I) = \frac{60}{120} = \frac{1}{2}. \end{gathered}

These probabilities rest on the uniform assumption. An organizer who prefers experienced volunteers for the opening role changes the probabilities while the count of valid lineups stays 120.

Circular arrangement

Definition A circular arrangement of n≥1n \ge 1 distinct objects places them around a circle whose positions are not labeled, and two placements count as the same when one is a rotation of the other. The number of circular arrangements is

n!n=(n−1)!,\frac{n!}{n} = (n - 1)!,

because each circular arrangement, read in a fixed direction, gives exactly nn of the n!n! linear lists, one for each choice of starting object. Equivalently, fix one object as a reference point and arrange the other n−1n - 1 in order around it. This convention counts a seating and its mirror image separately whenever they differ. For n≥3n \ge 3 they always differ, because a rotation keeps each person’s left and right neighbors while a reflection swaps them, and with three or more people those two neighbors are different people. If mirror images are also identified, the count for n≥3n \ge 3 is (n−1)!/2(n - 1)!/2. If the seats are numbered, the positions are distinguishable again and the count is n!n!.

In plain words Around an unlabeled circle only the relative order matters, so turning everyone together does not create a new seating. The phrase “around a table” does not settle the convention by itself, so state whether rotations, reflections or both count as the same.

Example Six people around an unlabeled round table, with rotations identified and mirror images kept distinct, can be seated in 6!/6=5!=1206!/6 = 5! = 120 ways. Identifying mirror images as well gives 120/2=60120/2 = 60 seatings, and six numbered chairs give 6!=7206! = 720 assignments.

Check yourself

  1. Compute 8!/6!8!/6! without writing out either factorial in full, and describe a counting problem it answers.
Show the answer

The factors from 6 down to 1 cancel, leaving 8⋅7=568 \cdot 7 = 56. This is 8P2{}_8P_2, the number of ordered selections of 2 objects from 8 distinct objects. For example, it counts the ways to choose a president and a vice president from 8 club members when one person cannot hold both offices.

  1. Seven distinct volunteers fill four distinct roles, and no one takes two roles. Count all assignments, the assignments with volunteer G in the final role, and the assignments that omit G. If an assignment is chosen uniformly from all valid ones, what is the probability that G is included?
Show the answer

There are 7P4=7⋅6⋅5⋅4=840{}_7P_4 = 7 \cdot 6 \cdot 5 \cdot 4 = 840 assignments. With G fixed in the final role, the other three roles have 6⋅5⋅4=1206 \cdot 5 \cdot 4 = 120 fillings. Omitting G leaves six volunteers for four roles, so 6P4=6⋅5⋅4⋅3=360{}_6P_4 = 6 \cdot 5 \cdot 4 \cdot 3 = 360 assignments omit G, and 840−360=480840 - 360 = 480 include G. A direct count agrees, since G can take any of the 4 roles and each choice leaves 120 fillings, and 4⋅120=4804 \cdot 120 = 480. Hence

P(G included)=480840=47.P(\text{G included}) = \frac{480}{840} = \frac{4}{7}.
  1. Five people, A and B among them, are seated in two ways, first in a row of five chairs and then around an unlabeled round table where rotations count as the same seating. In each case, how many seatings put A and B next to each other, and what is the probability of that under uniform seating?
Show the answer

In the row, glue A and B into one block. The block and the other three people form 4 units with 4!=244! = 24 orders, and the block itself has 2 internal orders, so 2⋅24=482 \cdot 24 = 48 of the 5!=1205! = 120 seatings put them together. The probability is 48/120=2/548/120 = 2/5.

Around the table there are 4!=244! = 24 seatings. Fix A as the reference point. Then B must take one of the 2 seats beside A, and the other three people fill the remaining seats in 3!=63! = 6 ways, so 12 seatings put them together. The probability is 12/24=1/212/24 = 1/2.

The answers differ because the line and the circle are different outcome sets. In the row, a person at either end has only one neighbor, while around the table everyone has two.

How this lesson connects