Day 48 — Permutations

Day 48 — Permutations

Stage V · concept day
Goal: Count ordered arrangements: \(n!\), \(P(n,k)\), with/without repetition, circular permutations, multiset permutations, and derangements with full formulas.

Why this matters

Whenever order matters—password characters in sequence, ranking candidates, scheduling jobs in a queue, assigning distinct keys to slots—you are counting permutations (or words over an alphabet). Combinations (Day 49) drop order; today you keep it. Derangements answer “hat check” and “nobody gets their own ID” problems that reappear in hashing and matching.

Theory

Factorial

For integer \(n\ge 0\),

\[ n! = n\cdot(n-1)\cdots 1,\qquad 0! := 1. \]

Why \(0!=1\): one empty arrangement of zero objects (empty product). Needed so \(\binom{n}{0}=1\) and \(P(n,0)=1\).

Recurrence: \(n! = n\cdot(n-1)!\) for \(n\ge 1\).

Permutations of \(n\) distinct objects

Number of ways to order \(n\) distinct objects in a line:

\[ n!. \]

Story: \(n\) choices for position 1, \(n-1\) for position 2, …, \(1\) for the last (product rule).

\(k\)-permutations

The number of injective sequences of length \(k\) from an \(n\)-set (\(0\le k\le n\)), order matters, no repetition:

\[ P(n,k) = n^{\underline{k}} = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}. \]

Story: fill \(k\) ordered slots without reuse. Equivalent: number of injections from a labeled \(k\)-set into an \(n\)-set.

Edge cases: \(P(n,0)=1\); \(P(n,n)=n!\); \(P(n,k)=0\) if \(k>n\) (no-repetition model).

Bridge to combinations (preview):

\[ P(n,k) = \binom{n}{k}\, k!, \]

because choose the \(k\) elements unordered, then order them in \(k!\) ways.

With repetition allowed

Sequences of length \(k\) from \(n\) types, repetition allowed (words of length \(k\) over alphabet size \(n\)):

\[ n^k. \]

Product rule: \(n\) choices each of \(k\) positions. This is not \(P(n,k)\).
Interpretation: all functions from a \(k\)-set to an \(n\)-set.

Multiset permutations

If objects are not all distinct—multiset with counts \(n_1,\ldots,n_m\) totaling \(n\)—the number of distinct linear arrangements is

\[ \frac{n!}{n_1!\,n_2!\cdots n_m!}. \]

Story: if all were distinct you would have \(n!\); for each type \(i\), the \(n_i!\) internal swaps of identical copies look the same, so divide.

Circular permutations

Arrangements of \(n\) distinct people around a round table, where rotations of the same relative order are identical:

\[ (n-1)!. \]

Story: fix one person’s position (break rotational symmetry), arrange the other \(n-1\) people in the remaining seats: \((n-1)!\).

Equivalently: \(n!\) linear arrangements, identify those that differ by rotation ( \(n\) per class) → \(n!/n=(n-1)!\).

Reflections: if the table has no distinguished direction (necklace that can flip), further identify reflections → \(\frac{(n-1)!}{2}\) for \(n\ge 3\) (only when the problem says flips count as the same).

Numbered seats (chairs labeled): use \(n!\), not \((n-1)!\)—labels break rotational symmetry.

Derangements

A derangement of \(n\) objects is a permutation \(\pi\) with no fixed points: \(\pi(i)\neq i\) for all \(i\).

Notation: \(!n\) or \(d(n)\) or \(D_n\).

Exact formula (inclusion–exclusion)

Let \(A_i\) be the set of permutations that fix \(i\). Then permutations with at least one fixed point are \(\bigcup A_i\), and derangements are the complement:

\[ !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. \]

Derivation sketch. By IE,

\[ \Bigl|\bigcap_i \overline{A_i}\Bigr| = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n\binom{n}{n}0! = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}, \]

since \(\binom{n}{k}(n-k)! = n!/k!\).

Approximation

\[ !n = \frac{n!}{e} \text{ rounded to nearest integer for } n\ge 1 \]

(more precisely \(!n = \bigl\lfloor n!/e + 1/2\bigr\rfloor\) for \(n\neq 0\)). As \(n\to\infty\), \(!n / n! \to 1/e \approx 0.3679\)—about \(37\%\) of permutations are derangements.

Recurrences (optional awareness)

\[ !n = (n-1)\bigl[!(n-1)+!(n-2)\bigr],\qquad !0=1,\; !1=0. \]

Also \(!n = n\cdot!(n-1)+(-1)^n\).

Relation to functions

Object	Count
All functions \([k]\to[n]\)	\(n^k\)
Injections \([k]\to[n]\)	\(P(n,k)\)
Bijections \([n]\to[n]\)	\(n!\)
Derangements of \([n]\)	\(!n\)

Worked examples

Example 1 — Full permutations

Line up 5 distinct books: \(5!=120\).

Example 2 — \(P(n,k)\)

From 10 people, choose president, VP, treasurer (roles different): \(P(10,3)=10\cdot 9\cdot 8=720\).
Unordered committee of 3: \(\binom{10}{3}=120\) (Day 49).

Example 3 — Passwords without repeated characters

Length-4 from 26 lowercase, no repeat: \(P(26,4)=26\cdot 25\cdot 24\cdot 23\).
With repetition: \(26^4\).

Example 4 — Multiset

Rearrangements of SUCCESS: S×3, C×2, E, U:

\[ \frac{7!}{3!\,2!} = \frac{5040}{12} = 420. \]

Example 5 — Partial with restriction

3-digit numbers, distinct digits, no leading zero: \(9\cdot 9\cdot 8=648\).

Example 6 — Circular

6 people around a table, rotations same: \((6-1)! = 120\).
If chairs are numbered: \(6!=720\).

Example 7 — Sequential assignment

4 distinct tasks to 4 workers, one each: \(4!\).
4 distinct tasks to 10 workers, at most one each: \(P(10,4)\).

Example 8 — Comparing models

From \(\{1,2,3,4\}\):

Object	Count	Formula
Length-2 sequences, rep OK	16	\(4^2\)
Length-2 sequences, no rep	12	\(P(4,2)\)
Unordered 2-subsets	6	\(\binom{4}{2}\)

Example 9 — Complement + permutations

Anagrams of MATH with A not at the end: total \(4!=24\); end with A: \(3!=6\); so \(24-6=18\).

Example 10 — Derangement of 3

Permutations of \(\{1,2,3\}\): \(6\) total. Fixed-point-free: \((123)\mapsto(2,3,1)\) and \((3,1,2)\) only. So \(!3=2\).
Formula: \(3!(1-1+1/2-1/6)=6\cdot(1/3)=2\).

Example 11 — Derangement of 4

\(!4 = 24(1-1+1/2-1/6+1/24)=24\cdot(9/24)=9\).
List types: 2-cycles double (9 of form \((ab)(cd)\) and 4-cycles with no fixed points: actually \(!4=9\)).

Example 12 — Circular with adjacency

\(n=5\) people, A and B must sit together (rotations identical): glue AB as a block (2 internal orders), arrange block + 3 others circularly: \(2\cdot 4! / 5\)? Better: fix one other person C, or: treat block as one, circular of 4 entities: \(2\cdot(4-1)! = 2\cdot 6=12\). Wait carefully: circular of 4 units = \(3!\), times \(2\) for AB/BA: \(2\cdot 3!=12\).
Alternative: linear glue then divide by rotation carefully—stick to fix-one method when unsure.

Example 13 — Seating row with adjacency

5 people in a row, A and B adjacent: glue → \(2\cdot 4!=48\). Not adjacent: \(5!-48=72\).

Example 14 — \(P\) recurrence

Prove \(P(n,k)=n\,P(n-1,k-1)\) for \(k\ge 1\): choose image of first slot (\(n\) ways), inject the rest into remaining \(n-1\) elements: \(P(n-1,k-1)\).

Example 15 — Words with/without order

How many ways to award gold and silver (distinct) from 20 athletes? \(P(20,2)=20\cdot 19\).
How many ways to pick 2 athletes for a two-person team with no roles? \(\binom{20}{2}\).

Exercises

Solve by hand. Name the model (\(n!\), \(P(n,k)\), \(n^k\), multiset, circular, derangement).

1. Compute \(P(7,3)\), \(P(7,7)\), \(P(7,0)\), and \(7!\).
   
2. Award gold/silver/bronze to 12 runners (no ties).
   
3. Length-5 passwords from 10 digits, no digit repeated; with repetition.
   
4. Distinct rearrangements of MISSISSIPPI.
   
5. Distinct rearrangements of LEVEL.
   
6. Circular arrangements of 8 distinct beads (rotations same; flips different).
   
7. Same beads if flips (necklace) count as identical.
   
8. 4-digit numbers with distinct digits (leading zero allowed as digit string vs as number—state both).
   
9. Injections from \(\{1,2,3\}\) into \(\{1,\ldots,10\}\).
   
10. Is \(P(n,k)=P(n,n-k)\)? Prove or counterexample.
    
11. Prove \(P(n,k)=n!/(n-k)!\) from the falling factorial definition.
    
12. \(!5\) by the sum formula; compare to \(\mathrm{round}(120/e)\).
    
13. \(!6\) by formula.
    
14. Probability a random permutation of \(n\) is a derangement (limit as \(n\to\infty\)).
    
15. Seating 6 in a row: A,B adjacent; A,B not adjacent.
    
16. Circular 7 with two particular people together.
    
17. Prove \(P(n,k)=n\,P(n-1,k-1)\) combinatorially.
    
18. How many ways to choose president and distinct VP from 20?
    
19. Words of length 4 from 10 symbols, no repetition.
    
20. Multiset rearrangements of BOOKKEEPER.
    
21. Compare \(5^3\) vs \(P(5,3)\) with interpretations.
    
22. Order \(n\) distinct deploy steps on one pipeline.
    
23. Derangements of 4 by classifying cycle types (optional).
    
24. Functions \([3]\to[5]\) vs injections \([3]\to[5]\).
    
25. Challenge: number of permutations of \([n]\) with exactly \(k\) fixed points: \(\binom{n}{k}\cdot !(n-k)\).

CS connection

• Unique IDs / nonces: ordered selections without replacement from a keyspace.
  
• Scheduling / priority queues: permutations of tasks.
  
• Password entropy with no-repeat policies: \(P(|\Sigma|,k)\) vs \(|\Sigma|^k\).
  
• Shuffles & randomness tests: \(n!\) of a deck; derangement probability \(\to 1/e\) in “secret santa” algorithms.
  
• Compiler / register assignment lite: injectives map temps to registers (\(P\)).

Common pitfalls

Pitfall	What to do instead
Using \(n!\) when only \(k\) positions filled	Use \(P(n,k)\)
Using \(P(n,k)\) when repetition allowed	Use \(n^k\)
Circular vs linear confusion	Ask: do rotations look the same?
Forgetting to divide for identical letters	Multiset formula
\(0!\) treated as \(0\)	\(0!=1\)
Derangement \(\approx n!/e\) without rounding note	Exact sum exists
Treating roles as unordered	\(P(n,k)\) vs \(\binom{n}{k}\)

Checkpoint

• Write \(P(n,k)\) two ways (product and factorial ratio)
  
• Circular: \((n-1)!\) with a one-line story
  
• Multiset permutation formula
  
• \(!n\) exact formula and \(\approx n!/e\)
  
• Compute \(!3,!4\) cold
  
• Exercises 1–15 with model names
  
• Explain \(P(n,k)=\binom{n}{k}k!\) in words

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

1. \(P(7,3)=210\), \(P(7,7)=5040\), \(P(7,0)=1\), \(7!=5040\).
   
2. \(P(12,3)=1320\).
   
3. MISSISSIPPI: \(11!/(4!4!2!)=34650\).
   
4. LEVEL: \(5!/(2!2!)=30\).
   
5. False: \(P(5,2)=20\neq 60=P(5,3)\).
   
6. \(!5=44\); \(120/e\approx 44.145\).
   
7. Exactly \(k\) fixed: choose them \(\binom{n}{k}\), derange the rest.

Deepening notes

Derangement inclusion–exclusion expanded

\(U=\) all \(n!\) permutations. \(A_i=\) fix \(i\). For a set \(I\) of \(r\) indices, \(|\cap_{i\in I}A_i|=(n-r)!\). There are \(\binom{n}{r}\) such \(I\). IE for none of the \(A_i\):

\[ !n=\sum_{r=0}^{n}(-1)^r\binom{n}{r}(n-r)! = n!\sum_{r=0}^{n}\frac{(-1)^r}{r!}. \]

Circular with reflections

If the problem is a necklace that can flip, Burnside or divide by \(2\) for \(n\ge 3\) when no symmetry issues—only when stated. Default banquet problem: rotations only ⇒ \((n-1)!\).

Extra drills

D1. \(P(15,2)\).
D2. Words length 3 no rep from 8 letters.
D3. PEPPER rearrangements.
D4. Circular 10.
D5. \(!6\) and \(!7\).
D6. Seating 8 row, 3 particular together as a block.
D7. Injections \([4]\to[9]\).
D8. Exactly 2 fixed points among \(S_5\): \(\binom{5}{2}!3\).

Flash

\(P(n,k)=n!/(n-k)!\);\(n^k\) with rep;\((n-1)!\) circular;\(!n\approx n!/e\).

Tomorrow

Day 49 — Combinations: unordered selections \(\binom{n}{k}\), symmetry, grid paths, committees, and combinations with repetition (stars-and-bars preview).