2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Совместимость перестановок с их пересортировкой
Сообщение17.10.2018, 20:49 
Заслуженный участник


27/04/09
28128
Yadryara
Ну здрасьте. :lol: У ТС написаны экспоненциальные производящие функции для последовательностей $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}.$$ Сами п. ф. можно получать из рекуррентных соотношений и других соображений об исследуемых комбинаторных числах, потом преобразовать их и находить в лучшем случае замкнутую формулу для таких чисел (часто весьма механической процедурой), в худшем часто более удобные представления. Ещё, например, дифференцирование, интегрирование, подстановка вместо переменной разных выражений дают много пользы.

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


29/04/13
7128
Богородский
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, Доброго утречка :-) Благодарю.

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


29/04/13
7128
Богородский
Вот ещё что заметил. $s(n)= q(n,n)$ — это у нас количество полностью совпавших вариантов после пересортировки. А $t(n) = q(n,0)$ — количество совершенно не совпавших. Так вот, очень похоже, что
$$\lim\limits_{n \to\infty}^{} \frac{n!}{t(n)}={e^\frac32}$$

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

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


22/11/13
496
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.

(Оффтоп)

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

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


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

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


27/04/09
28128
Раз уже упомянули числа беспорядков $!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 --

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

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

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

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


22/11/13
496
arseniiv в сообщении #1347466 писал(а):
Ладно, как минимум громадная формула в этом посте видится наконец-таки безошибочной. Она прошла проверку на совпадение с определением $q$ из первого поста на большом числе аргументов.

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

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

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



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

Сейчас этот форум просматривают: Vladimir Pliassov


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

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