Задача
COM-B2-M02-P018 Первые \(r\) не на местах
#18
★★★★★ Уровень 5 из 5
Докажите, что число перестановок \(n\) элементов, в которых элементы \(1,2,\ldots,r\) не стоят на своих местах, равно \(\sum_{i=0}^{r}(-1)^i\binom ri(n-i)!\).
Есть только \(r\) запрещённых событий.
Пусть \(A_j\) — событие, что элемент \(j\) стоит на своём месте, для \(j=1,\ldots,r\). Если выбраны \(i\) таких событий, то \(i\) элементов фиксированы, а остальные \(n-i\) можно переставить \((n-i)!\) способами. По включениям-исключениям число перестановок без этих \(r\) событий равно \(\sum_{i=0}^{r}(-1)^i\binom ri(n-i)!\).
Это обобщает частичные беспорядки.