Derangements & counting surjections
A derangement is a permutation leaving nothing in its own place, and Dₙ = n!Σ_{k=0}^{n}(−1)^k/k! — which is astonishingly close to n!/e, so about 37% of permutations are derangements regardless of n. Surjections are counted by the same inclusion–exclusion machinery: Σ(−1)^k C(m,k)(m−k)ⁿ functions from an n-set onto an m-set.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Set up the excluded propertiesFor derangements, Aᵢ is the set of permutations fixing element i. You want the complement of the union.
- Compute the intersection sizesPermutations fixing a specified set of k elements number (n−k)!, and there are C(n,k) such sets.
- Assemble the alternating sumDₙ = Σ(−1)^k C(n,k)(n−k)! = n!Σ(−1)^k/k!.
- Use the recurrence for hand computationDₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂), with D₁ = 0 and D₂ = 1.
Worked example
Compute D₄, the number of derangements of 4 objects.
- D₄ = 4!(1 − 1/1! + 1/2! − 1/3! + 1/4!).
- = 24(1 − 1 + 0.5 − 0.16667 + 0.041667).
- = 24 × 0.375.
- Check with the recurrence: D₃ = 2, D₂ = 1, so D₄ = 3(2 + 1) = 9 ✓.
Answer. D₄ = 9 — so 9 of the 24 permutations of four objects leave nothing fixed.
Where marks get dropped
These are the specific errors that cost credit on derangements & counting surjections questions — QED's rubric penalises each of them separately.
- Confusing derangements with permutations having exactly one fixed point. The latter is C(n,1)Dₙ₋₁.
- Using the surjection formula when the codomain is larger than the domain. Then there are no surjections at all.
- Forgetting the alternating signs, which turns inclusion–exclusion into a plain sum and vastly overcounts.
Practise this until it is automatic
Unlimited fresh questions
QED generates new derangements & counting surjections problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Combinatorics mastery is tracked so you know when this is exam-ready.
Derangements & counting surjections — frequently asked questions
Why is Dₙ ≈ n!/e?
Because Σ(−1)^k/k! is the Taylor series for e^(−1), truncated at n. Convergence is so fast that Dₙ is the nearest integer to n!/e for every n ≥ 1.
How many surjections from a 5-set onto a 3-set?
3⁵ − 3·2⁵ + 3·1⁵ = 243 − 96 + 3 = 150, equivalently 3!·S(5,3) = 6 × 25.
What is the hat-check problem?
The classic derangement story: n people leave hats and get one back at random. The probability nobody gets their own is Dₙ/n! ≈ 1/e ≈ 0.368.
The rest of Combinatorics
Counting principles, permutations, combinations. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Sum & product rules
- 2Permutations & combinations
- 3Binomial theorem & Pascal’s triangle
- 4The pigeonhole principle
- 5Inclusion–exclusion
- 6Counting with repetition (stars & bars)
- 7Derangements & counting surjections
- 8Double counting & bijective proofs
- 9Setting up & solving counting recurrences
- 10Generating functions — an introduction
- 11Multinomial coefficients & repeated items
- 12Hockey stick & Vandermonde identities
- 13Catalan numbers & lattice-path counting
Ready to make derangements & counting surjections exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →