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

задан 10 Сен 13:19

изменен 10 Сен 13:46

10|600 символов нужно символов осталось
2

Будем считать, что у нас имеются $%2n$% символов вида $%a_i$%, $%b_i$% ($%1\le i\le n$%), и мы располагаем их в строку. Общее число расположений равно $%(2n)!$%. Нас интересуют из них такие, для которых "враждующие" символы $%a_i$%, $%b_i$% ни при каком $%i$% не стоят рядом. Для каждого фиксированного $%i$% обозначим через $%A_i$% множество строк, в которых встречается подслово $%a_ib_i$% или $%b_ia_i$%. Требуется подсчитать мощность дополнения объединения $%A_1\cup\cdots\cup A_n$%. Как обычно бывает в таких случаях, применяем формулу включений и исключений:

$$|A_1\cup\cdots\cup A_n|=|A_1|+\cdots+|A_n|-\sum\limits_{i < j}|A_iA_j|+\cdots.$$

Для каждого $%i$% найдём мощность $%A_i$%; от $%i$% она не будет зависеть. Склеим символы $%a_i$%, $%b_i$% одним из двух способов. После этого у нас получается $%2n-1$% символ, и их произвольно переставляем $%(2n-1)!$% способами. Отсюда $%|A_1|+\cdots+|A_n|=n\cdot2(2n-1)!=(2n)!$%.

Теперь для произвольного $%k$% между $%1$% и $%n$% найдём мощность $%k$%-кратного пересечения $%A_{i_1}\ldots A_{i_k}$%, где $%i_1 < \cdots < i_k$%. Все такие мощности будет одинаковые, а слагаемых данного типа окажется $%C_n^k$%, по числу способов выбора набора индексов. Каждую пару символов вида $%a_i$%, $%b_i$% при $%i\in\{i_1,\ldots,i_k\}$% склеим одним из двух способов, что даёт $%2^k$% возможностей. При этом получается $%2n-k$% новых символов, и их переставляем $%(2n-k)!$% способами. В итоге имеем $$\sum\limits_{i_1 < \cdots < i_k}|A_{i_1}\ldots A_{i_k}|=C_n^k2^k(2n-k)!.$$

Вычитая из общего количества вариантов мощность дополнения, видим, что факториалы в самом начале сократятся, и далее останется сумма $$\sum\limits_{k=2}^n(-1)^kC_n^k2^k(2n-k)!.$$

Принципиально более простая форма ответа ту вряд ли возможна, хотя можно найти асимптотику (вероятность при больших $%n$% близка к $%e^{-1}$%). Дополнительную информацию о последовательности можно посмотреть здесь.

ссылка

отвечен 10 Сен 18:08

Почему после склеивания символов у нас (2n-1)! a не (2n-2)!, мы ведь "убрали" два символа.

(10 Сен 18:58) Niknet19

@Niknet19: мы их не убрали, а склеили, получив "слог" вида (ab) или (ba). Вместо двух старых символов получился один новый.

Ответ я проверял на компьютере ещё до заглядывания на oeis. Там всё совпадает.

(10 Сен 19:34) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,270
×1,122

задан
10 Сен 13:19

показан
81 раз

обновлен
10 Сен 19:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru