[Discrete Math & Precalculus ⑧] The Core of Permutations: Slot Placement, Together vs. Separated, Complementary Logic & Lexicographic Ranking

 

Foundational Algebra & Combinatorics · Concept Guide ⑧

The Core of Permutations: Slot Placement, Together vs. Separated & Lexicographic Order

Mastering $_n\mathrm{P}_r$, factorial mechanics, adjacent grouping vs. empty slot insertion, complementary counting, and 3-second lexicographic rank decoding.

🎯 [Permutations] Yul's 3 Golden Action Protocols
  • Visualize $_n\mathrm{P}_r$ as 'Filling Empty Slots', not abstract formulas: The multiplication rule of choosing among $n$ candidates for the 1st chair, $(n-1)$ for the 2nd, and so on across $r$ distinct slots defines the true foundation of permutations.
  • Separate adjacent conditions orthogonally (Block Grouping vs. Slot Insertion): Items that must stay together are tied into a single bundle with internal arrangements ($k!$). Items that cannot be adjacent must never be bundled; arrange other items first and insert the restricted items into the available outer and intermediate slots.
  • 'At least' signals Complementary Counting; Lexicographic Order relies on 'Block Accumulation': Subtract opposite events from the universal set, and trace dictionary order by locking the highest-order positions in factorial units ($4!, 3!, \dots$).

1. Permutations and Factorials: The Slot Placement Mechanism

Arranging $r$ distinct items chosen from $n$ distinct elements in an ordered sequence is called a permutation, denoted by $\mathbf{{}_n\mathrm{P}_r}$. It represents the fundamental application of the multiplication principle.

[Core Definition 1] Permutations and Factorials

• Slot Formula: $\mathbf{{}_n\mathrm{P}_r = n(n - 1)(n - 2) \cdots (n - r + 1)}$ (multiplying $r$ descending positive integers from $n$)
• Factorial ($n!$): The product of all positive integers from $1$ up to $n$ $\implies \mathbf{n! = n(n - 1) \cdots 2 \cdot 1}$
• Factorial Form: $\mathbf{{}_n\mathrm{P}_r = \dfrac{n!}{(n - r)!}$
• Definitional Invariants: $0! = 1$, $_n\mathrm{P}_0 = 1$, $_n\mathrm{P}_n = n!$

2. Two Essential Placement Protocols: Together (Grouping) vs. Separated (Slot Method)

Handling adjacency constraints determines problem difficulty. These two conditions require fundamentally opposite workflows.

📦 [Grouping] Adjacent Condition
[B1 B2 B3] (Treated as 1) G1 G2 G3 G4
5 Units Arranged ($5!$) $\times$ Internal Swap ($3!$)
📍 [Slot Method] Separated Condition
V G1 V G2 V G3 V G4 V
Girls First ($4!$) $\times$ Pick 3 Slots from 5 ($_5\mathrm{P}_3$)
▲ [Figure 2-1] Grouping Bundle vs. Slot Insertion Mechanics

✏️ [Practice Example 1] Adjacent vs. Separated Lineup

Three boys and four girls are to be arranged in a straight line. Find the number of arrangements such that:
(1) All three boys stand together.
(2) No two boys stand next to each other.

💡 Yul's Pro-Tip:
Never solve question (2) by subtracting the answer to (1) from the total arrangements! That misses the cases where exactly two boys stand together while the third stands apart. The separated condition demands that we place the 4 unrestricted girls first ($4!$), then assign the 3 boys into the 5 available border and intermediate slots ($_5\mathrm{P}_3$).
View Solution & Answer (Click)
(1) Treat 3 boys as 1 unit: 1 boy bundle + 4 girls = 5 units. Arrange units: $5! = 120$.
Internal arrangements within the boy bundle: $3! = 6$.
Total = $120 \times 6 = 720$.

(2) Arrange 4 girls first: $4! = 24$.
Choose 3 slots out of 5 for the boys: $_5\mathrm{P}_3 = 5 \times 4 \times 3 = 60$.
Total = $24 \times 60 = 1440$.
Answer: (1) 720 / (2) 1440
📝 [Diagnostic Check 1]

Two teachers and four students stand in a line. In how many ways can they stand such that the two teachers do not stand next to each other?

Check Answer
Arrange 4 students first: $4! = 24$.
Assign 2 teachers into 5 available slots: $_5\mathrm{P}_2 = 20$.
Total = $24 \times 20 = 480$.
Answer: 480

3. Alternating Lineups and Endpoint Fixed Constraints

Alternating patterns depend entirely on set sizes. Equal group sizes produce two symmetrical skeleton frameworks, whereas groups differing by 1 require the larger group to occupy both outer ends.

⚖️ [Equal Sizes: 3 Boys, 3 Girls]
B G B G B G
G B G B G B
Two Skeletons by Starting Element $\implies 2 \times (3! \times 3!)$
⚓ [Fixed Endpoints Condition]
[Boy Choice] Middle 4 Elements ($4!$) [Girl Choice]
End Candidates $(3 \times 3)$ $\times$ Left-Right Swap ($2!$) $\times$ Center $4!$
▲ [Figure 3-1] Dual Alternating Skeletons and Endpoint Fixed Slot Mechanism

✏️ [Practice Example 2] Alternating Lineup & End Constraints

Three boys and three girls stand in a line. Find the number of arrangements such that:
(1) Boys and girls stand alternately.
(2) A boy stands at one end and a girl stands at the other end.

💡 Yul's Pro-Tip:
• (1) With 3 boys and 3 girls, alternating lineups consist only of (BGBGBG) or (GBGBGB). Each skeleton evaluates to $3! \times 3!$.
• (2) Secure the two outer endpoints first! (Boy left, Girl right) or (Girl left, Boy right), then arrange the remaining 4 individuals in the center with $4!$.
View Solution & Answer (Click)
(1) Alternating Lineup:
• Pattern 1 (BGBGBG): Boys $3! = 6$, Girls $3! = 6 \implies 36$.
• Pattern 2 (GBGBGB): Girls $3! = 6$, Boys $3! = 6 \implies 36$.
Total = $36 + 36 = 72$.

(2) Boy and Girl at Opposite Ends:
• Choosing 1 boy for an end: 3 options; choosing 1 girl for the other end: 3 options.
• Swap endpoints (Left/Right): $2! = 2$.
• Arrange center 4 individuals: $4! = 24$.
Total = $(3 \times 3 \times 2) \times 24 = 18 \times 24 = 432$.
Answer: (1) 72 / (2) 432
📝 [Diagnostic Check 2]

Four boys and three girls stand in a line. In how many ways can they stand alternately?

Check Answer
Since sizes are 4 and 3, only the pattern (BGBGBGB) is valid.
Arrange 4 boys: $4! = 24$. Arrange 3 girls: $3! = 6$.
Total = $24 \times 6 = 144$.
Answer: 144

4. 'At Least' Constraints and Complementary Subtraction

Phrases such as 'at least one vowel at an end' indicate that direct counting requires too many case subdivisions. Transform the problem immediately using [Total Arrangements] - [Complementary Event].

Universal Set ($U$) All Arrangements ($n!$)
−
Complement ($A^c$) Both Ends Vowels
=
Target Event ($A$) At Least One End Consonant
▲ [Figure 4-1] Modeling 'At Least' via Universal Set ($U$) Minus Complement ($A^c$)

✏️ [Practice Example 3] 'At Least' in Character Arrangements

In how many ways can the 6 letters of the word $s, p, r, i, n, g$ be arranged in a line such that at least one end has a consonant?

💡 Yul's Pro-Tip:
The complement of 'at least one consonant at an end' is 'both ends are vowels'. However, there is only 1 vowel ($i$). It is physically impossible to place vowels at both ends! Always audit your element counts first: Vowels $\{i\}$ (1), Consonants $\{s, p, r, n, g\}$ (5).
View Solution & Answer (Click)
Step 1: Vowels = $\{i\}$ (1), Consonants = $\{s, p, r, n, g\}$ (5).
Step 2: Placing vowels at both ends is impossible since only 1 vowel exists (0 ways).
Step 3: Therefore, every valid arrangement naturally satisfies the condition: $6! = 720$.
Answer: 720
📝 [Diagnostic Check 3]

All letters of the word $f, r, i, e, n, d$ are arranged in a row. In how many arrangements is there at least one vowel at an end?

Check Answer
Vowels $\{i, e\}$ (2), Consonants $\{f, r, n, d\}$ (4). Total = $6! = 720$.
Complement (Both ends consonants): $_4\mathrm{P}_2 = 12$, Center 4: $4! = 24 \implies 12 \times 24 = 288$.
Valid = $720 - 288 = 432$.
Answer: 432

5. Lexicographic (Dictionary) Order and Rank Inversion

Lexicographic order problems pin down the highest-order prefix first and count possibilities in factorial blocks to narrow down the exact rank.

✏️ [Practice Example 4] Bidirectional Lexicographic Search

Using the 5 letters $A, B, C, D, E$ exactly once, 5-letter strings are arranged in alphabetical order:
(1) Find the position (rank) of the string $C E B D A$.
(2) Find the string in the $80^{\text{th}}$ position.

💡 Yul's Pro-Tip: Map Letters to Numbers (1, 2, 3, 4, 5)!
When alphabet sequences feel visually cluttered, replace each letter with its sequential rank: $A \to 1, B \to 2, C \to 3, D \to 4, E \to 5$! The string $C E B D A$ instantly transforms into the integer $35241$. The question becomes the intuitive task of finding the rank of $35241$ when numbers are listed in ascending order. Each fixed leading digit yields $4! = 24$ permutations. To locate the $80^{\text{th}}$ string, $24 \times 3 = 72$ instantly places it inside the block starting with $D$ ($4$).
View Solution & Answer (Click)
(1) Rank of $C E B D A$ (Number $35241$):
• Starting with $A$ ($1\square\square\square\square$): $4! = 24$
• Starting with $B$ ($2\square\square\square\square$): $4! = 24$ (Cumulative: 48)
• Starting with $C A$ ($31\square\square\square$): $3! = 6$
• Starting with $C B$ ($32\square\square\square$): $3! = 6$
• Starting with $C D$ ($34\square\square\square$): $3! = 6$ (Cumulative: $48 + 18 = 66$)
• Starting with $C E A$ ($351\square\square$): $2! = 2$ (Cumulative: 68)
• $69^{\text{th}}$ string: $C E B A D$ ($35214$)
• $70^{\text{th}}$ string: $C E B D A$ ($35241$)
Hence, $C E B D A$ is in the $70^{\text{th}}$ position.

(2) Finding the $80^{\text{th}}$ String:
• Strings starting with $A, B, C$: $24 \times 3 = 72$ completed.
• Target offset: $80 - 72 = 8$. Enter the $D$ ($4$) block:
• $D A \square\square\square$ ($41\square\square\square$): $3! = 6$ (Cumulative: $72 + 6 = 78$)
• Target offset: $80 - 78 = 2$. Enter the $D B$ ($42$) block:
• $79^{\text{th}}$: $D B A C E$ ($42135$)
• $80^{\text{th}}$: $D B A E C$ ($42153$)
Answer: (1) 70th / (2) DBAEC
📝 [Diagnostic Check 4]

Using each of the digits $1, 2, 3, 4, 5$ once, five-digit integers are written in ascending order. Find the $60^{\text{th}}$ integer.

Check Answer
• Leading digit $1$: $4! = 24$.
• Leading digit $2$: $4! = 24$ (Cumulative: 48).
• Leading digit $3$: $4! = 24$ (Cumulative: 72). The $60^{\text{th}}$ is in the $3$-block!
• Prefix $3 1$: $3! = 6$ (Cumulative: 54).
• Prefix $3 2$: $3! = 6$ (Cumulative: 60).
The $60^{\text{th}}$ is the largest number starting with $32$: $32541$.
Answer: 32541

6. Integer Digit Permutations: The Role of Zero & Divisibility Rules

When forming multi-digit integers, error rates peak when the "leading digit cannot be zero" restriction intersects with "endpoint divisibility conditions". Always apply the following standards.

① $\{1, 2, 3, 4, 5\}$ Set (Zero Excluded)

• Unconstrained Placement: All positions can take any remaining digit equally.
• Total 5-digit Integers: $5! = 120$
• Uniform Block Size: Fixing any leading digit leaves exactly $4! = 24$ integers in that block.

② $\{0, 1, 2, 3, 4\}$ Set (Zero Included)

• Leading Digit Restriction: The first slot cannot be $0$, leaving only 4 choices ($1, 2, 3, 4$).
• Total 5-digit Integers: $4 \times 4! = 96$
• Lexicographic Offset: No integer begins with $0$. The very first number is $10234$, with 24 integers per leading digit.

🎯 4 Core Divisibility Rules and Slot Allocations

• Divisible by 2 (Even): Units digit must belong to $\{0, 2, 4, 6, 8\}$.
※ Core Check: When $0$ is in the set, always split into [Units digit $= 0$] and [Units digit $\in \{2, 4, \dots\}$]. If the units digit is $0$, the leading digit is free from the zero restriction!

• Divisible by 3: The sum of all digits must be a multiple of 3.
Do not place slots first. Group digits by remainders modulo 3, choose subsets whose digit sums equal a multiple of 3, and only then permute ($n!$) within those subsets.

• Divisible by 4: The last two digits must form a multiple of 4 (or end in $00$).
List all valid two-digit endings (e.g., $04, 12, 20, 24, 32, 40 \dots$), fix each ending pair, and assign the remaining leading digits (distinguishing whether $0$ was used at the end).

• Divisible by 5: Units digit must belong to $\{0, 5\}$.
Set up two distinct skeletons: [Ends in $0$] and [Ends in $5$], and fill the leading slots independently.

EXAM PITFALL CHECK

⚠️ 3 Frequent Exam Traps in Digit Permutations

❌ Trap 1: "Failing to isolate zero when counting even numbers"
• Common Mistake: When forming 4-digit even numbers from $\{0, 1, 2, 3, 4\}$, assuming there are 3 choices for the units digit ($0, 2, 4$) and multiplying: $3 \times 3 \times \dots$
• Yul's Fix: If the units digit is $0$, the leading digit has 4 choices. If the units digit is $2$ or $4$, the leading digit has only 3 choices (excluding both $0$ and the chosen even digit). Always branch on whether $0$ occupies the units slot!
❌ Trap 2: "Rushing to fill slots when checking divisibility by 3"
• Common Mistake: Treating divisibility by 3 like even numbers and placing $3, 6, 9$ at the end.
• Yul's Fix: Divisibility by 3 is determined by the digit sum, not the final digit. Group digits by remainder modulo 3 ($\{0, 3\}, \{1, 4\}, \{2, 5\}$), pick a valid subset of numbers first, and then apply permutations.
❌ Trap 3: "Forgetting zero in secondary positions during reverse lexicographic search"
• Common Mistake: Finding the $50^{\text{th}}$ integer from $\{0, 1, 2, 3, 4\}$; after exhausting 48 numbers with prefixes $1$ and $2$, declaring the first number in the $3$-block to be $31240$.
• Yul's Fix: While $0$ cannot be the leading digit, it is the smallest available digit for all subsequent slots! The first number starting with $3$ is $30124$.
YUL'S PERSPECTIVE

Mathematical Mindset: A Word from Yul

"Mastering permutations is not about blindly plugging numbers into $_n\mathrm{P}_r$, but anchoring your reasoning to the most constrained slots first."

By mastering bundle grouping for adjacent items, empty slot allocation for separated elements, alternating frameworks, lexicographic block counting, and zero-boundary divisibility protocols, you have established the structural pillars of combinatorial reasoning. In our next session, we will tackle high-tier exam discriminators in [Advanced Combinatorics: Problem Set ⑧] 15 Killer Permutation Challenges.

Yul Math Lab · Daily Math Series Yul, Mathematics Educator & Researcher

Comments

Popular posts from this blog

Authentic Reference Models Beyond Basic Rulers

[Math Column]Studying Alongside Dedicated Peers: Becoming Each Other’s Lifelong Catalyst

[High School Math] Coordinate Geometry: 15 Essential Practice Problems on Section Formulas (Internal & External Division)