Solution
Keep or Swap
Show the problem again
Eight people each bring one gift. Afterwards every person ends up holding exactly one gift, and the only exchanges allowed are pairwise swaps: each person either keeps their own gift or swaps gifts with exactly one other person (who then holds theirs). No one takes part in more than one swap. How many different final assignments of gifts to people are possible (including the one where nobody swaps)? Give an integer.
Worked solution
**Answer: 764.** The outcomes are the involutions of an 8-element set: permutations made only of fixed points and 2-cycles. Let t(n) count them. Person n either keeps their gift (t(n − 1) ways for the others) or swaps with one of the other n − 1 people (then t(n − 2) ways for the rest). So t(n) = t(n − 1) + (n − 1) t(n − 2), with t(0) = t(1) = 1. This gives 1, 1, 2, 4, 10, 26, 76, 232, 764, so t(8) = 764. As a check by direct count: Σ_k 8! / (k! 2^k (8 − 2k)!) over k = 0..4 swaps is 1 + 28 + 210 + 420 + 105 = 764.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.