Частный случай теоремы о включениях и исключениях
   В некоторых случаях количество объектов, обладающих определенным набором свойств, зависит только от числа этих свойств. Тогда формула для подсчета числа объектов, не обладающих ни одним из выделенных свойств, упрощается.
    При произвольном n имеем:
 
   В последнем примере предыдущего параграфа мы использовали этот частный случай главной теоремы комбинаторики. В общем случае при перестановке n предметов количество расстановок, при которых ни один предмет не находится на своем месте:
                                                                                                              (10)

  Полученное значение      иногда называют формулой полного беспорядка или субфакториалом. Субфакториал       можно представить и так:




    где выражение в [...] стремится к     при неограниченном возрастании n.
    Субфакториал имеет свойства, похожие на свойства обычного факториала. Например,
n! = (n - 1)[(n - 1)! + (n - 2)!] - для обычного факториала,
                                          - для субфакториала.
 
    Субфакториалы легко вычисляются по формуле 
 

    Приведем некоторые начальные значения субфакториалов:



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