Problem
COM-B2-M02-P018 First \(r\) Not Fixed
#18
★★★★★ Level 5 of 5
Prove that the number of permutations of \(n\) elements in which elements \(1,2,\ldots,r\) are not fixed is \(\sum_{i=0}^{r}(-1)^i\binom ri(n-i)!\).
There are only \(r\) forbidden events.
Let \(A_j\) be the event that element \(j\) is fixed, for \(j=1,\ldots,r\). If \(i\) such events are chosen, then \(i\) elements are fixed and the remaining \(n-i\) can be permuted in \((n-i)!\) ways. By inclusion-exclusion, the number of permutations avoiding these \(r\) events is \(\sum_{i=0}^{r}(-1)^i\binom ri(n-i)!\).
This generalises partial derangements.