Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 76 стр.

                         Pn,r = C rn Pn–r.                 (14)
      В самом деле, сначала нужно выбрать, какие именно r элементов ос-
таются на месте. Это можно сделать С rn способами, а остальные перестав-
лять.
      Перестановку можно произвести Pn–r способами. По правилу произве-
дения получаем С rn Pn–r.
      3. Сумма всех смещений равна
                     n                  n
                n!= ∑ D      = ∑ Сr D    ,                                (15)
                        n, r      n n- r
                    r =0               r =0
причем D0 = 1.
     4. Число перестановок из n элементов, при которых данные r эле-
ментов смещены (остальные могут быть смещены, а могут оставаться на
своих местах), выражается формулой
                    1              2                   r
        Dn,r = Pn – C Pn–1 + C Pn–2 – ... +(–1)r C Pn–r (r– –смещение);
                    r              r                   r
                               1                   2
                Dn,r = n! – C (n–1)! + C (n-2)! – ... + (–1)r (n–r)!.     (16)
                               r                   r

                             3.9.3. Смещение пар
       Задача 2. По пустыне идет караван из 9 верблюдов. За много дней пу-
тешествия надоедает видеть впереди себя одного и того же верблюда.
       Сколькими способами можно переставить верблюдов так, чтобы впе-
реди каждого шел другой верблюд, чем до этого?
       Для решения задач пронумеруем верблюдов в первоначальном поряд-
ке от конца каравана к его началу числами: 1, 2, 3, 4, 5, 6, 7, 8, 9. Нам нуж-
но найти все перестановки из чисел, в которых не встречаются пары (1, 2),
(2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9).
       Используем формулу включения–исключения.
       1. Сосчитаем во сколько перестановок входит пара (1, 2). Можно обо-
значить в этих перестановках пару за один элемент. Следовательно, всего 8
элементов, и число перестановок из 8 элементов, содержащих пару (1, 2)
равно P8.
       Тот же результат получаем для всех 8 пар.
       2. Рассмотрим перестановки, содержащие данные две пары. В этом
случае объединяем элементы, входящие в две пары:
       а) если обе пары содержат один и тот же элемент, например, (1, 2) и
(2, 3) => (1, 2, 3), 4, 5, 6, 7, 8, 9, то всего P7 перестановок;

                                              76