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

[arseniiv]

Yadryara
Ну здрасьте. У ТС написаны экспоненциальные производящие функции для последовательностей $s$ и $t$, и они, во-первых, позволяют представить все члены последовательности в другом часто более удобном для операций виде (и сохраняют всю информацию о последовательности — а если убрать переменную, подставив вместо неё ту же единицу, мы потеряем информацию) и, во-вторых в общем случае они понимаются как формальный степенной ряд, и о сходимости можно не думать, пока не возникает необходимость подставить туда вместо переменной число (что бывает полезным, конечно, но не всякий раз).

-- Ср окт 17, 2018 23:08:40 --

(В дополнение)

Самый простой пример пользы: свёртка двух последовательностей имеет п. ф. (уже обычную, не экспоненциальную — и ещё есть пара других видов; одни удобнее там, другие сям), равную произведению п. ф. этих последовательностей, потому что

$$\left( \sum_{n=0}^\infty a_n z^n \right) \left( \sum_{n=0}^\infty b_n z^n \right) = \sum_{n=0}^\infty z^n \sum_{m=0}^n a_m b_{n-m}.$$

Сами п. ф. можно получать из рекуррентных соотношений и других соображений об исследуемых комбинаторных числах, потом преобразовать их и находить в лучшем случае замкнутую формулу для таких чисел (часто весьма механической процедурой), в худшем часто более удобные представления. Ещё, например, дифференцирование, интегрирование, подстановка вместо переменной разных выражений дают много пользы.

[Yadryara]

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

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

А следующее, то есть $s(8) = 764$.

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

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

И, соответственно, $t(8) = 8988$.

arseniiv, Доброго утречка Благодарю.

[Yadryara]

Вот ещё что заметил. $s(n)= q(n,n)$ — это у нас количество полностью совпавших вариантов после пересортировки. А $t(n) = q(n,0)$ — количество совершенно не совпавших. Так вот, очень похоже, что

$$\lim\limits_{n \to\infty}^{} \frac{n!}{t(n)}={e^\frac32}$$

arseniiv, не затруднит ли Вас сопроводить Ваши формулы числовыми примерами?

[kthxbye]

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

свёртка двух последовательностей имеет п. ф., равную произведению п. ф. этих последовательностей

Замечательное свойство! Благодаря нему, мы можем быть в полной уверенности, что

$$\sum\limits_{k=0}^{n}q(n,k)=n!$$

поскольку

$$\sum\limits_{n=0}^{\infty}\frac{x^n}{n!}\sum\limits_{k=0}^{n}q(n,k)=\frac{1}{1-x}$$

А вот ваши манипуляции для меня остались загадкой. Присоединяюсь к Yadryara - буду очень признателен за примеры на перестановках небольшой длины (в пределах 4).

Еще можно сделать генерализацию и рассмотреть более простой вариант с одними только неподвижными точками, для которого

$$q_{1}(n,k)=\binom{n}{k}a(n-k)$$

где

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

$$1,0,1,2,9,44,265,1854,\cdots$$

$$a(n)=na(n-1)+(-1)^n$$

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

Yadryara в сообщении #1347215 писал(а):

Вот ещё что заметил. $s(n)= q(n,n)$ — это у нас количество полностью совпавших вариантов после пересортировки. А $t(n) = q(n,0)$ — количество совершенно не совпавших.

Точно так. Все это (в том числе и асимптотику), а также многое другое можно найти в A000085 и A038205.

(Оффтоп)

Удивительно, как далеко друг от друга оказались эти две последовательности.

[arseniiv]

Стал выписывать — увидел ещё одну ошибку: одну и ту же перестановку можно получить несколько раз по той процедуре. Значит всё-таки надо расставлять оставшиеся элементы сразу так, чтобы в остатке не было ни неподвижных точек, ни транспозиций.

[arseniiv]

Раз уже упомянули числа беспорядков $!x$, к упрощённой задаче они как раз применяются; $q_1(n, m) = \binom nm\;!(n-m)$ — выбираем $m$ неподвижных и остальные перемешиваем без неподвижны. Для формулы самой $q$ понадобится уже «число беспорядков без транспозиций», обозначим его $!_2x$. Это A038205.

-- Пт окт 19, 2018 01:03:12 --

Если не удалось собрать формулу для $q$ (даже ту неправильную), которую я описал, вот она в явном виде:

$$ q(n, m) = \sum_{\substack{m_1 + 2m_2 = m \\ m_1,m_2\geqslant0}} \binom n{m_1}\;\; \binom{n-m_1}{2m_2} \binom{2m_2}{m_2} \frac{m_2!}{2^{m_2}} \;\;!_2(n-m) ,$$

причём $\binom n{m_1} \binom{n-m_1}{2m_2} \binom{2m_2}{m_2}$ можно записать короче через мультиномиальный коэффициент $\binom n{m_1,m_2,m_2,n-m}$, а суммирование, разумеется, можно представить как

$$\sum_{m_2 = 0}^{\lfloor m/2 \rfloor} [m_1 = m-2m_2].$$

Сейчас проверю, получаются ли правильные числа.

-- Пт окт 19, 2018 01:05:24 --

Поправил в очередной раз.

-- Пт окт 19, 2018 01:25:37 --

Так ваши $t(n)$ и есть $!_2n$!

-- Пт окт 19, 2018 01:28:06 --

Оказывается, я не очень хорошо читал ваш предыдущий пост, в котором вы уже и так формулу с субфакториалом привели.

-- Пт окт 19, 2018 01:30:27 --

Ладно, как минимум громадная формула в этом посте видится наконец-таки безошибочной. Она прошла проверку на совпадение с определением $q$ из первого поста на большом числе аргументов.

[kthxbye]

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

Ладно, как минимум громадная формула в этом посте видится наконец-таки безошибочной. Она прошла проверку на совпадение с определением $q$ из первого поста на большом числе аргументов.

Это действительно так. Огромное вам спасибо! Заменить число беспорядков без транспозиций можно формулой-ужастиком из OEIS, которую туда добавил некий Владимир Кручинин, но я попытаюсь найти что-нибудь более элегантное.