Перестановки и подпоследовательности

[Corwin]

Например, когда я решаю задачу перебором, по моему мнению эквивалентному полному перебору (доказать не могу), то для $n = 7$ на 41921 супер последовательностей, не прошедших проверку, у меня всего 34 подпоследовательности, на которых проверка не прошла. Для $n = 8$ на 4994956 супер последовательностей - всего 96 таких подпоследовательностей (из 40320).

[Corwin]

maxal в сообщении #710031 писал(а):

Я исправил A136094.

Можно дополнить это последовательность значением для $n = 6$:
1234516234152361425312643512

Всего для $n = 6$ существует 33809 различных решений (минимальной длины). Решения, которые можно получуть друг из друга отображением (1,2,3,4,5,6) в произвольную перестановку этих чисел, я считаю эквивалентными. Поэтому формально можно говорить о 33809 классах эквивалентности, а всего решений больше в 6! раз.

Обратите внимание, что это число не начинается на "123456". Для $n = 4$ и $n = 5$ все решения начинались на "1234" и "12345" соответсвенно.


p.s. Только что обратил внимание, что там указано неверное число для $n = 3$. Поэтому приведу данные для всех n.

$n = 5$:
всего 128
минимальное 1234512341523142351

$n = 4$:
всего 9
минимальное 123412314213

$n = 3$:
всего 7
минимальное 1213121

$n = 2$:
всего 1
минимальное 121

[maxal]

Corwin в сообщении #719485 писал(а):

maxal в сообщении #710031 писал(а):

Я исправил A136094.

Можно дополнить это последовательность значением для $n = 6$:
1234516234152361425312643512

...

p.s. Только что обратил внимание, что там указано неверное число для $n = 3$. Поэтому приведу данные для всех n.

Исправьте и пополните эту последовательность. Это просто - зарегистрируйтесь и вам будет доступна кнопка "edit"...