Комбинаторные алгоритмы для программистов



             

Задача: "Затруднение мажордома" - часть 2


Один из вернувшихся должен сесть между ними. Тогда за столом окажутся
2n + 1
рыцарей, между которыми есть
2n + 1
мест. Из них два места - рядом с только что севшим гостем – запретны для второго рыцаря, и ему остается
2n - 1
мест. Так как первым может войти любой из двух вышедших рыцарей, то получается
2(2m-1)
способов рассадки. Но число случаев, когда
2n
рыцарей сели так, чтобы ровно одна пара врагов оказалась соседями, ровно
B_n
. Поэтому мы получаем
2(2n - 1)B_n
способов посадить гостей требуемым образом.

Наконец, пусть никакие два врага не сидели рядом. В этом случае первый рыцарь садится между любыми двумя гостями - это он может сделать

2n
способами. После этого для его врага останется
2n - 1
мест - он может занять любое место, кроме двух мест, соседних с только что севшим рыцарем. Таким образом, если
2n
рыцарей уже сидели нужным образом, то вернувшихся гостей можно посадить
2n(2n - 1)A_n

способами. Как уже отмечалось, разработанными случаями исчерпываются все возможности. Поэтому имеет место рекуррентное соотношение

A_{n + 1} = 2n(2n - 1)A_n + 2(2n - 1)B_n + 2C.

(7.7)

Этого соотношения пока недостаточно, чтобы найти

A_n
для всех значений
n
. Надо еще узнать, как выражаются
B_{n + 1},C_{n + 1}
через
A_n, B_n, C_n
.

Предположим, что среди

2n + 2,n > 1
рыцарей оказалась ровно одна пара врагов-соседей. Мы знаем, что это может произойти в
B_{n + 1}
случаях. Во избежание ссоры попросим их удалиться из-за стола. Тогда останется
2n
рыцарей, причем возможно одно из двух: либо среди оставшихся нет врагов-соседей, либо есть ровно одна пара таких врагов - до ухода покинувших зал они сидели по обе стороны от них и теперь оказались рядом. Во втором случае ушедших можно посадить обратно только на старое место - иначе появится вторая пара враждующих соседей. Но так как
2n
рыцарей можно посадить
B_n
способами так, чтобы была только одна пара враждующих соседей, то мы получаем
2B_n
вариантов (возвратившихся рыцарей можно поменять местами). В первом же случае можно посадить ушедших между любыми двумя рыцарями, то есть
2n

способами, а так как их еще можно поменять местами, то получится

4n
способов. Комбинируя их со всеми способами посадки
n
пар рыцарей, при которых нет соседей врагов, получаем
4nA_n
способов.


Содержание  Назад  Вперед