Discrete Math › Section D · Counting › Topic D.8
Advanced counting: derangements and functions
Some counts are hard to make directly but easy to make by subtracting what you do not want. Inclusion-exclusion in its full form handles three classic problems: distributions with upper limits, derangements, and functions that hit every target.
Counting what goes wrong
Many counting questions come with a list of forbidden properties: no child gets more than six pens, nobody draws their own name, no worker is left without a task. Counting the good outcomes directly is awkward, because the restrictions interact. The strategy of this topic is to count all outcomes, then subtract the bad ones. Let \(A_i\) be the set of outcomes that break restriction \(i\). The good outcomes are those in none of the \(A_i\), and their number is the total minus \(|A_1 \cup A_2 \cup \cdots \cup A_n|\). That union is exactly what inclusion-exclusion, from "Overlaps and inclusion-exclusion", computes, provided the intersections are easy to count.
Inclusion-exclusion in full
For sets \(A_1, \ldots, A_n\) inside a universe \(U\), the number of elements in none of them is
with the signs alternating until the intersection of all \(n\) sets. Each sum runs over all choices of that many different sets, so the \(j\)-fold sum has \(\binom{n}{j}\) terms. The method pays off when the problem is symmetric: if every intersection of \(j\) sets has the same size \(s_j\), the \(j\)-th sum is simply \(\binom{n}{j}s_j\), and the whole count collapses to a short alternating sum. All three examples in this topic have that symmetry.
Worked example: upper limits on a distribution
Share 15 identical pens among 3 students so that nobody gets more than 6. 1. Without limits, stars and bars from "Counting multisets (stars and bars)" gives \(\binom{17}{2} = 136\). 2. Let \(A_i\) be the sharings where student \(i\) gets at least 7. Hand that student 7 first and share the other 8 freely: \(|A_i| = \binom{10}{2} = 45\). 3. Two students with at least 7 each: hand out 14, share 1: \(\binom{3}{2} = 3\) for each of the 3 pairs. 4. All three would need 21 pens, more than 15, so that intersection is empty. 5. Good sharings: \(136 - 3 \cdot 45 + 3 \cdot 3 - 0 = 10\). 6. Check by listing: (6, 6, 3) in 3 orders, (6, 5, 4) in 6, and (5, 5, 5) once, giving 10.
Derangements
A derangement of \(n\) objects is a permutation that moves every object: none stays in its own place. If 6 friends put their names in a hat for a gift exchange and each draws one, a draw where nobody gets their own name is a derangement. Let \(A_i\) be the permutations that fix object \(i\). Fixing any \(j\) chosen objects leaves \((n - j)!\) permutations of the rest, and there are \(\binom{n}{j}\) ways to choose them. Inclusion-exclusion gives the number of derangements:
The first values are \(D_1 = 0\), \(D_2 = 1\), \(D_3 = 2\), \(D_4 = 9\) and \(D_5 = 44\).
Worked example: the gift-exchange draw
How many of the draws among 6 friends give nobody their own name, and how likely is that? 1. Total draws: \(6! = 720\). 2. The terms \(\binom{6}{j}(6-j)!\) for \(j = 0\) to 6 are 720, 720, 360, 120, 30, 6 and 1. 3. Alternate the signs:
4. So \(D_6 = 265\), and the probability of a draw that works first time is \(\frac{265}{720} \approx 0.368\). 5. A computer check over all 720 permutations finds the same 265. Roughly 63% of the time at least one friend draws their own name and the hat must be passed round again.
The surprising limit
The fraction of permutations that are derangements is
These are the first terms of the series for \(e^{-1}\), so as \(n\) grows the fraction approaches \(\frac{1}{e} \approx 0.3679\). The convergence is very fast: \(\frac{265}{720} \approx 0.3681\) already. Remarkably, the answer hardly depends on \(n\): with 10 people or 10,000, the chance that nobody gets their own name is about 37%. In fact \(D_n\) is always the whole number nearest to \(\frac{n!}{e}\) for \(n \ge 1\), and \(\frac{720}{e} \approx 264.9\).
Counting onto functions
"The sum and product principles" showed that there are \(n^k\) functions from a \(k\)-element set \(A\) to an \(n\)-element set \(B\). A function is surjective, or onto, if every element of \(B\) is the image of something. Let \(A_i\) be the functions that miss element \(i\) of \(B\). Functions missing \(j\) chosen targets map into the other \(n - j\), so there are \((n - j)^k\) of them. Hence the number of surjections is
For example, from a 4-element set onto a 3-element set the surjections number
Worked example: no idle workers
A manager assigns 6 different tasks to 3 workers, every task to exactly one worker, so that each worker gets at least one task. How many assignments are there? 1. An assignment is a function from the 6 tasks to the 3 workers, and the condition says it is onto. 2. All functions: \(3^6 = 729\). 3. Missing one chosen worker: \(\binom{3}{1}2^6 = 192\). 4. Missing two chosen workers: \(\binom{3}{2}1^6 = 3\). Missing all three is impossible. 5. Surjections: \(729 - 192 + 3 = 540\). 6. Contrast with 6 identical tasks, where only the number per worker matters: stars and bars with at least one each gives \(\binom{5}{2} = 10\). Distinct objects into boxes means functions; identical objects means multisets.
Common mistakes to avoid
First, stopping inclusion-exclusion after the single sets: subtracting \(3 \cdot 45\) from 136 in the pens example gives 1, not 10. Second, forgetting that an intersection can be empty, or worse, using a negative number of leftover objects in a stars-and-bars formula. Third, confusing derangements, where nothing is fixed, with "not the identity", where at least one object moves. Fourth, counting surjections with \(P(n, k)\), which counts injections. Fifth, mixing up distinct and identical objects: tasks with names give functions, identical pens give multisets.
Key takeaways
To count outcomes with forbidden properties, subtract the union of the bad sets using full inclusion-exclusion, with alternating signs and \(\binom{n}{j}\) terms at stage \(j\). Upper limits in stars and bars are handled by handing out the excess first. Derangements number \(D_n = n!\sum_j \frac{(-1)^j}{j!}\), with \(D_6 = 265\), and make up about \(\frac{1}{e} \approx 37\%\) of permutations. Surjections from a \(k\)-set onto an \(n\)-set number \(\sum_j (-1)^j\binom{n}{j}(n-j)^k\). Decide first whether the objects are distinct or identical.
Flashcards
Flashcard
Good outcomes = total − |A₁ ∪ ... ∪ Aₙ|
Test your understanding
Question 1 of 5
Five friends draw names for a gift exchange. In how many of the 120 possible draws does nobody get their own name?
Question 2 of 5
How many functions from a 4-element set onto a 3-element set are there?
Question 3 of 5
In how many ways can 10 identical sweets be shared among 3 children so that no child gets more than 4?
Question 4 of 5
For large n, roughly what fraction of the permutations of n objects are derangements?
Question 5 of 5
Which method counts the ways to give 7 different books to 3 children so that each child gets at least one?
