Clear Notion
Login

Concepts

Read through concept notes with worked explanations and diagrams, chapter by chapter.

Concept 06 / 09Permutations and Combinations

Derangements and the Inclusion-Exclusion Principle in Counting

Counting with inclusion-exclusion over properties, the derangement formula D(n) = n! (1 - 1/1! + 1/2! - ... ), its recurrence, partial derangements (exactly k objects in place), and the limit D(n)/n! approaching 1/e.

Inclusion-exclusion counts the objects with none of several properties. If A1,…,AmA_{1}, \ldots, A_{m} are the sets of objects having properties 1,…,m1, \ldots, m, then the number with none of the properties is N−∑∣Ai∣+∑∣Ai∩Aj∣−∑∣Ai∩Aj∩Ak∣+⋯+(−1)m∣A1∩⋯∩Am∣N - \sum|A_{i}| + \sum|A_{i} \cap A_{j}| - \sum|A_{i} \cap A_{j} \cap A_{k}| + \cdots + (-1)^{m}|A_{1} \cap \cdots \cap A_{m}|. Each object with exactly t≥1t \ge 1 properties is counted 1−(t1)+(t2)−⋯=(1−1)t=01 - \binom{t}{1} + \binom{t}{2} - \cdots = (1 - 1)^{t} = 0 times, while objects with no property are counted once. The method is powerful when the intersections are easy to count, which usually happens because of symmetry: every intersection of kk sets has the same size. Derangements. A derangement is a permutation in which no object is in its original position: letters in wrongly addressed envelopes, hats returned to the wrong owners, and so on. Let AiA_{i} be the arrangements with object ii in its own place. Fixing kk specific objects leaves (n−k)!(n - k)! arrangements, and there are (nk)\binom{n}{k} ways to choose which kk. So Dn=∑k=0n(−1)k(nk)(n−k)!=n!(1−11!+12!−13!+⋯+(−1)nn!)D_{n} = \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n - k)! = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^{n}}{n!}\right). Small values are worth memorising: D1=0D_{1} = 0, D2=1D_{2} = 1, D3=2D_{3} = 2, D4=9D_{4} = 9, D5=44D_{5} = 44, D6=265D_{6} = 265. Recurrence: Dn=(n−1)(Dn−1+Dn−2)D_{n} = (n - 1)(D_{n-1} + D_{n-2}). Reason: object 11 goes to some position j≠1j \neq 1 (n−1n - 1 choices). Either object jj goes to position 11 (a swap), leaving a derangement of the other n−2n - 2 objects (Dn−2D_{n-2} ways), or it does not, which is equivalent to deranging n−1n - 1 objects where jj is forbidden from position 11 (Dn−1D_{n-1} ways). Another form: Dn=nDn−1+(−1)nD_{n} = nD_{n-1} + (-1)^{n}. The limit: the series in brackets is the start of the expansion of e−1e^{-1}, so Dnn!→1e≈0.368\frac{D_{n}}{n!} \to \frac{1}{e} \approx 0.368. For n≥1n \ge 1, DnD_{n} is the integer nearest to n!e\frac{n!}{e}. So the probability that a random permutation has no fixed point is about 37%37\%, almost independent of nn. Partial derangements. The number of permutations of nn objects with exactly kk objects in their original places is (nk)Dn−k\binom{n}{k}D_{n-k}: choose which kk are fixed, then derange the rest. 'At least kk in place' requires summing, or using the complement. Other inclusion-exclusion applications: onto functions (see the Functions chapter), integers not divisible by any of a set of primes (leading to Euler's totient ϕ(n)=n∏(1−1p)\phi(n) = n\prod(1 - \frac{1}{p})), arrangements with forbidden adjacent pairs, and seating problems where certain couples must not sit together. Key Takeaways: - None of the properties: N−S1+S2−S3+⋯N - S_{1} + S_{2} - S_{3} + \cdots, where SkS_{k} sums the sizes of the kk-fold intersections. - Dn=n!∑k=0n(−1)kk!D_{n} = n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}; Dn=(n−1)(Dn−1+Dn−2)D_{n} = (n - 1)(D_{n-1} + D_{n-2}). - D2,D3,D4,D5,D6=1,2,9,44,265D_{2}, D_{3}, D_{4}, D_{5}, D_{6} = 1, 2, 9, 44, 265. - Exactly kk fixed: (nk)Dn−k\binom{n}{k}D_{n-k}. - DnD_{n} is the integer nearest to n!e\frac{n!}{e}. - Euler's totient: ϕ(n)=n∏p∣n(1−1p)\phi(n) = n\prod_{p \mid n}(1 - \frac{1}{p}). - Pitfall: 'exactly kk correct' computed as (nk)(n−k)!\binom{n}{k}(n - k)!, which ignores that the rest must all be wrong. Brain-Teaser 1: 55 letters are placed at random in 55 addressed envelopes. In how many ways are exactly 22 letters in the correct envelopes? At least one in the correct envelope? Solution: Exactly 22 correct: choose the correct pair in (52)=10\binom{5}{2} = 10 ways, and the other 33 must all be wrong: D3=2D_{3} = 2. Total 2020. At least one correct: 5!−D5=120−44=765! - D_{5} = 120 - 44 = 76. As a check, the counts with exactly 0,1,2,3,4,50, 1, 2, 3, 4, 5 correct are 4444, (51)D4=45\binom{5}{1}D_{4} = 45, 2020, (53)D2=10\binom{5}{3}D_{2} = 10, 00 (four correct forces the fifth to be correct) and 11; they add to 120120. Brain-Teaser 2: How many arrangements of 1,2,…,61, 2, \ldots, 6 have no even number in its own position (odd numbers may be anywhere)? Solution: Only the three even numbers have forbidden positions. Let AiA_{i} be arrangements with the even number ii in position ii. By inclusion-exclusion, 6!−(31)5!+(32)4!−(33)3!=720−360+72−6=4266! - \binom{3}{1}5! + \binom{3}{2}4! - \binom{3}{3}3! = 720 - 360 + 72 - 6 = 426. This is not D6D_{6}, because only some of the objects are restricted. Inclusion-exclusion adapts naturally; the derangement formula is just the special case where every object is restricted. Brain-Teaser 3: Using the recurrence, find D7D_{7}, and estimate it using ee. Solution: D7=6(D6+D5)=6(265+44)=1854D_{7} = 6(D_{6} + D_{5}) = 6(265 + 44) = 1854. Alternatively D7=7D6−1=1855−1=1854D_{7} = 7D_{6} - 1 = 1855 - 1 = 1854. Estimate: 7!e=50402.71828≈1854.1\frac{7!}{e} = \frac{5040}{2.71828} \approx 1854.1, whose nearest integer is 18541854. The two recurrences and the n!e\frac{n!}{e} approximation form a triple check that is useful under exam conditions.