Частный случай теоремы о включениях и исключениях
В некоторых случаях количество объектов, обладающих определенным набором свойств, зависит только от числа этих свойств. Тогда формула для подсчета числа объектов, не обладающих ни одним из выделенных свойств, упрощается.
При произвольном n имеем:
В последнем примере предыдущего параграфа мы использовали этот частный случай главной теоремы комбинаторики. В общем случае при перестановке n предметов количество расстановок, при которых ни один предмет не находится на своем месте:
(10)
Полученное значение иногда называют формулой полного беспорядка или субфакториалом. Субфакториал можно представить и так:
где выражение в [...] стремится к при неограниченном возрастании n.
Субфакториал имеет свойства, похожие на свойства обычного факториала. Например,
n! = (n - 1)[(n - 1)! + (n - 2)!] - для обычного факториала,
- для субфакториала.
Субфакториалы легко вычисляются по формуле
Приведем некоторые начальные значения субфакториалов:
Упражнения
1. Вычислите значения субфакториалов для n = 10, 11, 12.
2. Имеется 6 различных предметов. В каком числе перестановок ровно 2 предмета остаются на своих местах, а остальные на чужих?
3. Имеется 10 разных предметов, расставленных в линию. Благоприятной перестановкой будем считать такую, при которой точно 4 любых предмета будут стоять на своих местах (а остальные - на чужих). Сколько существует таких расстановок? Во сколько раз изменится число благоприятных комбинаций, если на своих местах будут стоять 6 предметов?
