Chapter 3 — Front Matter
Purpose and Overview
This chapter develops one of the central ideas in combinatorics: the ordered arrangement. When the positions of objects matter — when switching two elements produces something genuinely different — the situation calls for permutation reasoning. This chapter builds that reasoning carefully, beginning with the meaning of order and factorials, then extending through arrangements of selected objects, circular arrangements, repeated symbols, and restricted positions.
Every formula in this chapter will be connected to its meaning. The goal is not to memorize a formula and move on. The goal is to understand why ordered arrangements are counted the way they are, when a restriction changes the structure of the count, and how to justify a permutation argument in clear and complete terms.
Opening Question
A competition awards gold, silver, and bronze medals to three different athletes chosen from a field of ten finalists. How many different outcomes are possible? Before answering, think carefully: does it matter which medal each athlete receives? If Alice wins gold and Bob wins silver, is that the same outcome as Alice winning silver and Bob winning gold? It is not. The medals are distinct. The positions are distinct. The order in which athletes are assigned to positions matters. This is a permutation problem. By the end of this chapter, you will be able to count outcomes like this one, justify the count, and recognize the structure that makes it different from a selection problem where order does not matter.
14Sections
14Objectives
11Key Terms
15+Worked Examples
Why This Chapter Matters
Permutation reasoning appears throughout mathematics, computing, science, and everyday decision-making. Passwords, access codes, and cryptographic keys depend on the number of ordered sequences of characters. Scheduling problems — which job runs first, which flight departs at which time — are permutation problems. Genetics depends on the ordered sequences of base pairs. Algorithms process data in sequences. Rankings, outcomes in competitions, and assigned roles all involve ordered arrangements.
Understanding permutations also prepares you for the next major idea: combinations, where order is deliberately ignored. You cannot correctly understand combinations without first understanding permutations clearly, because combinations are built by removing the overcounting that comes from treating order as irrelevant.
Learning Objectives
- 1Explain what an arrangement is and why order matters in certain counting problems.
- 2Compute and interpret factorials.
- 3Count arrangements of all distinct objects from a set.
- 4Count arrangements of some objects chosen from a larger set of distinct objects.
- 5Count arrangements when repetition of objects is allowed.
- 6Count arrangements of objects that include repeated identical symbols.
- 7Count circular arrangements and explain how they differ from linear arrangements.
- 8Apply restrictions to arrangement problems using the restriction-first method.
- 9Apply the gap method to separate specified objects in a line.
- 10Apply the block method to keep specified objects together.
- 11Describe derangements informally and connect them to later study.
- 12Apply permutation reasoning to codes, seating, and scheduling models.
- 13Identify and correct common permutation mistakes.
- 14Distinguish permutation problems from combination problems.
Sections 3.1 – 3.2
Arrangements and Factorials: The Foundation
What an Arrangement Is · Factorials · Definition · Computation · Cancellation
Section 3.1
What an Arrangement Is
An arrangement is a listing of objects in a definite order. The word definite here means that position carries meaning. If you rearrange the same objects into a different order, you get a different arrangement.
Consider three letters: A, B, and C. There are several ways to list all three in a row: ABC, ACB, BAC, BCA, CAB, and CBA. These six orderings are six distinct arrangements, because the positions are meaningful. Placing A first and B second is different from placing B first and A second, even though both lists use the same three letters.
Now compare this to a situation where order does not matter. If you are choosing a committee of three people from a group, you do not assign anyone to a first position or a second position. The group {Alice, Bob, Carol} is the same committee regardless of the order you list the names. That situation calls for different reasoning, which we will study carefully in Chapter 4.
In this chapter, order matters. Every distinction of position is real. Two arrangements are different whenever any object occupies a different position.
Key Diagnostic Question
Before choosing a counting method, ask: Does the order in which objects are arranged matter? If yes, you are in permutation territory. If different orderings of the same group are not meaningfully different, you are in combination territory.
- A teacher assigns three students to the roles of Presenter, Note-taker, and Timer. Does the order of assignment matter? Explain.
- A teacher selects three students to form a study group. Does the order of selection matter? Explain.
- A safe opens when digits are entered in a specific sequence. Does order matter? Explain.
- A committee selects three members to attend a conference. Does the order of selection matter? Explain.
- A race finishes with five runners crossing the line in some sequence. Does order matter? Explain.
Section 3.2
Factorials
Suppose you have n distinct objects and you want to arrange all of them in a row. Think about it step by step using the product rule from Chapter 2. For the first position, you have n choices. Once the first position is filled, you have n − 1 choices for the second position. Once the second position is filled, you have n − 2 choices for the third position. And so on, until the last position, which has only 1 choice.
By the product rule, the total number of arrangements is:
n · (n − 1) · (n − 2) · · · 2 · 1
This product is important enough to have its own name and notation.
Definition — Factorial
For any positive integer n, the factorial of n, written n!, is defined as:
n! = n · (n − 1) · (n − 2) · · · 2 · 1
By convention, 0! = 1. There is exactly one way to arrange zero objects: do nothing. This convention also ensures that formulas involving factorials work correctly at boundary cases.
Factorial Values
0!= 1
1!= 1
2!= 2
3!= 6
4!= 24
5!= 120
6!= 720
7!= 5,040
8!= 40,320
9!= 362,880
10!= 3,628,800
Recursive Form
Factorials have a natural recursive structure: n! = n · (n − 1)! Arranging n objects is the same as choosing the first object (n ways) and then arranging the remaining n − 1 objects in (n − 1)! ways. This recursive view connects to recurrence relations in Chapter 10.
Cancellation in Factorial Fractions
When factorials appear in fractions, they often cancel in useful ways. Since n! = n · (n−1) · · · (n−k+1) · (n−k)!, dividing by (n−k)! cancels the tail of the product:
Example 3.2.1
Computing a factorial fraction by cancellation
- ProblemCompute 8! / 5! without computing 8! or 5! separately.
- ThinkThe denominator 5! appears as part of 8!. Write out 8! long enough to see 5! inside it.
- Count
8! / 5! = (8 · 7 · 6 · 5!) / 5! = 8 · 7 · 6 = 336
- CheckWe can verify: 8! = 40,320 and 5! = 120, so 40,320 / 120 = 336. Correct.
- InterpretThe expression 8!/5! counts the number of ways to fill three ordered positions using objects chosen from eight distinct objects without repetition, as we will see in Section 3.4.
Answer: 8! / 5! = 8 · 7 · 6 = 336
- Compute 6!
- Compute 9! / 6!
- Compute 7! / (3! · 4!)
- Compute 10! / (2! · 3! · 5!)
- Simplify n! / (n − 1)! in terms of n
- Simplify (n + 1)! / (n − 1)! in terms of n
- Simplify 15! / 13! without computing 15!
- Show that (n + 1)! = (n + 1) · n! using the definition of factorial
Student Warning
A student claims 4! + 3! = 7!. This is wrong. Factorials are not added like ordinary numbers. 4! + 3! = 24 + 6 = 30, which is not 7! = 5,040. Factorial notation means a specific product, not a sum.
Sections 3.3 – 3.6
The Four Main Arrangement Models
All Distinct Objects · Some from a Larger Set · Repetition Allowed · Repeated Symbols
Section 3.3
Permutations of All Distinct Objects
If you have n distinct objects and you arrange all of them in a row, the number of arrangements is n!. This follows directly from the product rule argument: fill the first position in n ways, the second in n − 1 ways, and so on down to 1.
Example 3.3.1
Seating six people in a row
- ProblemSix people are seated in a row of six chairs. How many different seating arrangements are possible?
- ThinkAll six people are distinct. Each person occupies exactly one chair. The order of seating matters because changing who sits in which chair produces a genuinely different arrangement.
- RepresentWe are arranging 6 distinct objects in 6 distinct positions, one object per position.
- Count
6! = 6 · 5 · 4 · 3 · 2 · 1 = 720
- CheckWith 6 people, each of the 720 orderings is genuinely different because swapping any two people changes who sits where.
Answer: 720 distinct seating arrangements.
Example 3.3.2
Arranging books on a shelf
- ProblemA student has 8 distinct books and one shelf. How many different ways can the student arrange all 8 books in a row?
- Count
8! = 40,320
- InterpretThere are 40,320 ways to arrange 8 distinct books in a row. This demonstrates how rapidly the count grows even for a small number of objects.
Answer: 40,320 arrangements.
Section 3.4
Arranging Some Objects from a Larger Set
In many problems, you do not arrange all of the available objects. You select some of them and arrange only the selected ones. Suppose you have n distinct objects and you want to fill exactly k ordered positions, where k ≤ n. By the product rule:
First position: n choices · Second: n − 1 · Third: n − 2 · · · · · k-th position: n − k + 1
Notation
P(n, k) is also written nPk or Pkn. All mean the same thing. This textbook uses P(n, k). Boundary cases: P(n, n) = n! and P(n, 0) = 1.
Example 3.4.1
Medal ceremony
- ProblemTen athletes compete. Gold, silver, and bronze medals are awarded to the top three finishers. How many different medal outcomes are possible?
- ThinkThree positions must be filled: gold, silver, bronze. The positions are distinct because different medals have different meanings. We are choosing 3 from 10 and arranging them in order.
- RepresentThis is P(10, 3): arranging 3 objects from 10 distinct objects into 3 ordered positions.
- Count
P(10, 3) = 10! / (10 − 3)! = 10! / 7! = 10 · 9 · 8 = 720
- CheckGold has 10 options. Silver has 9. Bronze has 8. This matches 10 · 9 · 8 = 720. Correct.
Answer: 720 distinct medal outcomes.
Example 3.4.2
Creating a ranked list
- ProblemA teacher has 15 student essays to rank. The teacher wants to select and rank the top 4. How many different ranked outcomes are possible?
- Count
P(15, 4) = 15! / 11! = 15 · 14 · 13 · 12 = 32,760
Answer: 32,760 possible ranked outcomes.
Section 3.5
Permutations with Repetition Allowed
All of the arrangements counted so far assume each object can be used only once. But many real situations allow repetition — a combination lock can repeat digits; a binary string reuses 0 and 1 freely. When repetition is allowed, each position is filled independently, so the number of choices stays the same at every step.
Example 3.5.1
PIN codes
- ProblemA four-digit PIN code uses digits 0 through 9 in each position, and digits may repeat. How many possible PIN codes are there?
- ThinkEach of the 4 positions has 10 possible digits. Repetition is allowed, so choices are independent.
- Count
10^4 = 10,000
Answer: 10,000 possible four-digit PIN codes.
Example 3.5.2
Binary strings
- ProblemHow many binary strings of length 8 are there?
- Count
2^8 = 256
- InterpretThere are 256 distinct 8-bit binary strings. This is why one byte of data represents exactly 256 distinct values.
Answer: 256 distinct 8-bit binary strings.
Example 3.5.3
License plates
- ProblemA license plate consists of 3 letters followed by 3 digits. Letters may repeat; digits may repeat. How many license plates are possible?
- Count
26^3 · 10^3 = 17,576 · 1,000 = 17,576,000
Answer: Approximately 17.6 million distinct license plates.
Section 3.6
Permutations of Repeated Symbols
What happens when the objects themselves are not all distinct? Suppose you want to arrange the letters of the word BOOK. The two O's are identical. If you label them O₁ and O₂ to make them temporarily distinct, the arrangements BO₁O₂K and BO₂O₁K look different but produce the same string: BOOK. Treating the O's as distinct produces overcounting — every arrangement gets counted twice. To correct this, divide by 2! = 2, the number of ways to rearrange the identical O's among themselves.
where n = total objects, n₁ = count of the first repeated symbol, n₂ = count of the second, and so on, with n₁ + n₂ + · · · + nr = n.
Example 3.6.1
Arranging MISSISSIPPI
- ProblemHow many distinct arrangements of the letters of MISSISSIPPI are there?
- ThinkCount the repeated letters: M appears 1 time, I appears 4 times, S appears 4 times, P appears 2 times. Total letters: 1 + 4 + 4 + 2 = 11.
- Count
11! / (1! · 4! · 4! · 2!)
= 39,916,800 / (1 · 24 · 24 · 2)
= 39,916,800 / 1,152
= 34,650
Answer: 34,650 distinct arrangements.
Example 3.6.2
Arranging ARRANGE
- ProblemHow many distinct arrangements are there of the letters in ARRANGE?
- ThinkA appears 2 times, R appears 2 times, N appears 1 time, G appears 1 time, E appears 1 time. Total: 7 letters.
- Count
7! / (2! · 2! · 1! · 1! · 1!)
= 5,040 / (2 · 2 · 1 · 1 · 1)
= 5,040 / 4
= 1,260
Answer: 1,260 distinct arrangements.
- Compute P(8, 3)
- Compute P(12, 5)
- Compute P(7, 7)
- Compute P(10, 1)
- Simplify P(n, 2)
- How many 4-letter arrangements from {A, B, C, D, E, F, G}, no repeats?
- How many 3-character codes from {A, B, C, D, E} with repetition?
- How many 5-character binary strings (0 and 1, with repetition)?
- Distinct arrangements of BANANA?
- Distinct arrangements of MISSISSIPPI?
Sections 3.7 – 3.11
Circular, Restricted, and Special Arrangements
Circular Permutations · Restrictions · Gap Method · Block Method · Derangements
Section 3.7
Circular Permutations
All previous arrangements were linear: objects are placed in a row, and the positions are numbered from left to right. In a circular arrangement, there is no fixed starting position. What matters is the relative order of objects with respect to each other — not their absolute positions.
Consider three people, A, B, and C, seated around a circular table. The linear arrangements ABC, BCA, and CAB all describe the same circular seating — in each case, A is next to B and C, in the same relative order. These are rotations of each other and count as one circular arrangement.
For a linear arrangement of n objects there are n! arrangements. Every group of n linear arrangements corresponds to one circular arrangement (rotating the circle gives n distinct linear orderings of the same circular pattern). So we divide by n:
What About Reflections?
If a circular arrangement is also considered the same as its mirror image (necklaces where flipping over gives the same necklace), then divide by an additional factor of 2:
Circular arrangements up to rotation and reflection = (n − 1)! / 2
In most seating problems, reflections are not equivalent — sitting to the left of someone is different from sitting to the right. Read each problem carefully.
Example 3.7.1
Seating around a circular table
- ProblemEight people are seated around a circular table. How many distinct seating arrangements are there?
- ThinkFix one person's seat to remove rotational symmetry, then count arrangements of the remaining 7.
- Count
(8 − 1)! = 7! = 5,040
- CheckThe linear count would be 8! = 40,320. Each circular arrangement corresponds to 8 linear arrangements (one for each rotation), so 40,320 / 8 = 5,040. Consistent.
Answer: 5,040 distinct circular seating arrangements.
Example 3.7.2
Arranging keys on a key ring
- ProblemSix distinct keys are placed on a circular key ring. Flipping the ring over produces the same arrangement. How many distinct arrangements are there?
- ThinkReflections are equivalent. Circular arrangements up to rotation: (6 − 1)! = 120. Divide by 2 for reflections.
- Count
(6 − 1)! / 2 = 5! / 2 = 120 / 2 = 60
Answer: 60 distinct arrangements.
Section 3.8
Arrangements with Restrictions
Restrictions change the structure of a permutation problem. A restriction might say: a specific person must sit in a specific seat; two people cannot sit adjacent to each other; a specific letter must appear first; a certain item must be included or excluded.
The general principle is: handle restrictions before counting freely.
Restriction-First Method
1. Identify what the restriction requires.
2. Satisfy the restriction first.
3. Count the remaining free choices.
4. Multiply all results together.
Example 3.8.1
Fixed position restriction
- ProblemSeven people are seated in a row of seven chairs. Alex must sit in the leftmost chair. How many arrangements are possible?
- ThinkThe restriction fixes Alex in chair 1. The remaining 6 people can be arranged freely in the remaining 6 chairs.
- Count
1 · 6! = 720
Answer: 720 valid seating arrangements.
Example 3.8.2
Two people must not sit together — complement counting
- ProblemFive people are seated in a row of five chairs. Alex and Blair must not sit in adjacent chairs. How many valid arrangements are there?
- ThinkUse complement counting: Valid = Total − (Alex and Blair are adjacent).
- Count — Total
5! = 120
- Count — AdjacentTreat Alex and Blair as a block: 4 units arranged in 4! = 24 ways. Within the block, 2! = 2 internal arrangements. Adjacent count: 4! · 2! = 24 · 2 = 48.
- Count — Valid
120 − 48 = 72
Answer: 72 valid seating arrangements.
Example 3.8.3
Restriction on first position
- ProblemA password of length 4 is formed using digits 0–9 without repetition. The password must begin with an odd digit. How many such passwords are there?
- ThinkOdd digits in 0–9 are {1, 3, 5, 7, 9} — 5 options. Once the first digit is chosen, fill the remaining 3 positions from the remaining 9 digits without repetition.
- Count
5 · 9 · 8 · 7 = 2,520
Answer: 2,520 valid passwords.
Section 3.9
The Gap Method for Separation Problems
When a restriction requires that certain objects must not be adjacent to each other, the gap method is an efficient technique. The key insight: first arrange the unrestricted objects, then insert the restricted objects into the spaces between them.
Gap Method Procedure
1. Arrange the m unrestricted objects in a row: m! ways.
2. The m objects create m + 1 gaps (before, between, and after).
3. Place s separated objects into distinct gaps: P(m + 1, s) ways.
4. Multiply: m! · P(m + 1, s).
Example 3.9.1
No two vowels adjacent
- ProblemArrange the letters A, B, C, D, E so that no two vowels (A and E) are adjacent.
- ThinkThe consonants are B, C, D (three objects). Arrange them first, then place the vowels in the gaps so they are not adjacent to each other.
- RepresentArrange B, C, D: 3! = 6 ways. This creates 4 gaps: _ B _ C _ D _. Choose 2 of 4 gaps for the 2 vowels, arranging them: P(4, 2) = 4 · 3 = 12 ways.
- Count
3! · P(4, 2) = 6 · 12 = 72
- CheckTotal arrangements of 5 letters: 5! = 120. The count of 72 is less than 120, as expected with a restriction. Reasonable.
Answer: 72 arrangements with no two vowels adjacent.
Example 3.9.2
Separating specific people in a row
- ProblemSix people are seated in a row. Three specific people — X, Y, Z — must not sit adjacent to any of the other two. How many valid arrangements are there?
- ThinkArrange the 3 non-restricted people (P, Q, R): 3! = 6 ways. This creates 4 gaps. Place X, Y, Z in distinct gaps: P(4, 3) = 4 · 3 · 2 = 24 ways.
- Count
3! · P(4, 3) = 6 · 24 = 144
Answer: 144 valid seating arrangements.
Section 3.10
The Block Method for Togetherness Problems
When a restriction requires that certain objects must remain adjacent to each other, the block method treats the group of required-together objects as a single unit.
Block Method Procedure
1. Combine the objects that must stay together into a single block.
2. Count the arrangements of the block plus the remaining free objects: if there were originally n objects and the block contains b of them, you now have n − b + 1 units.
3. Within the block, the objects can be arranged in b! ways (or fewer if they have their own restrictions).
4. Multiply: (n − b + 1)! · b!.
Example 3.10.1
Family members must sit together
- ProblemEight people, including a family of three (F1, F2, F3), are seated in a row. The three family members must sit in adjacent seats. How many valid arrangements are there?
- ThinkTreat the family of three as a single block. We now have 8 − 3 + 1 = 6 units: the family block plus 5 others.
- Count
6! · 3! = 720 · 6 = 4,320
Answer: 4,320 valid arrangements.
Example 3.10.2
Multiple groups must stay together
- ProblemTen people are seated in a row. Group A (2 people) must sit together. Group B (3 people) must sit together. How many valid arrangements are there?
- ThinkTreat Group A as one block and Group B as another. We have 10 − 2 − 3 + 2 = 7 units. Arrange 7 units; arrange within each block.
- Count
7! · 2! · 3! = 5,040 · 2 · 6 = 60,480
Answer: 60,480 valid arrangements.
Gap vs. Block — Don't Confuse Them
The gap method is for objects that must be separated from each other. The block method is for objects that must stay together. Using the wrong method produces an incorrect count. Check the restriction carefully before choosing a technique.
Section 3.11
Derangements: An Introduction
A derangement is a permutation in which no object appears in its original position. Every object is displaced. Consider the letters A, B, C in their natural positions. A derangement is any arrangement where A is not in position 1, B is not in position 2, and C is not in position 3.
| Arrangement | A in pos 1? | B in pos 2? | C in pos 3? | Derangement? |
|---|
ABC | Yes | Yes | Yes | No |
ACB | Yes | — | — | No |
BAC | — | — | Yes | No |
BCA | No | No | No | Yes |
CAB | No | No | No | Yes |
CBA | — | Yes | — | No |
There are exactly 2 derangements of 3 objects: BCA and CAB. The number of derangements of n objects, written Dn or !n, satisfies a beautiful formula developed using inclusion-exclusion in Chapter 7.
MGU Library Connection
- The derangement formula and its connection to inclusion-exclusion will be fully developed in Chapter 7 of this book.
- The derangement sequence also appears in the MGU Combinatorics Formula Sheet under "Inclusion-Exclusion and Derangements."
- How many ways can 5 people be seated around a circular table?
- How many ways can 10 people be seated around a circular table?
- Eight keys are on a circular key ring that can be flipped. How many distinct arrangements are there?
- Six people sit around a circular table. Two specific people must not be adjacent. How many valid arrangements are there? (Hint: use complement counting in circular form.)
- Seven people are seated in a row. Two specific people must sit adjacent to each other. How many valid arrangements are there?
- Arrange {A, E, I, B, C, D, F} in a row so that no two vowels (A, E, I) are adjacent. How many arrangements are possible?
- Ten people are seated in a row. Three specific people must all sit together. How many valid arrangements are there?
- List all derangements of {1, 2, 3, 4}. How many are there? Compare with the table in Section 3.11.
Sections 3.12 – 3.14
Applications, Mistakes, and the Road Ahead
Codes · Seating · Scheduling · Common Errors · Preparing for Combinations
Section 3.12
Arrangements in Codes, Seating, and Scheduling
Permutations model a wide range of practical situations. This section illustrates how the ideas of this chapter apply to codes, seating, and scheduling contexts.
Codes and Cryptography
A code is an ordered sequence of symbols. A 5-character code using 26 uppercase letters without repetition gives P(26, 5) = 26 · 25 · 24 · 23 · 22 = 7,893,600 possible codes. With repetition: 26⁵ = 11,881,376. The difference illustrates why repetition significantly expands the space of possible codes. In cryptography, a larger code space means harder brute-force attacks. This is why longer passwords with repeated characters are stronger than shorter passwords without repetition.
Seating Problems — Summary Table
| Situation | Formula |
|---|
| n distinct people in n chairs in a row | n! |
| n distinct people around a circular table | (n − 1)! |
| n people, circular, reflections equivalent | (n − 1)! / 2 |
| n people in a row, group of b must stay together | (n − b + 1)! · b! |
| n people in a row, s specific people must be separated | (n − s)! · P(n − s + 1, s) |
Example 3.12.1
Tournament scheduling
- ProblemA round-robin tournament has 6 teams. Each team plays every other team exactly once. There are C(6,2) = 15 matches total (we will prove this in Chapter 4). In how many different orders can the 15 matches be scheduled across 15 time slots?
- ThinkWe are arranging 15 distinct matches in 15 distinct time slots.
- Count
15! = 1,307,674,368,000
- InterpretThere are over 1.3 trillion possible scheduling orders. Even small scheduling problems have astronomically large solution spaces, which is why operations research uses optimization algorithms rather than exhaustive search.
Answer: 15! ≈ 1.3 trillion scheduling orders.
Section 3.13
Common Permutation Mistakes
Mistake 1 — Using a permutation formula when combinations are needed
P(20, 3) counts committee members
If you want to count how many groups of 3 students can form a committee from a class of 20, order does not matter. The committee {Alice, Bob, Carol} is the same regardless of listing order. Use combinations (Chapter 4), not P(n, k).
Mistake 2 — Applying the general formula before handling restrictions
Compute n! first, then adjust for restrictions
Students often compute n! or P(n, k) first and then try to subtract restricted cases afterward. While complement counting can work, it is easy to miss cases when restrictions are multiple. Identify and satisfy restrictions first, then count free choices.
Mistake 3 — Treating circular arrangements like linear ones
Circular arrangements of 6 people = 6! = 720
Correct: (6 − 1)! = 5! = 120. Each circular arrangement appears in 6 rotational versions among the linear orderings, so divide by 6.
Mistake 4 — Dividing by repeated symbols incorrectly
Dividing by a wrong factorial or forgetting to divide at all
Carefully count how many objects of each type are identical before writing the denominator. Each repeated symbol type gets its own factorial in the denominator.
Mistake 5 — Using repetition formulas when the problem forbids repetition
Using 26^4 when letters cannot repeat
"Choose 4 letters from the alphabet to form a code" most naturally means without repetition unless stated otherwise. Ask explicitly: can an object be used more than once?
Mistake 6 — Forgetting internal arrangements in the block method
Family of 3 together: answer is 6! only
When treating a group as a block, always multiply by the number of internal arrangements of the block. If a family of 3 must sit together, multiply by 3! = 6 for internal orderings.
Mistake 7 — Confusing the gap method and the block method
Using gaps when objects must stay together
The gap method is for objects that must be separated. The block method is for objects that must stay together. Check the restriction carefully before choosing a technique.
Mistake 8 — Confusing "choose and arrange" with "choose only"
Using C(n, 5) when roles are assigned
If a problem says "select 5 people and assign them to 5 distinct roles," both selection and arrangement are involved. This calls for P(n, 5), not C(n, 5).
Section 3.14
Preparing for Combinations
This chapter developed ordered arrangements. In Chapter 4, we turn to unordered selections. The transition is conceptually important. A permutation counts arrangements where position matters. A combination counts groups where only membership matters.
If you arrange 3 objects chosen from 5, you get P(5, 3) = 60 ordered arrangements. But if you only care which 3 objects were chosen — not in what order — many of those 60 arrangements represent the same group. Specifically, any one group of 3 objects can be arranged in 3! = 6 different orders. So the number of unordered groups is:
This is the combination C(5, 3) = 10. Combinations are derived directly from permutations by dividing out the overcounting caused by order. If you understand why arrangements are counted the way they are, you will understand why the combination formula works. Chapter 4 will develop combinations carefully: what they count, why the formula works, when to use them instead of permutations, and how to handle restricted selections.
Chapter 3 — Back Matter
Chapter Summary
- Sec 3.1An arrangement is a listing of objects in a definite order. When the problem distinguishes different orderings of the same objects, we are in permutation territory. The key question: does the order in which objects are arranged matter?
- Sec 3.2The factorial n! = n · (n−1) · · · 1 counts arrangements of all n distinct objects. By definition, 0! = 1. Factorials grow rapidly. They cancel in fractions: n!/(n−k)! = n · (n−1) · · · (n−k+1).
- Sec 3.3The number of arrangements of all n distinct objects is n!. This follows from the product rule applied to all positions in sequence.
- Sec 3.4The number of ordered arrangements of k objects from n distinct objects without repetition is P(n, k) = n!/(n−k)!. Boundary cases: P(n, n) = n! and P(n, 0) = 1.
- Sec 3.5When repetition is allowed, each position is filled independently. The number of arrangements of k positions using n symbols is n^k.
- Sec 3.6When objects include repeated identical symbols, divide by the factorials of the repetition counts: n! / (n₁! · n₂! · · · nr!). This corrects overcounting caused by treating identical objects as distinct.
- Sec 3.7Circular arrangements of n distinct objects: (n−1)!, because rotations are equivalent. If reflections are also equivalent (necklaces, key rings): (n−1)!/2.
- Sec 3.8Restrictions must be handled before applying free-choice formulas. The restriction-first method: satisfy the restriction, then count remaining free choices, then multiply.
- Sec 3.9The gap method is used when specified objects must be separated. Arrange the unrestricted objects first (m!), count the m+1 gaps, then insert the separated objects using P(m+1, s).
- Sec 3.10The block method is used when specified objects must stay together. Treat the group as a single unit, count the arrangements of the block among other units, then multiply by the internal arrangements of the block.
- Sec 3.11A derangement is a permutation where no object is in its original position. D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9. The full derangement formula will be developed in Chapter 7 using inclusion-exclusion.
- Sec 3.12Permutations model codes (with or without repetition), seating (linear and circular), and scheduling (ordered sequences of tasks). Even small scheduling problems have astronomically large solution spaces.
- Sec 3.13Eight common errors: confusing permutations and combinations; ignoring restrictions; circular vs. linear confusion; incorrect divisors for repeated symbols; allowing unwanted repetition; forgetting internal block arrangements; confusing gap and block methods; confusing "select and assign" with "select only."
- Sec 3.14Combinations arise from permutations by dividing out the overcounting caused by order: C(n, k) = P(n, k) / k!. Permutations are the foundation on which Chapter 4 builds.
Key Terms Review
arrangement
A listing of objects in a specific order, where different orderings count as different outcomes.
factorial
For a positive integer n, the product n · (n−1) · · · 1; by definition, 0! = 1.
permutation
An ordered arrangement of objects chosen from a set.
P(n, k)
The number of ordered arrangements of k objects chosen from n distinct objects without repetition; P(n, k) = n! / (n−k)!.
repetition allowed
An arrangement model where each position may be filled by any of the n available symbols; count: n^k.
repeated symbols
Identical objects in an arrangement that reduce the number of distinct arrangements; corrected by dividing by repetition factorials.
circular permutation
An arrangement where rotations of the same arrangement are considered identical; count: (n−1)!.
restriction
A condition that limits which objects may occupy certain positions or which combinations of positions are allowed.
gap method
A technique for counting arrangements where specified objects must be separated, by placing other objects first and inserting the separated objects in the resulting gaps.
block method
A technique for counting arrangements where specified objects must remain together, by treating the group as a single unit.
derangement
A permutation in which no object appears in its original position.
fixed point
An object that remains in its original position under a permutation; derangements have no fixed points.
Concept Review Questions
- What does it mean for order to matter in a counting problem? Give an original example where order matters and one where it does not.
- Explain in your own words why the number of arrangements of all n distinct objects is n!. Do not just state the formula — explain where each factor comes from.
- Why is 0! defined to be 1? Give two reasons or contexts where this definition is needed.
- What is the difference between P(n, k) and n^k? Describe a real situation that calls for each.
- When objects include repeated identical symbols, why must the count be divided? What error does the division correct?
- Explain why a circular arrangement of n objects has (n−1)! arrangements rather than n!.
- Describe the restriction-first method in your own words. Why is it usually better to handle restrictions before counting free choices?
- Explain the gap method. In what type of problem is it used? How does it guarantee the required separation?
- Explain the block method. In what type of problem is it used? Why must you also count the arrangements within the block?
- What is a derangement? Give an example with 3 or 4 objects.
Skill Practice
- Compute 6!
- Compute 9! / 6!
- Compute 7! / (3! · 4!)
- Simplify n! / (n − 1)!
- Without computing 15!, simplify 15! / 13!
- Show that (n+1)! = (n+1) · n!
- Compute P(8, 3)
- Compute P(12, 5)
- Compute P(7, 7)
- Simplify P(n, 2)
- A class of 30 elects president, VP, treasurer. How many outcomes?
- How many 4-letter arrangements from {A, B, C, D, E, F, G}, no repeats?
- How many 4-digit numbers from {1, 2, 3, 4, 5, 6, 7, 8, 9}, no repeats?
- Distinct arrangements of BANANA?
- Distinct arrangements of MISSISSIPPI?
- Distinct arrangements of PROBABILITY?
- Six people are seated in a row. Alex must sit in the first seat. How many arrangements are possible?
- Eight people are seated in a row. Two specific people must sit at the two ends (in either order). How many arrangements are possible?
- Five people are seated in a row. Two specific people must not sit adjacent to each other. How many valid arrangements are there?
- Using the letters {A, B, C, D, E, F}, how many 6-letter arrangements have A in the first position and F in the last position?
- Using digits {1, 2, 3, 4, 5, 6} without repetition, how many 4-digit numbers have an even digit in the first position?
- Seven distinct books are arranged on a shelf. Three specific books must appear together (as a block). How many arrangements are possible?
- Arrange the letters {A, E, I, B, C, D, F} in a row so that no two vowels (A, E, I) are adjacent. How many arrangements are possible?
- Six runners compete. How many different finishing orders are possible if a specific runner must finish in the top three?
- 5 people around a circular table
- 10 people around a circular table
- 8 keys on a flippable key ring
- 6 people, circular, two must not be adjacent
- Necklace with 8 distinct beads (flippable)
Real-World Applications
- Password Security. A password consists of 8 characters chosen from 26 lowercase letters and 10 digits (36 symbols), with repetition allowed.
a. How many possible passwords are there?
b. If the first character must be a letter, how many passwords are possible?
c. If no character may repeat, how many passwords are possible?
- Seating Chart. A teacher has 25 students and 25 desks in a row.
a. How many possible seating arrangements are there?
b. If two specific students must sit next to each other, how many valid arrangements are there?
c. If two specific students must not sit next to each other, how many valid arrangements are there?
- Scheduling. A project manager has 8 tasks to complete in sequence.
a. How many possible schedules (orderings of the tasks) are there?
b. If one critical task must be first and another must be last, how many valid schedules are there?
- DNA Sequences. DNA uses four bases: A, T, G, C.
a. How many distinct sequences of length 6 are possible, with repetition allowed?
b. How many 6-base sequences begin with the start codon ATG?
- Cryptography. A simple substitution cipher replaces each of the 26 letters with a different letter (a permutation of the alphabet).
a. How many distinct ciphers are possible?
b. A specific cipher must fix the letter E (map E to E). How many such ciphers are there?
Error Analysis
Each of the following solutions contains an error. Identify the error and explain how to correct it.
Problem 1
Circular seating of 4 people: 4! = 24
What is wrong? What is the correct answer?
Problem 2
Distinct arrangements of LEVEL: 5! = 120
What is wrong? What is the correct answer?
Problem 3
3-letter codes from {A, B, C, D, E}, first must be a vowel, no repeats: 2 · 5 · 5 = 50
What is wrong? What is the correct answer?
Problem 4
7 people in a row, X and Y must sit adjacent: treat as block → 6! = 720
What is wrong? What is the correct answer?
Problem 5
5 people in a row, two must not be adjacent: 5! − 4! = 120 − 24 = 96
What is wrong? What is the correct answer?
Chapter 3 Checkpoint
Chapter 3 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 3
Part A — Concepts
- Explain the difference between a permutation and a combination in your own words. Give an original example of each.
- A student says: "P(n, k) and n^k both count arrangements, so they should give the same answer." Explain carefully why this is wrong and when each formula applies.
- Explain why n! / (n₁! · n₂! · · · nr!) counts arrangements when some objects are identical.
Part B — Computation
- Compute P(9, 4).
- How many distinct arrangements of the letters in STATISTICS are there?
- Eight people are seated around a circular table. How many arrangements are possible?
Part C — Restricted Problems
- Ten people are in a line. Two specific people must not be adjacent. How many valid arrangements are there?
- Arrange the letters {B, C, D, F, A, E} in a row so that the two vowels (A and E) are not adjacent.
- Five people are seated around a circular table. Two specific people must sit adjacent to each other. How many valid arrangements are there?
Part D — Applications
- A company generates employee ID codes using 3 uppercase letters followed by 4 digits. Letters may repeat; digits may not repeat. How many distinct ID codes are possible?
- A competition assigns gold, silver, bronze, and honorable mention to 4 finalists chosen from 12 competitors. How many distinct outcomes are possible?
- A committee of 8 people is seated around a circular table. The chairperson must always occupy a fixed designated seat. How many distinct seating arrangements are possible for the remaining members?
Part E — Reasoning
- Prove or disprove: For all n ≥ 2, the number of circular arrangements of n people is less than the number of linear arrangements.
- How many arrangements of {1, 2, 3, 4, 5} have the property that 1 is not in the first position and 5 is not in the last position? (Use complement or casework reasoning. Answers may be placed in the answer key.)
Looking Ahead
Chapter 4: Combinations and Selections
Chapter 3 gave you the tools for ordered arrangements. Chapter 4 turns to unordered selections — situations where only the group itself matters, not the order in which its members are listed. We will develop the combination formula C(n, k) = n! / (k! · (n−k)!), explain why dividing by k! corrects the overcounting from order, and apply combinations to committees, groups, hands of cards, and restricted selections. Every idea in Chapter 4 is built directly on the permutation reasoning you have learned here.
MGU Library Connection
- Factorial and permutation formulas are summarized in the MGU Combinatorics Formula Sheet.
- Permutation reasoning is foundational to Probability and Statistics: counting ordered outcomes in sample spaces.
- Codes and cipher key-spaces are developed in the MGU Cryptography lessons.
- Ordered scheduling and optimization are developed in the MGU Operations Research lessons.
- The derangement formula and its connection to inclusion-exclusion will be fully developed in Chapter 7 of this book.
- Recurrence relations for factorial-like sequences are explored in Chapter 10 of this book.
- MGU Dictionary entries: permutation, factorial, circular permutation, derangement, restriction, block method, gap method.