Задача о порядочных беспорядках

[maxal]

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

HacpeggiH в сообщении #1148448 писал(а):

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

Замечания:

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

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

[Null]

Еще бы понять условие задачи.

[ИСН]

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

[maxal]

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

[Boris Skovoroda]

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

[maxal]

Boris Skovoroda в сообщении #1157680 писал(а):

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

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

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

[maxal]

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

[maxal]

На самом деле все ингридиенты для решения уже указаны. Приведу ответ в общем виде: количество искомых беспорядков равно

$$\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$.

[Null]

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

[maxal]

Null, да.

[Efendi]

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$.

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

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

[maxal]

Efendi в сообщении #1158019 писал(а):

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

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

[maxal]

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

[Efendi]

maxal в сообщении #1158025 писал(а):

Подробно расписывать у меня нет времени - все по аналогии с моей статьей (ссылка приведена выше).

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

[maxal]

Efendi в сообщении #1158106 писал(а):

Может быть у Вас есть эта статья в русском варианте?

Увы, но нет.