Explanation
Derangements Dₙ = n!(1 − 1/1! + 1/2! − … +…
A derangement puts every item in a wrong place: no letter in its own envelope. The count comes from inclusion–exclusion.
Learn the first five: zero, one, two, nine, forty-four.
Derangements Dₙ = n!(1 − 1/1! + 1/2! − … + (−1)ⁿ/n!) · D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9, D₅ = 44
N identical things into r boxes
Identical objects into different boxes is stars and bars: n stars and r minus one bars, so n plus r minus one choose r minus one. If every box needs at least one, it becomes n minus one choose r minus one.
n identical things into r boxes: C(n + r − 1, r − 1) · none empty: C(n − 1, r − 1)
N distinct things into r boxes
Distinct objects into distinct boxes: each object chooses a box, so r to the n. To keep every box non-empty, subtract the cases that miss a box, add back the double misses, and so on.
n distinct things into r boxes: rⁿ · none empty: rⁿ − C(r, 1)(r − 1)ⁿ + C(r, 2)(r − 2)ⁿ − …
2n distinct things into 2 equal groups
Splitting into equal groups: divide by the factorials of the group sizes, and also by the number of equal groups, because swapping them changes nothing. If the groups have names, like teams A and B, don't divide by that.
2n distinct things into 2 equal groups: (2n)!/(2! (n!)²) · named groups: drop the 2!
Divisors of N = pᵃ qᵇ rᶜ
To count divisors, write the number as a product of prime powers. Each prime can appear zero up to a times, so the count is a plus one times b plus one, and so on.
Divisors of N = pᵃ qᵇ rᶜ: (a + 1)(b + 1)(c + 1)
Worked example
10 identical sweets among 3 children, each child getting at least one. Give each child one sweet first, then share the other 7 freely: C(7 + 2, 2) = C(9, 2) = 36.