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

      Задача 2. За круглом столом короля Артура сидят 12 рыцарей. Из них
каждый враждует с соседом. Надо выбрать 5 рыцарей (например, в экспе-
дицию, чтобы освободить заколдованную принцессу), причем так, чтобы
среди них не было враждующих (рис. 59). Сколькими способами это мож-
                          но сделать?
                                Отличие от предыдущей задачи состоит в том,
                          что рыцари сидят не в ряд, а по кругу. Но ее легко
                          свести к случаю, когда рыцари сидят в ряд. Для этого
                          возьмем рыцаря, например, сэра Ланселота, и ра-
                          зомкнем круг. Все выбираемые комбинации распа-
                          даются на два класса: в одном участвует сэр Лансе-
                          лот, в другом – нет. Подсчитаем, сколько комбина-
     Рис. 5.9
                          ций входит в каждый класс.
      1) Если сэр Ланселот отправился в поход, то его соседи справа и
слева не должны участвовать. Остаются 9 рыцарей из которых надо вы-
брать 4. Надо проследить, чтобы среди выбранных не было врагов, т. е.
чтобы двое врагов не сидели рядом. Цепь разорвана, следовательно,
          Л     4            4
              C          = С = 6! = 15 .
                9 − 4 +1     6 4!2!

     2) Так как сэр Ланселот не участвует в экспедиции, то его можно
исключить, остается 11 рыцарей, из которых выбирается 5. С5    = С5 =
                                                                         11− 5 +1   7
21. По правилу суммы всего С 4 + С5 = 15 + + 21 = 36.
                             6    7
       В общем случае, если по кругу расположены n элементов, а надо вы-
брать k так, чтобы в их число не попали два соседа, то это можно сделать
Сnk- 1       k
          + Сn    способами.
   − k- 1      −k
      Это доказывается аналогично. Все комбинации элементов разбивают-
ся на два класса в зависимости от одного из них (сэра Ланселота). В первом
варианте будет С k - 1 комбинаций, а во втором С k .
                    n − k -1                                n −k
                                                         n
      Легко проверяется, что С kn -−1k - 1 + С kn − k =     С kn − k .
                                                        n−k
      Доказательство:
              (n − k − 1)!         + (n − k)! =
      (k − 1)! (n − k − 1 − k + 1)! k! (n − k − k)!

      =      (n − k − 1)! (n − k)k + (n − k)! =
          (k − 1)! (n − 2k)! (n − k)k k! (n − 2k)!


                                         71