Бывают комбинаторные задачи, в которых приходится составлять не одно рекуррентное соотношение, а систему соотношений, связывающую несколько последовательностей. Эти соотношения выражают
-у члены последовательностей через предыдущие члены не только данной, но и остальных последовательностей.
Задача: "Затруднение мажордома". Однажды мажордом короля Артура обнаружил, что к обеду за круглым столом приглашено 6 пар враждующих рыцарей. Сколькими способами можно рассадить их так, чтобы никакие два врага не сидели рядом?
Если мы найдем какой-то способ рассадки рыцарей, то, пересаживая их по кругу, получим еще 11 способов. Мы не будем сейчас считать различными способы, получающиеся друг из друга такой циклической пересадкой.
Введем следующие обозначения. Пусть число рыцарей равно
. Через
обозначим число способов рассадки, при которых никакие два врага не сидят рядом. Через
обозначим число способов, при которых рядом сидит ровно одна пара врагов, и через
- число способов, при которых есть ровно две пары враждующих соседей.
Выведем сначала формулу, выражающую
через
. Пусть
пар рыцарей посажены так, что никакие два врага не сидят рядом. Мы будем считать, что все враждующие пары рыцарей занумерованы. Попросим встать из-за стола пару рыцарей с номером
. Тогда возможны три случая: среди оставшихся за столом нет одной пары соседей- врагов, есть одна такая пара и есть две такие пары (ушедшие рыцари могли разделять эти пары). Мы считаем, что
. При
последующие рассуждения теряют силу.
Выясним теперь, сколькими способами можно снова посадить ушедших рыцарей за стол так, чтобы после этого не было одной пары соседей-врагов.
Проще всего посадить их, если за столом рядом сидят две пары врагов. В этом случае один из вновь пришедших садится между рыцарями первой пары, а другой – между рыцарями второй пары. Это можно сделать двумя способами. Но так как число способов рассадки
рыцарей, при которых две пары соседей оказались врагами, равно
, то всего получилось
способов.
Пусть теперь рядом сидит только одна пара врагов.
Один из вернувшихся должен сесть между ними. Тогда за столом окажутся
рыцарей, между которыми есть
мест. Из них два места - рядом с только что севшим гостем – запретны для второго рыцаря, и ему остается
мест. Так как первым может войти любой из двух вышедших рыцарей, то получается
способов рассадки. Но число случаев, когда
рыцарей сели так, чтобы ровно одна пара врагов оказалась соседями, ровно
. Поэтому мы получаем
способов посадить гостей требуемым образом. Наконец, пусть никакие два врага не сидели рядом. В этом случае первый рыцарь садится между любыми двумя гостями - это он может сделать
способами. После этого для его врага останется
мест - он может занять любое место, кроме двух мест, соседних с только что севшим рыцарем. Таким образом, если
рыцарей уже сидели нужным образом, то вернувшихся гостей можно посадить
способами. Как уже отмечалось, разработанными случаями исчерпываются все возможности. Поэтому имеет место рекуррентное соотношение
(7.7)
Этого соотношения пока недостаточно, чтобы найти
для всех значений
. Надо еще узнать, как выражаются
через
. Предположим, что среди
рыцарей оказалась ровно одна пара врагов-соседей. Мы знаем, что это может произойти в
случаях. Во избежание ссоры попросим их удалиться из-за стола. Тогда останется
рыцарей, причем возможно одно из двух: либо среди оставшихся нет врагов-соседей, либо есть ровно одна пара таких врагов - до ухода покинувших зал они сидели по обе стороны от них и теперь оказались рядом. Во втором случае ушедших можно посадить обратно только на старое место - иначе появится вторая пара враждующих соседей. Но так как
рыцарей можно посадить
способами так, чтобы была только одна пара враждующих соседей, то мы получаем
вариантов (возвратившихся рыцарей можно поменять местами). В первом же случае можно посадить ушедших между любыми двумя рыцарями, то есть
способами, а так как их еще можно поменять местами, то получится
способов. Комбинируя их со всеми способами посадки
пар рыцарей, при которых нет соседей врагов, получаем
способов.
Наконец, номер ушедшей и вернувшейся пары рыцарей мог быть любым от 1 до
. Отсюда вытекает, что рекуррентное соотношение для
имеет вид
(7.8)
Наконец, разберем случай, когда среди
рыцарей было две пары врагов-соседей. Номера этих пар можно выбрать
способами. Заменим каждую пару одним новым рыцарем, причем будем считать новых двух рыцарей врагами. Тогда за столом будут сидеть
рыцарей, причем среди них либо не будет ни одной пары врагов-соседей (если новые рыцари не сидят рядом), либо только одна такая пара. Первый вариант может быть в
случаях. Вернуться к исходной компании мы можем 4 способами благодаря возможности изменить порядок рыцарей в каждой паре. Поэтому первый вариант приводит к
способами. Второй же вариант может быть в
случаях. Имеется
случаев, когда какая-нибудь пара врагов сидит рядом. Если указать, какая именно пара должна сидеть рядом, получим в
раз меньше случаев. Здесь тоже можно вернуться к исходной компании 4 способами, и мы получаем всего
способов. Отсюда вытекает, что при
(7.9)
Мы получили систему рекуррентных соотношений
(7.10)
(7.11)
(7.12)
Они справедливы при
. Но простой подсчет показывает, что
. Поэтому из соотношений 7.10-7.12 вытекает, что
. Продолжая далее, находим, что гостей можно посадить за стол требуемым образом
