Совместимость перестановок с их пересортировкой

[kthxbye]

Для $n$ чисел имеем $n!$ перестановок. Далее каждое число в каждой перестановке мы заменяем его позицией. Назовём это пересортировкой. Тогда количество перестановок которые имеют $k$ одинаковых чисел на одинаковых позициях со своими пересортировками равно

$$q(n,k)=\binom{n}{k}s(k)t(n-k)$$

где

$$\sum\limits_{k=0}^{\infty} s(k)\frac{x^k}{k!}=\exp(\frac{x}{2}(x+2))$$

$$1,1,2,4,10,26,76,232,\cdots$$

$$\sum\limits_{k=0}^{\infty} t(k)\frac{x^k}{k!}=\frac{\exp(-\frac{x}{2}(x+2))}{1-x}$$

$$1,0,0,2,6,24,160,1140,\cdots$$

Насколько это очевидно и как можно доказать?

Этот же вопрос я ранее задал на MSE (вот тут), там есть примеры, которые я сюда не скопировал, потому что ругается цветовой тег. Также его прокомментировал некий Gerry Myerson (обильно отвечающий там на всякие вопросы), который, если ему верить, не считает этот результат тривиальным.

[wrest]

kthxbye
А можете доходчивей объяснить?
Вот например вы пишете что $q(4,0)=6[2341,2413,3142,3421,4123,4312]$ -- тут, видимо, $6$ перестановок таких, что ноль элементов совпадают с "изначальной" перестановкой $1234$
А вот $q(4,4)= 10[1234,1243,1324,1432,2134,2143,3214,3412,4231,4321]$ лично мне непонятно как сформировано. Я так понял ваш текст что должно быть $q(4,4)=1[1234]$

[Geen]

kthxbye в сообщении #1346374 писал(а):

Далее каждое число в каждой перестановке мы заменяем его позицией.

И получаем "массив" от $1$ до $n$ (единичную перестановку)... А из нескопированных примеров вроде бы получается, что Вы хотите просто взять обратную перестановку...

[grizzly]

wrest
Я попытаюсь ответить. Вот, например, 1243. Ему соответствующее строим по такому правилу: на месте 1 -- 1, на месте 2 -- 2, на месте 4 -- 3 (потому как 4 стоит на месте 3, инвентируем цифру и место), на месте 3 -- 4. Получили 1243. Сколько цифр совпало со стартовой перестановкой? -- 4.

[kthxbye]

wrest, благодарю за участие в теме! Доходчивое объяснение - моя самая сокровенная мечта. Но на мне видимо лежит какое-то проклятие. Простите за сумбур.

Как это обычно бывает, пока писал ответ, мне уже пришли на помощь. Выражаю огромную благодарность grizzly!

До:

А) $123456$ (числа по возрастанию, т.е. позиции)
Б) $146235$ (выбранная перестановка)

После:

А) $145263$ (пересортировка)
Б) $123456$ (числа в перестановке по возрастанию)

И теперь сравниваем 146235 и 145263. Совпадают 1,4,2. Эта перестановка - элемент $q(6,3)$.

[Geen]

kthxbye в сообщении #1346403 писал(а):

И теперь сравниваем 146235 и 145263. Совпадают 1,4,2.

То есть "отбрасываем" циклы длины 1 и 2?

[kthxbye]

Geen в сообщении #1346404 писал(а):

То есть "отбрасываем" циклы длины 1 и 2?

Не совсем понимаю. По этой же причине не ответил на ваш предыдущий комментарий. Мой пример немного неудачный, ведь половина совпадает, а другая - нет. Но в первом посте я однозначно указал, что буковка $k$ отвечает за количество совпадений.

На базе моего примера: 1 - единичный цикл; 4,2 - меняют друг друга, цикл длины 2. Так? Или не совсем? Или совсем не?

[Geen]

kthxbye в сообщении #1346429 писал(а):

На базе моего примера: 1 - единичный цикл; 4,2 - меняют друг друга, цикл длины 2. Так?

Да.
А обратная перестановка это та, которая приводит данную к единичной/тождественной.

kthxbye в сообщении #1346429 писал(а):

Но в первом посте я однозначно указал, что буковка $k$ отвечает за количество совпадений.

Ну это не сильно принципиально - ведь сумма будет $n$...

[kthxbye]

Geen в сообщении #1346447 писал(а):

Да.
А обратная перестановка это та, которая приводит данную к единичной/тождественной.

Т.е. исходя из того, что циклы выше двух никогда не дают совпадений, задача становится тривиальной и надо только.. только что?

Geen в сообщении #1346447 писал(а):

Ну это не сильно принципиально - ведь сумма будет $n$...

И функции надо будет менять местами. Но доказывать можно с любой стороны, это да.

[Geen]

kthxbye в сообщении #1346486 писал(а):

задача становится тривиальной

Я такого не говорил

А где Вы взяли эту формулу? Вывели/догадались/где-то нашли?

[kthxbye]

Geen в сообщении #1346506 писал(а):

А где Вы взяли эту формулу? Вывели/догадались/где-то нашли?

Об этом же меня спросили на MSE, где я честно ответил (правда без некоторых деталей), что, поскольку кодить не умею, всячески штурмовал excel, далее пробил первый столбец и диагональ в OEIS (и не только их, но это не дало результата), а затем

grizzly в сообщении #1313342 писал(а):

После часового тупления в экран я замечаю следующее.

Как-то так.

Найти конечно хорошо, но ещё лучше доказать.

[arseniiv]

Выше заметили, что вы считаете для перестановки количество её неподвижных точек (циклов длины 1) плюс дважды количество транспозиций (циклов длины 2) (или, проще, количество неподвижных точек квадрата перестановки). Можно попробовать идти отсюда прямой дорогой: чтобы получить $m$ таких точек, возьмём перестановки с $m_1$ неподвижными точками и $m_2$ транспозициями, где $m_1 + 2m_2 = m$. Перестановку с $m_1$ неподвижными точками получим просто приколов $\binom n{m_1}$ способами $m_1$ чисел; после этого разместим аналогично транспозиции (вот тут уж посложнее выражение, я его как-то выводил, но сейчас голова без бумаги не варит) и остальные элементы $(n-m)!$ способов (тут уж у нас ведь полная свобода). Если я ничего не проворонил, остаётся упрощать или усложнять, ну и ещё надо проверить, не нужно ли вдруг расставить ограничения на неотрицательность тех или иных чисел.

-- Вт окт 16, 2018 18:12:21 --

(Кстати, а простые, не экспоненциальные производящие функции для $s, t$ у вас не получались?)

-- Вт окт 16, 2018 18:32:34 --

Итак, нарисовать $m_2$ транспозиций среди оставшихся $n-m_1$ элементов можно

$$\binom{n-m_1}{2m_2}\frac{(2m_2)!}{2^{m_2} m_2!} = \binom{n-m_1}{2m_2} \binom{2m_2}{m_2} \frac{m_2!}{2^{m_2}}$$

способами (выбираем транспонируемых по очереди, но учитываем, что порядок элементов в парах и порядок самих пар не важны).

UPD.

arseniiv в сообщении #1346756 писал(а):

и остальные элементы $(n-m)!$ способов (тут уж у нас ведь полная свобода)

Не полная, см. на следующей странице.

[Geen]

arseniiv в сообщении #1346756 писал(а):

Если я ничего не проворонил,

Кажется, ещё надо учесть, что в "остатке" нет циклов длины 1 и 2.

[arseniiv]

Действительно! Значит, получается количество перестановок с не менее чем $m$ НТК (неподвижных точек квадрата), и надо брать у них как последовательности конечную разность. (Но не уверен, что ошибок больше не осталось.)

[Yadryara]

kthxbye в сообщении #1346374 писал(а):

$$\sum\limits_{k=0}^{\infty} s(k)\frac{x^k}{k!}=\exp(\frac{x}{2}(x+2))$$

Лишние сущности вроде бы не очень нужны. Зачем же нам $x$? Пишем просто

$$\sum\limits_{k=0}^{\infty} \frac{s(k)}{k!}=e^{\frac32}$$

kthxbye в сообщении #1346374 писал(а):

$$\sum\limits_{k=0}^{\infty} t(k)\frac{x^k}{k!}=\frac{\exp(-\frac{x}{2}(x+2))}{1-x}$$

А здесь, по-моему, ошибка. Если $x$ так уж нужен, может стоит для него ОДЗ указать?