[Discrete Math & Precalculus ⑧] The Core of Permutations: Slot Placement, Together vs. Separated, Complementary Logic & Lexicographic Ranking
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.
- 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.
• 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.
✏️ [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.
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)
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
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
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.
✏️ [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.
• (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)
• 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
Four boys and three girls stand in a line. In how many ways can they stand alternately?
Check Answer
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].
✏️ [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?
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 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
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
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.
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)
• 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
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 $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.
• 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.
• 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.
• 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.
⚠️ 3 Frequent Exam Traps in Digit Permutations
• 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!
• 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.
• 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$.

Comments
Post a Comment