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

      =        (n − k)! k     + (n − k)! = С k   ( k +1)= n С k .
          k! (n − 2k)! (n − k) k! (n − 2k)!  n −k n − k  n − k n −k
      Упражнения 3.8
      1. На собрании должно выступить 5 человек: А, Б, В, Г и Д. Скольки-
ми способами можно расположить их в списке ораторов при условии, что Б
не должен выступать до того, как выступит А?
      Решение. Список ораторов может быть составлен,
например, так, как показано на рис. 60. Общее число
вариантов           составления             списка         из А, Б, В, Г, Д
5 элементов может быть найдено как число перестано-
                                                               В, А, Д, Б, Г
вок 5 элементов. Все перестановки можно разбить на
два класса: 1-й класс содержит перестановки, в которых
                                                               В, А, Д, Г, Б
элемент А предшествует элементу Б, а 2-й класс со-
держит перестановки, в которых элемент Б предшеству- . . .
ет элементу А.           Рис. 60
Оба класса равнозначны. Следовательно, количество перестановок, в кото-
рых элемент А предшествует элементу Б, равно количеству перестановок 2-
го класса. Всего перестановок . . . . . . , а искомое число перестановок . . . . . .
..
      Ответ: . . . . . . . . . .

                          2. Решите ту же задачу при условии, что оратор А
                     должен выступить непосредственно перед оратором Б.
 А, Б, В, Г, Д
                          Решение. Рассмотрим перестановки, в которых два
 В, А, Б, Д, Г       элемента стоят рядом, т. е. элементы А, Б можно рассмат-
                     ривать как один элемент (рис. 61). Следовательно, общее
 В, Д, Г, А, Б       число перестановок . . . . . . . . . .
 ...                           Рис. 61              Ответ: . . . . . . . . . .

         3. Сколько можно сделать перестановок из n элементов, в которых
элементы А и Б не стоят рядом; элементы А, Б, С не стоят рядом (в любом
порядке)?
         Решение. Известно общее число перестановок n элементов –
. . . . . . . . . . Как и в предыдущей задаче мы можем найти перестановки, в
которых два элемента стоят рядом, т. е. элементы А , Б можно рассматри-
вать как один элемент. Число таких перестановок . . . . . . . Учтем, что эле-
менты А, Б можно поменять местами. Из общего числа перестановок вы-
чтем число перестановок, в которых два элемента стоят рядом . . . . . . . . . . . .
. . . . . . . . Аналогично рассуждаем для трех элементов. Следует учесть, что

                                       72