2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 11:39 
Аватара пользователя


22/11/13
497
Для $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 (обильно отвечающий там на всякие вопросы), который, если ему верить, не считает этот результат тривиальным.

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 12:55 


05/09/16
11469
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]$

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 13:09 
Заслуженный участник
Аватара пользователя


01/09/13
4318
kthxbye в сообщении #1346374 писал(а):
Далее каждое число в каждой перестановке мы заменяем его позицией.

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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 13:11 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 13:18 
Аватара пользователя


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

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

До:

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

После:

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

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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 13:26 
Заслуженный участник
Аватара пользователя


01/09/13
4318
kthxbye в сообщении #1346403 писал(а):
И теперь сравниваем 146235 и 145263. Совпадают 1,4,2.

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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 14:59 
Аватара пользователя


22/11/13
497
Geen в сообщении #1346404 писал(а):
То есть "отбрасываем" циклы длины 1 и 2?

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

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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 15:56 
Заслуженный участник
Аватара пользователя


01/09/13
4318
kthxbye в сообщении #1346429 писал(а):
На базе моего примера: 1 - единичный цикл; 4,2 - меняют друг друга, цикл длины 2. Так?

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

kthxbye в сообщении #1346429 писал(а):
Но в первом посте я однозначно указал, что буковка $k$ отвечает за количество совпадений.

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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение15.10.2018, 18:11 
Аватара пользователя


22/11/13
497
Geen в сообщении #1346447 писал(а):
Да.
А обратная перестановка это та, которая приводит данную к единичной/тождественной.

Т.е. исходя из того, что циклы выше двух никогда не дают совпадений, задача становится тривиальной и надо только.. только что?
Geen в сообщении #1346447 писал(а):
Ну это не сильно принципиально - ведь сумма будет $n$...

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

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


01/09/13
4318
kthxbye в сообщении #1346486 писал(а):
задача становится тривиальной

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

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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение16.10.2018, 05:11 
Аватара пользователя


22/11/13
497
Geen в сообщении #1346506 писал(а):
А где Вы взяли эту формулу? Вывели/догадались/где-то нашли?

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

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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение16.10.2018, 16:08 
Заслуженный участник


27/04/09
28128
Выше заметили, что вы считаете для перестановки количество её неподвижных точек (циклов длины 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)!$ способов (тут уж у нас ведь полная свобода)
Не полная, см. на следующей странице.

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение16.10.2018, 22:47 
Заслуженный участник
Аватара пользователя


01/09/13
4318
arseniiv в сообщении #1346756 писал(а):
Если я ничего не проворонил,

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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение17.10.2018, 08:06 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение17.10.2018, 17:45 
Аватара пользователя


29/04/13
7131
Богородский
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$ так уж нужен, может стоит для него ОДЗ указать?

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

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



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

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


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

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