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

buratino.2016

Пусть имеем порядок: $$x_1,x_2,.....x_n$$

и один из его беспорядков. Представим, что порядок и беспорядок - это два различных порядка. Необходимо найти количество беспорядков, являющихся беспорядками обеих этих порядков.

buratino.2016

Ищем беспорядки к первому порядку, затем ко второму. Пересечение этих множеств дает беспорядки, принадлежащие обеим порядкам. Но нам необходимо вывести(подобрать, получить) обобщенную формулу для количества этих беспорядков при различных n.

grigoriy · Сообщение **grigoriy** » 04 сен 2016, 13:40

buratino.2016

Не, это было бы слишком просто.
Всего перестановок $$n!$$

Если одну перестановку принять за порядок, то у этого порядка будет $$!n$$

(субфакториал n) беспорядков, что равно ближайшему целому к $\frac{n!}{e}$ .
А если мы возьмем в качестве порядка исходный порядок и один из $$!n$$

беспорядков, то необходимо найти такие беспорядки, которые будут являтся беспорядками для обоих этих порядков. Можно условно назвать их "двойными беспорядками".

Под беспорядком понимается: https://ru.wikipedia.org/wiki/Беспорядок_(перестановка)
Возможно даже, что задача нерешаема или имеет в качестве решения многозначную функцию. Уже для $$n=5$$

количество двойных беспорядков зависит от выбора порядков. Т.е. пары порядков распределяются на 2 вида. для одних из них существует 12 двойных беспорядков, для других- 13.

grigoriy · Сообщение **grigoriy** » 05 сен 2016, 05:14

О беспорядках впервые слышу. Думал Вы так называете перестановки.
Муторная задачка. Хотя кому-то и интересна и может где-то даже и важна...

buratino.2016

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

buratino.2016

Пусть есть порядок и один из его беспорядков. Запишем их друг под другом и рассмотрим следующие рассуждения:
Мы имеем таблицу из 2-х строк и n столбцов, в столбцах которой нет ни одного дубля. Третью строку мы можем записать n! числом способов. Если из этих n! способов вычесть количество тех, при которых в столбцах таблицы возникнет 1 дубль, 2 дубля,3 дубля,......, n дублей, то останутся те способы, заполнения третьей строки, при которых в таблице не будет ни дублей, ни триплетов. Они и будут беспорядками порядков, представленных в первых двух строках.
при заполнении третьей строки один дубль может возникнуть на любой из n ячеек строки. Т.е. может возникнуть на $$C_n^1$$

местах, при этом совпадение значения третьей строки в столбце может быть как с первой, так и со второй строкой, т.е. количество вариантов одного дубля удваивается. Все остальные $$n-1$$

ячейки строки могут быть заполнены $$(n-1)!$$

способами, в которых кстати также могут быть и дубли. Таким образом, Количество заполнений третьей строки в которых присутствует хотябы один дубль равно $$2C_n^1(n-1)!$$

, но нам необходимо было вычесть из n! количество комбинаций, содержащих ровно один дубль, а не хотябы один. Получается, что мы вычли лишнее: комбинации, содержащие более одного дубля. Поэтому прибавим комбинации, включающие хотябы два дубля. Их количество будет $$2^2C_n^2(n-2)!$$

, пользуясь методом включения-исключения доберемся до последнего слагаемого: (-1)^n2^nC_n^n(n-n)! и общая формула примет вид:
$n!\sum_{i=0}^n\frac{2^i}{i!}$ и при достаточно больших n выражение примерно равно $\frac{n!}{e^2}$
Вроде бы рассуждения верные, но компьютерный расчет опровергает этот результат. На самом деле решение раздваивается и зависит не только от n, но и от выбора первых двух строк. Из-за чего может происходить такое раздвоение результатов? Какие ошибки могут быть в приведенных рассуждениях?

yourdomain.com