Inclusion-Exclusion question A careless payroll clerk is placing employees’ paychecks into pre-labeled envelopes. The envelopes are sealed before the clerk realizes he didn’t match the names on the paychecks with the names on the envelopes. If there are seven employees, in how many ways could he have placed the paychecks into the envelopes so that exactly three employees receive the correct paycheck? Is it $6^4$?

Let $d_n$ be the number of derangements (permutations without fixed points) on $n$ points, that is $$ d_n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!}\right). $$ The number of permutations of $n$ elements having exactly $k$ fixed points is $$ \binom{n}{k} d_{n-k}. $$ The first factor gives the number of choices for the fixed points, and the second factor gives the number of choices for the other coordinates. The sequence $d_n$ starts (indexed from $0$) $$ 1, 0, 1, 2, 9, 44, 265, 1854, \ldots. $$ Therefore the number of permutations of $n = 7$ with $k = 0,\ldots,7$ fixed points is $$ 1854, 1855, 924, 315, 70, 21, 0, 1. $$