26-02 — Permutations

Phase: Combinatorics | Subject: 26-02 Prerequisites: 26-01-counting-principles.md Next subject: 26-03-combinations.md

Learning Objectives

By the end of this subject, you will be able to:

1. Define a permutation as an ordered arrangement of distinct objects
2. Compute $P(n, r) = \frac{n!}{(n-r)!}$ for permutations of $r$ from $n$
3. Count permutations with repeated elements: $\frac{n!}{n_1! n_2! \ldots n_k!}$
4. Solve circular permutation problems
5. Apply permutations to probability and combinatorics problems

Core Content

Definition and Notation

A permutation is an ordered arrangement of objects. Distinct orderings of the same objects count as different permutations.

Factorial: $n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$, with $0! = 1$.

Permutations of $n$ Distinct Objects

The number of ways to arrange $n$ distinct objects in a line is $n!$.

Example: Arrange letters A, B, C. $3! = 6$: ABC, ACB, BAC, BCA, CAB, CBA.

$r$-Permutations: $P(n, r)$

The number of ways to select and arrange $r$ objects from $n$ distinct objects (order matters):

$$P(n, r) = \frac{n!}{(n-r)!} = n \times (n-1) \times \cdots \times (n-r+1)$$

Derivation: $n$ choices for position 1, $(n-1)$ for position 2, ..., $(n-r+1)$ for position $r$. Multiply these $r$ terms.

Example: How many ways to award gold, silver, bronze from 10 athletes? $P(10, 3) = 10 \times 9 \times 8 = 720$.

Permutations with Repeated Elements

When some objects are identical, we overcount by the number of ways to rearrange the identical ones:

$$\frac{n!}{n_1! n_2! \ldots n_k!}$$

where $n_i$ is the number of copies of the $i$-th distinct element, and $\sum n_i = n$.

Example: Arrange the letters in MISSISSIPPI. Total: 11 letters. M=1, I=4, S=4, P=2. Count = $\frac{11!}{1!4!4!2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1152} = 34,650$.

Circular Permutations

Arranging $n$ distinct objects around a circle: $(n-1)!$ ways.

Reasoning: In a line, rotating everyone by one seat gives a different arrangement. Around a circle, rotations are considered the same. Fix one person to break symmetry, then arrange the remaining $n-1$ in $(n-1)!$ ways.

Example: Seat 5 people around a round table. $(5-1)! = 4! = 24$ arrangements.

⚠️ CRITICAL — If reflection is also considered identical (e.g., a necklace can be flipped), divide by 2: $\frac{(n-1)!}{2}$ for $n \geq 3$.

Permutations with Restrictions

• Objects together: Treat the group as a single block, permute the block and remaining objects, then permute within the block.
• Objects apart: Place the "separated" objects in gaps between the others.

Example: Arrange A, B, C, D where A and B sit together. Treat {A,B} as a block. Arrange 3 items (block, C, D): $3! = 6$. Arrange A and B within block: $2! = 2$. Total: $6 \times 2 = 12$.

Key Terms

• Permutation
• Factorial
• $r$-permutation
• Circular permutation
• Permutations with repetition

Worked Examples

Example 1: $P(n, r)$ Calculation

Compute $P(12, 4)$.

Solution: $P(12, 4) = \frac{12!}{(12-4)!} = \frac{12!}{8!} = 12 \times 11 \times 10 \times 9 = 11,880$.

Example 2: Repeated Letters

How many distinct arrangements of "BANANA"?

Solution: 6 letters: B=1, A=3, N=2. $\frac{6!}{1! 3! 2!} = \frac{720}{1 \times 6 \times 2} = \frac{720}{12} = 60$.

Example 3: Circular with Constraint

In how many ways can 4 men and 4 women sit at a round table with men and women alternating?

Solution: Fix one man's seat (circular symmetry). The remaining 3 men fill every other seat (3! ways). The 4 women fill the 4 gaps (4! ways). Total: $3! \times 4! = 6 \times 24 = 144$.

Quiz

Q1: What does the concept of Permutation primarily refer to in this subject?

A) A computational error related to Permutation B) A visual representation of Permutation C) A historical anecdote about Permutation D) The definition and application of Permutation

Correct: D)

• If you chose A: This is incorrect. Permutation is defined as: the definition and application of permutation. The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Permutation is defined as: the definition and application of permutation. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Permutation is defined as: the definition and application of permutation. The other options describe different aspects that are not the primary focus.
• If you chose D: Permutation is defined as: the definition and application of permutation. The other options describe different aspects that are not the primary focus. Correct!

Q2: Which of the following is the key formula discussed in this subject?

A) An unrelated formula from a different topic B) The inverse operation of the formula in question C) P(n, r) = \frac{n!}{(n-r)!} D) A simplified version of P(n, r) = \frac{n!}{(n-r)!}...

Correct: C)

• If you chose A: This is incorrect. The formula P(n, r) = \frac{n!}{(n-r)!} is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: This is incorrect. The formula P(n, r) = \frac{n!}{(n-r)!} is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: The formula P(n, r) = \frac{n!}{(n-r)!} is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose D: This is incorrect. The formula P(n, r) = \frac{n!}{(n-r)!} is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Factorial?

A) It is used to factorial in mathematical analysis B) It is used only in advanced research contexts C) It replaces all other methods in this domain D) It is primarily a historical notation system

Correct: A)

• If you chose A: Factorial serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose B: This is incorrect. Factorial serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: This is incorrect. Factorial serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: This is incorrect. Factorial serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Circular permutation is TRUE?

A) Circular permutation is a fundamental concept covered in this subject B) Circular permutation is an advanced topic beyond this subject's scope C) Circular permutation is mentioned only as a historical footnote D) Circular permutation is not related to this subject

Correct: A)

• If you chose A: Circular permutation is a fundamental concept covered in this subject. This subject covers Circular permutation as part of its core content. Correct!
• If you chose B: This is incorrect. Circular permutation is a fundamental concept covered in this subject. This subject covers Circular permutation as part of its core content.
• If you chose C: This is incorrect. Circular permutation is a fundamental concept covered in this subject. This subject covers Circular permutation as part of its core content.
• If you chose D: This is incorrect. Circular permutation is a fundamental concept covered in this subject. This subject covers Circular permutation as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) Repeated Letters B) A different result from a common mistake C) An unrelated numerical value D) The inverse of the correct answer

Correct: A)

• If you chose A: The worked examples show that the result is Repeated Letters. The other options represent common errors. Correct!
• If you chose B: This is incorrect. The worked examples show that the result is Repeated Letters. The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is Repeated Letters. The other options represent common errors.
• If you chose D: This is incorrect. The worked examples show that the result is Repeated Letters. The other options represent common errors.

Q6: How are Circular permutation and Permutations with repetition related?

A) Circular permutation and Permutations with repetition are completely unrelated topics B) Circular permutation is a special case of Permutations with repetition C) Circular permutation is the inverse of Permutations with repetition D) Circular permutation and Permutations with repetition are closely related concepts

Correct: D)

• If you chose A: This is incorrect. Both Circular permutation and Permutations with repetition are covered in this subject as interconnected topics.
• If you chose B: This is incorrect. Both Circular permutation and Permutations with repetition are covered in this subject as interconnected topics.
• If you chose C: This is incorrect. Both Circular permutation and Permutations with repetition are covered in this subject as interconnected topics.
• If you chose D: Both Circular permutation and Permutations with repetition are covered in this subject as interconnected topics. Correct!

Q7: What is a common pitfall when working with Definition And Notation?

A) Definition And Notation is always computed the same way in all contexts B) A common mistake is confusing Definition And Notation with a similar concept C) The main error with Definition And Notation is using it when it is not needed D) Definition And Notation has no common misconceptions

Correct: B)

• If you chose A: This is incorrect. Students often confuse Definition And Notation with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: Students often confuse Definition And Notation with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose C: This is incorrect. Students often confuse Definition And Notation with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: This is incorrect. Students often confuse Definition And Notation with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Permutations Of $N$ Distinct Objects?

A) Permutations Of $N$ Distinct Objects is not practically useful B) Use Permutations Of $N$ Distinct Objects only in pure mathematics contexts C) Avoid Permutations Of $N$ Distinct Objects unless explicitly instructed D) Apply Permutations Of $N$ Distinct Objects to solve problems in this subject's domain

Correct: D)

• If you chose A: This is incorrect. Permutations Of $N$ Distinct Objects is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. Permutations Of $N$ Distinct Objects is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: This is incorrect. Permutations Of $N$ Distinct Objects is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: Permutations Of $N$ Distinct Objects is a practical tool used throughout this subject to solve relevant problems. Correct!

Practice Problems

1. How many ways to arrange 7 books on a shelf?
   

   Click for answer

   $7! = 5040$.

2. From 15 runners, how many ways can the top 4 positions (1st-4th) be filled?
   

   Click for answer

   $P(15, 4) = 15 \times 14 \times 13 \times 12 = 32,760$.

3. How many distinct arrangements of "MISSISSIPPI"?
   

   Click for answer

   $11!/(4!4!2!) = 34,650$.

4. Seat 6 people around a circular table. How many arrangements?
   

   Click for answer

   $(6-1)! = 5! = 120$.

5. Arrange 5 students where Alice and Bob must sit together. How many ways?
   

   Click for answer

   Treat {Alice, Bob} as a block: 4 items → $4!$. Permute within block: $2!$. Total: $24 \times 2 = 48$.

Summary

Key takeaways:

• Permutations count ordered arrangements
• $n!$ for all $n$ distinct objects in a line
• $P(n, r) = n!/(n-r)!$ for ordered selections of $r$ from $n$
• Repeated objects: divide by factorial of each repetition count
• Circular: fix one object, arrange the rest: $(n-1)!$
• Blocks/constraints: treat grouped items as a single unit, then multiply by internal arrangements

Pitfalls

• Confusing permutations with combinations: "How many ways to choose a president, VP, and secretary from 10 people?" is a permutation ($P(10,3) = 720$) because the three positions are distinct — order matters. "How many ways to choose a 3-person committee?" is a combination ($\binom{10}{3} = 120$) because the committee is an unordered set. The key question is always: if you swap two selected people, do you get the same outcome or a different one?
• Forgetting to divide by repeated-element factorials: "How many arrangements of BANANA?" is NOT $6! = 720$. The three A's and two N's are identical, so swapping them produces the same arrangement. The correct count is $6!/(3! \cdot 2!) = 60$. Every set of identical items must be divided out — and this includes single-occurrence letters (1! = 1, which doesn't change the count but reminds you to check all letters).
• Using $n!$ for circular arrangements without fixing a reference: Around a table, rotations are considered the same arrangement because there's no distinguished "first seat." The count is $(n-1)!$, not $n!$. A common source of error: fixing one person breaks symmetry, but then forgetting that only the remaining $n-1$ need arranging. For necklaces (where reflection is also identical), divide further by 2: $(n-1)!/2$ for $n \geq 3$.
• Miscounting when objects must be together or apart: For "A and B must sit together," the block method works: treat {A,B} as one unit, arrange $n-1$ items, then permute within the block. But the error comes when additional constraints interact — if multiple pairs must be together (e.g., A-B together AND C-D together), treat each pair as a separate block. For "A and B must be separated," the gap method (place A and B in gaps between the others) is safer than subtracting invalid arrangements.
• Applying the permutation formula to problems where items are not all distinct: $P(n,r) = n!/(n-r)!$ assumes all $n$ items are distinguishable. If you're selecting from a multiset (e.g., letters from "MISSISSIPPI"), the simple $P(n,r)$ formula overcounts because identical items produce identical ordered selections. In such cases, either enumerate cases by distinctness pattern or use generating functions.

Next Steps

Next up: 26-03-combinations.md — unordered selections, binomial coefficients, and the relationship between permutations and combinations.