Задача
COM-B2-M02-P014 Ровно \(k\) неподвижных точек
#14
★★★★☆ Уровень 4 из 5
Докажите, что число перестановок \(n\) элементов с ровно \(k\) неподвижными точками равно \(\binom nkD_{n-k}\).
Сначала выберите, какие точки будут неподвижными.
Выбираем \(k\) элементов, которые будут неподвижными: \(\binom nk\) способов. Остальные \(n-k\) элементов должны не иметь неподвижных точек среди своих позиций, иначе неподвижных точек было бы больше \(k\). Это можно сделать \(D_{n-k}\) способами. Получаем \(\binom nkD_{n-k}\).
Формула часто встречается в олимпиадных задачах с “ровно”.