Надо срочно грокнуть решение данной задачи. Нашёл описание в книге "Комбинаторика" Холла. Но ничего не понял. Так же искал в сети, нашёл 3 англоязычных статьи, и тоже ничего не понял (хотя мне приходилось разбираться и с более страшной математикой, например, с ТК или теорией Галуа). Что за ужас! Где найти внятное объяснение?
Могу рассказать о том, что я конкретно не понял (М. Холл "Комбинаторика" Мир, 1970): 25 страница, почти всё. Непонятно, к чему обозначение P(i): a_i = i, i + 1. Не понятно, что есть "дополнения перестановки". Почему мы "должны сначала подсчитать сколькими способами..."? Не понятно, как n может быть в каком-либо столбце, и причём тут вообще столбцы. Ну а дальше не понятно вообще ничего.
Здравствуйте, konsoletyper, Вы писали:
K>Надо срочно грокнуть решение данной задачи.
Оригинальная форма давать условие задачи. Мы наверное все дружно целыми днями зачитываемся Холлом. Когда человеку что-то СРОЧНО нужно, он старается, чтобы другие могли это что-то ему быстро дать.
K>Могу рассказать о том, что я конкретно не понял (М. Холл "Комбинаторика" Мир, 1970): 25 страница, почти всё. Непонятно, к чему обозначение P(i): a_i = i, i + 1. Не понятно, что есть "дополнения перестановки". Почему мы "должны сначала подсчитать сколькими способами..."? Не понятно, как n может быть в каком-либо столбце, и причём тут вообще столбцы. Ну а дальше не понятно вообще ничего.
K>Народ, отзовитесь, пожалуйста!
Ну раз просите, то придется...
Если начать читать с предыдущей страницы 24, то там нарисованы табличка, в ней есть столбцы, с этим разобрались.
Жен мы рассадили, далее, есть n мест для мужей. В первых двух строках столбца i этой таблички -- кто будет с тобой рядом, если тебя посадят на i-е место. Например, если тебя посадят на второе место, то рядом с тобой жена второго и третьего мужа. Третья строчка -- номер мужа, которого мы посадили на i-е место. ЧТобы выполнить условия, должно быть ai <> i, ai<>i+1, где в случае i=n мы полагаем (циклически) n+1=1 (здесь и потом), а также 1-1=n.
Короче, задача теперь расставить a1,...,an так, чтобы выполнилось это условие.
while (Задача включения-исключения НЕ знакомо что такое) { Читаем со страницы 18 }
Теперь P(i) -- число расстановок таких, что на i-м месте муж одной из соседних жен, т.е. на i-м месте муж i или i+1. Нам надо, чтобы не было ни одной такой P(i). Т.е. надо посчитать сколько различных расстановок, где на 1-м месте муж одной из соседок, или на втором, или на третьем и т.д.. А затем из всех возможных посадок вычесть это число.
Чтобы его найти мы и применяем формулу включения-исключения. Для этого нам еще надо найти число перестановок с r свойствами P(i), т.е. таких перестановок где есть r мужей, сидящих рядом с женами. Если свойство P(i) выполняется для r заданных мест ai1,...,air, то "дополнение перестановки" -- это то, как мы рассадим остальных. Т.к. все равно как, то вариантов (n-r)!.
Остальное должно быть понятно. Автор показывает двумя способами, что число перестановок с по крайней мере r совпадениями равно (2.1.24), ну а далее подставляет это выражение в формулу включения-исключения. В конце он показывает, как это можно переписать рекуррентно.
Здравствуйте, SergH, Вы писали:
K>>Народ, отзовитесь, пожалуйста! SH>
SH>Нужен телепат. Обращаться сами знаете куда (c)
SH>Текст задачи опубликуй хотя бы...
Странно, я думал, это общеизвестная задача
Смысл такой: хозяин пригласил n супружеских пар и хочет рассадить их за столом так, чтобы мужчины и женщины чередовались, и чтобы никто не сидел рядом со своим/своей супругом/супругой. Спрашивается: сколькими возможными способами это можно сделать?
Здравствуйте, konsoletyper, Вы писали:
K>Надо срочно грокнуть решение данной задачи. Нашёл описание в книге "Комбинаторика" Холла. Но ничего не понял. Так же искал в сети, нашёл 3 англоязычных статьи, и тоже ничего не понял (хотя мне приходилось разбираться и с более страшной математикой, например, с ТК или теорией Галуа). Что за ужас! Где найти внятное объяснение?
K>Могу рассказать о том, что я конкретно не понял (М. Холл "Комбинаторика" Мир, 1970): 25 страница, почти всё. Непонятно, к чему обозначение P(i): a_i = i, i + 1. Не понятно, что есть "дополнения перестановки". Почему мы "должны сначала подсчитать сколькими способами..."? Не понятно, как n может быть в каком-либо столбце, и причём тут вообще столбцы. Ну а дальше не понятно вообще ничего.
K>Народ, отзовитесь, пожалуйста!
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, konsoletyper, Вы писали:
K>>Надо срочно грокнуть решение данной задачи. Нашёл описание в книге "Комбинаторика" Холла. Но ничего не понял. Так же искал в сети, нашёл 3 англоязычных статьи, и тоже ничего не понял (хотя мне приходилось разбираться и с более страшной математикой, например, с ТК или теорией Галуа). Что за ужас! Где найти внятное объяснение?
K>>Могу рассказать о том, что я конкретно не понял (М. Холл "Комбинаторика" Мир, 1970): 25 страница, почти всё. Непонятно, к чему обозначение P(i): a_i = i, i + 1. Не понятно, что есть "дополнения перестановки". Почему мы "должны сначала подсчитать сколькими способами..."? Не понятно, как n может быть в каком-либо столбце, и причём тут вообще столбцы. Ну а дальше не понятно вообще ничего.
K>>Народ, отзовитесь, пожалуйста!
J>Ответ-то какой?
Yу если верить книжке, то ответ выражается только как ряд страшного вида, либо рекуррентно.