Задача: "Затруднение мажордома"

Бывают комбинаторные задачи, в которых приходится составлять не одно рекуррентное соотношение, а систему соотношений, связывающую несколько последовательностей. Эти соотношения выражают

$(n + 1)$

-у члены последовательностей через предыдущие члены не только данной, но и остальных последовательностей.

Задача: "Затруднение мажордома". Однажды мажордом короля Артура обнаружил, что к обеду за круглым столом приглашено 6 пар враждующих рыцарей. Сколькими способами можно рассадить их так, чтобы никакие два врага не сидели рядом?

Если мы найдем какой-то способ рассадки рыцарей, то, пересаживая их по кругу, получим еще 11 способов. Мы не будем сейчас считать различными способы, получающиеся друг из друга такой циклической пересадкой.

Введем следующие обозначения. Пусть число рыцарей равно

$2n$

. Через

$A_n^{}$

обозначим число способов рассадки, при которых никакие два врага не сидят рядом. Через

$B_n$

обозначим число способов, при которых рядом сидит ровно одна пара врагов, и через

$C_n$

- число способов, при которых есть ровно две пары враждующих соседей.

Выведем сначала формулу, выражающую

$A_{n + 1}$

через

$A_n,B_n,C_n$

. Пусть

$n + 1$

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

$n + 1$

. Тогда возможны три случая: среди оставшихся за столом нет одной пары соседей- врагов, есть одна такая пара и есть две такие пары (ушедшие рыцари могли разделять эти пары). Мы считаем, что

$n > 1$

. При

$n = 1$

последующие рассуждения теряют силу.

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

Проще всего посадить их, если за столом рядом сидят две пары врагов. В этом случае один из вновь пришедших садится между рыцарями первой пары, а другой – между рыцарями второй пары. Это можно сделать двумя способами. Но так как число способов рассадки

$2n$

рыцарей, при которых две пары соседей оказались врагами, равно

$C_n$

, то всего получилось

$2C_n$

способов.

Пусть теперь рядом сидит только одна пара врагов.

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