2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Уточнение деталей комбинаторного метода
Сообщение12.10.2020, 08:51 
Аватара пользователя


22/11/13
02/04/25
549
Кроме ГП (Гамильтоновы пути) ладьи я интересовался также вопросом ГЦ (Гамильтоновы циклы). Для ладьи $n\times2$ результат размещен вот тут - A276356. Результат базируется на двух подпоследовательностях, которые связаны с ГП ладьи $n\times2$, где мы начинаем на определенной строке клеток и заканчиваем либо на той же строке, либо на противоположной, откуда и вытекают две подпоследовательности (подробнее мои комментарии к A001040 и A001053). В то же время результат по ГЦ совпадает с другой комбинаторной задачей - A089039. Мне бы хотелось обратиться к помощи с целью уточнить некоторые детали.

Суть задачи (или проблемы) состоит в следующем: существует $2n$ людей, которые представляют собой $n$ женатых пар. Их нам необходимо рассадить за столом таким образом, что персоны противоположного пола не могут сидеть рядом друг с другом за одним исключением - сидеть рядом разрешается, только если они супруги. В A089039 имеется ссылка (http://kurihara.sansu.org/sansu1-3/380.html) на разбор данной задачи, но даже с переводчиком я понял далеко не все.

Автор статьи рассуждает следующим образом. Пусть $k$ - число пар размещаемых супружеских пар (т.е. мы размещаем $2k$ мужчин и $2k$ женщин). Выбрать их можно

$\binom{n}{2k}$

способами. Далее идут какие-то манипуляции с $(2k-1)!\cdot2!$ которые мне и хотелось бы уточнить. После чего мы всаживаем между мужчинами новых мужчин. Первого мужчину из $n-2k$ оставшихся мы всаживаем $k$ способами, второго из $n-2k-1$ оставшихся мы всаживаем $k+1$ способами. Сумма числа мужчин и способов их размещения равна всегда $n-k$, тогда

$n-2k$ $\to$ $k$ в сумме $(n-k)$
$n-2k-1$ $\to$ $k+1$ в сумме $(n-k)$
$n-2k-2$ $\to$ $k+2$ в сумме $(n-k)$
...
$1$ $\to$ $n-k-1$ в сумме $(n-k)$

Отсюда имеем

$\frac{(n-k-1)!}{(k-1)!}$

способов дополнительно разместить мужчин между мужчинами. Аналогично с женщинами. Непонятным отсается нюанс, связанный с $(2k-1)!\cdot2!$. Что это вообще может быть и какой смысл в данной операции?

 Профиль  
                  
 
 Re: Уточнение деталей комбинаторного метода
Сообщение12.10.2020, 10:29 
Аватара пользователя


22/11/13
02/04/25
549
Сообразил, но не уверен что абсолютно корректно. По логике разместить $2k$ пар мы можем $(2k)!$ способами, однако т.к. пары сидят за столом, то некоторые размещения тождественны, а именно

$1234-2341-3412-4123$
$1243-2431-4312-3124$
...
$1432-4321-3214-2143$

следовательно сокращаем на $2k$. А $2!$ - это когда мы размещаем пары за столом начиная с мужчины либо с женщины. Вроде бы все укладывается в рамки задачи. Насколько эти догадки могут быть корректны?

 Профиль  
                  
 
 Posted automatically
Сообщение12.10.2020, 11:57 


20/03/14
12041
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);


Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение13.10.2020, 08:21 


20/03/14
12041
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group