Задача о супружеских парах
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 01.11.07 19:25
Оценка:
Надо срочно грокнуть решение данной задачи. Нашёл описание в книге "Комбинаторика" Холла. Но ничего не понял. Так же искал в сети, нашёл 3 англоязычных статьи, и тоже ничего не понял (хотя мне приходилось разбираться и с более страшной математикой, например, с ТК или теорией Галуа). Что за ужас! Где найти внятное объяснение?

Могу рассказать о том, что я конкретно не понял (М. Холл "Комбинаторика" Мир, 1970): 25 страница, почти всё. Непонятно, к чему обозначение P(i): a_i = i, i + 1. Не понятно, что есть "дополнения перестановки". Почему мы "должны сначала подсчитать сколькими способами..."? Не понятно, как n может быть в каком-либо столбце, и причём тут вообще столбцы. Ну а дальше не понятно вообще ничего.

Народ, отзовитесь, пожалуйста!
... << RSDN@Home 1.2.0 alpha rev. 710>>
Re: Задача о супружеских парах
От: Mab Россия http://shade.msu.ru/~mab
Дата: 01.11.07 19:26
Оценка:
Здравствуйте, konsoletyper, Вы писали:

Что за задача-то? Двудольные паросочетания?
Re: Задача о супружеских парах
От: SergH Россия  
Дата: 01.11.07 20:11
Оценка: +2
Здравствуйте, konsoletyper, Вы писали:

K>Народ, отзовитесь, пожалуйста!

Нужен телепат. Обращаться сами знаете куда (c)


Текст задачи опубликуй хотя бы...
Делай что должно, и будь что будет
Re: Задача о супружеских парах
От: vadimcher  
Дата: 01.11.07 20:14
Оценка: 33 (3)
Здравствуйте, 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), ну а далее подставляет это выражение в формулу включения-исключения. В конце он показывает, как это можно переписать рекуррентно.

А вот зайца кому, зайца-выбегайца?!
Re[2]: Задача о супружеских парах
От: konsoletyper Россия https://github.com/konsoletyper
Дата: 01.11.07 21:07
Оценка:
Здравствуйте, SergH, Вы писали:

K>>Народ, отзовитесь, пожалуйста!

SH>

SH>Нужен телепат. Обращаться сами знаете куда (c)


SH>Текст задачи опубликуй хотя бы...


Странно, я думал, это общеизвестная задача

Смысл такой: хозяин пригласил n супружеских пар и хочет рассадить их за столом так, чтобы мужчины и женщины чередовались, и чтобы никто не сидел рядом со своим/своей супругом/супругой. Спрашивается: сколькими возможными способами это можно сделать?
... << RSDN@Home 1.2.0 alpha rev. 710>>
Re: Задача о супружеских парах
От: jazzer Россия Skype: enerjazzer
Дата: 13.11.07 14:20
Оценка:
Здравствуйте, konsoletyper, Вы писали:

K>Надо срочно грокнуть решение данной задачи. Нашёл описание в книге "Комбинаторика" Холла. Но ничего не понял. Так же искал в сети, нашёл 3 англоязычных статьи, и тоже ничего не понял (хотя мне приходилось разбираться и с более страшной математикой, например, с ТК или теорией Галуа). Что за ужас! Где найти внятное объяснение?


K>Могу рассказать о том, что я конкретно не понял (М. Холл "Комбинаторика" Мир, 1970): 25 страница, почти всё. Непонятно, к чему обозначение P(i): a_i = i, i + 1. Не понятно, что есть "дополнения перестановки". Почему мы "должны сначала подсчитать сколькими способами..."? Не понятно, как n может быть в каком-либо столбце, и причём тут вообще столбцы. Ну а дальше не понятно вообще ничего.


K>Народ, отзовитесь, пожалуйста!


Ответ-то какой?
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[2]: Задача о супружеских парах
От: vadimcher  
Дата: 13.11.07 14:59
Оценка:
Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, konsoletyper, Вы писали:


K>>Надо срочно грокнуть решение данной задачи. Нашёл описание в книге "Комбинаторика" Холла. Но ничего не понял. Так же искал в сети, нашёл 3 англоязычных статьи, и тоже ничего не понял (хотя мне приходилось разбираться и с более страшной математикой, например, с ТК или теорией Галуа). Что за ужас! Где найти внятное объяснение?


K>>Могу рассказать о том, что я конкретно не понял (М. Холл "Комбинаторика" Мир, 1970): 25 страница, почти всё. Непонятно, к чему обозначение P(i): a_i = i, i + 1. Не понятно, что есть "дополнения перестановки". Почему мы "должны сначала подсчитать сколькими способами..."? Не понятно, как n может быть в каком-либо столбце, и причём тут вообще столбцы. Ну а дальше не понятно вообще ничего.


K>>Народ, отзовитесь, пожалуйста!


J>Ответ-то какой?


Yу если верить книжке, то ответ выражается только как ряд страшного вида, либо рекуррентно.

А вот зайца кому, зайца-выбегайца?!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.