2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача о порядочных беспорядках
Сообщение05.10.2016, 19:53 
Модератор
Аватара пользователя


11/01/06
5516
Задача от забаненного автора, которая показалась мне интересной:

HacpeggiH в сообщении #1148448 писал(а):
Пусть имеем порядок: $x_1,x_2,....x_n$ и один из его беспорядков. Представим, что порядок и данный его беспорядок это два различных порядка. Необходимо найти выражение, дающее количество беспорядков обеих этих порядков.

Замечания:
  • Беспорядки здесь следует понимать как перестановки без неподвижных точек.
  • Ответ здесь, вообще говоря, зависит от заданного беспорядка, а именно от распределения циклов в нём. Поэтому можно считать, что нам заданы числа $c_i$ -- количество циклов длины $i$ (причём $c_1=0$), а ответ является функцией от $c_2,\dots,c_n$.

Бонусный вопрос: для какого заданного беспорядка ответ будет минимальным/максимальным?

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение06.10.2016, 08:14 
Заслуженный участник


12/08/10
1260
Еще бы понять условие задачи. :-)

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение06.10.2016, 08:43 
Заслуженный участник
Аватара пользователя


18/05/06
13364
с Территории
Ну, найти кол-во перестановок, которые не совпадают ни в одном элементе ни с правильной расстановкой (это-то просто), ни с ещё одной неправильной (фиксированной).

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение06.10.2016, 08:48 
Модератор
Аватара пользователя


11/01/06
5516
Переформулирую простым языком: дана таблица $2\times n$, где в первой строке написаны числа от 1 до $n$ по возрастанию, а во второй строке -- те же числа в некотором другом порядке, причем два числа в каждом столбце различны.
Сколькими способами можно приписать к этой таблице третью стоку, опять же содержающую все числа от 1 до $n$ в некотором порядке, так, чтобы три числа в каждом столбце были различны?

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение06.10.2016, 10:28 


05/10/16
6
Если $c_n=1$, то решение есть в книге М.Холла (М.Холл. Комбинаторика. Раздел 2.1) Там эта задача названа задачей о супружеских парах.

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение06.10.2016, 16:18 
Модератор
Аватара пользователя


11/01/06
5516
Boris Skovoroda в сообщении #1157680 писал(а):
Если $c_n=1$, то решение есть в книге М.Холла (М.Холл. Комбинаторика. Раздел 2.1) Там эта задача названа задачей о супружеских парах.

Да, хорошее наблюдение. Про задачу о супружеских парах можно также прочитать в Википедии или в моей статье.

Следующий простой случай -- это $n=2m$ и $c_2=m$.

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение06.10.2016, 19:56 
Модератор
Аватара пользователя


11/01/06
5516
Исходная задача может рассматриваться как обобщение задачи о супружеских парах на несколько круглых столов (и именно, с количество столов на $2i$ персон равным $c_i$).
Вполне жизненная задача :D

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение07.10.2016, 05:56 
Модератор
Аватара пользователя


11/01/06
5516
На самом деле все ингридиенты для решения уже указаны. Приведу ответ в общем виде: количество искомых беспорядков равно
$$\sum_{j=0}^n (-1)^j\cdot (n-j)!\cdot [z^j]\ F(z),$$
где
$$F(z) = (1+z)^{c_1}\cdot \prod_{i=2}^n \left( \left(\frac{1+\sqrt{1+4z}}2\right)^{2i} + \left(\frac{1-\sqrt{1+4z}}2\right)^{2i} \right)^{c_i}.$$

При этом формула работает и для случая $c_1>0$, т.е. данная перестановка не обязана быть беспорядком. За деталями отсылаю к своей статье (в частности, см. формулу (4) и Lemma 1), описанный там метод легко применим к рассматриваемой "много-столовой" задаче и даёт вышеуказанную формулу.

Частные случаи:
  • Для $c_1=n$ (т.е. данная перестановка тождественна) получаем просто количество беспорядков.
  • Для $c_n=1$, как уже было справедливо замечено, получаем менажные числа A000179(n).
  • Для $n=2m$ и $c_2=m$ получаем A000316(m) = A000459(m)$\cdot 2^m$.

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение07.10.2016, 08:36 
Заслуженный участник


12/08/10
1260
$ [z^j]\ F(z)$ - Это коэффициент при $z^j$?

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение07.10.2016, 14:09 
Модератор
Аватара пользователя


11/01/06
5516
Null, да.

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение07.10.2016, 15:57 


07/10/16
2
maxal в сообщении #1157940 писал(а):
На самом деле все ингридиенты для решения уже указаны. Приведу ответ в общем виде: количество искомых беспорядков равно
$$\sum_{j=0}^n (-1)^j\cdot (n-j)!\cdot [z^j]\ F(z),$$
где
$$F(z) = (1+z)^{c_1}\cdot \prod_{i=2}^n \left( \left(\frac{1+\sqrt{1+4z}}2\right)^{2i} + \left(\frac{1-\sqrt{1+4z}}2\right)^{2i} \right)^{c_i}.$$

При этом формула работает и для случая $c_1>0$, т.е. данная перестановка не обязана быть беспорядком. За деталями отсылаю к своей статье (в частности, см. формулу (4) и Lemma 1), описанный там метод легко применим к рассматриваемой "много-столовой" задаче и даёт вышеуказанную формулу.

Частные случаи:
  • Для $c_1=n$ (т.е. данная перестановка тождественна) получаем просто количество беспорядков.
  • Для $c_n=1$, как уже было справедливо замечено, получаем менажные числа A000179(n).
  • Для $n=2m$ и $c_2=m$ получаем A000316(m) = A000459(m)$\cdot 2^m$.


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

Заранее благодарю.

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение07.10.2016, 16:24 
Модератор
Аватара пользователя


11/01/06
5516
Efendi в сообщении #1158019 писал(а):
Простите, не могли бы Вы более подробно расписать ход решения, а не просто привести готовый ответ, а также привести пояснения к использованным обозначениям. Также непонятно, что Вы подразумеваете под циклами.
Как было указано раньше, задача не имеет однозначного ответа и результат зависит от выбора второй строки, как это учитывается в Вашем решении?

Подробно расписывать у меня нет времени - все по аналогии с моей статьей (ссылка приведена выше). Под циклами понимаются циклы данной перестановки ("второй строки" в вашей терминологии), и ответ, как легко видеть, зависит от её цикловой структуры, задаваемой числами $c_1,c_2,\dots,c_n$.

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение07.10.2016, 21:10 
Модератор
Аватара пользователя


11/01/06
5516
Добавил в OEIS связанные числовые последовательности: A277256, A277257, A277265.

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение07.10.2016, 23:57 


07/10/16
2
maxal в сообщении #1158025 писал(а):
Подробно расписывать у меня нет времени - все по аналогии с моей статьей (ссылка приведена выше).


Может быть у Вас есть эта статья в русском варианте?
Ну или хотябы урезанный вариант, объясняющий суть метода?

 Профиль  
                  
 
 Re: Задача о порядочных беспорядках
Сообщение08.10.2016, 00:01 
Модератор
Аватара пользователя


11/01/06
5516
Efendi в сообщении #1158106 писал(а):
Может быть у Вас есть эта статья в русском варианте?

Увы, но нет.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

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



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

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


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

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