Удвоение в конечных последовательностях

[juna]

Я имел в виду, что можно рассмотреть сначала тривиальные случаи. Например, для множества $\{1,2\}$, правило, по которому получаются допустимые последовательности очень простое: необходимо и достаточно, чтобы первая и последняя цифра были разными.
Всегда приходим к одной из двух последовательностей $\{1,2,1,2....1,2\}$ или $\{2,1,2,1...2,1\}$
Для множества $\{1,2,3\}$ это условие необходимое, но уже недостаточное.
Пусть искомое множество - это $A=\{1,2,...N\}$, рассматриваем все последовательности $\forall x_i\in A, i=1..k, k>N:\{x_1,x_2...x_k\}$
Если $a(N,k)$ - количество допустимых последовательностей, то расчеты (на бумажке, при малой концентрации внимания и большой вероятности ошибки) показывают:
$a(3,4)=3\cdot 3!=18$ среди $3^4=81$ возможных
$a(3,5)=8\cdot 3!=48$ среди $3^5=243$ возможных
$a(3,6)=22\cdot 3!=132$ среди $3^6=729$ возможных
Было бы интересно продолжить эту последовательность дальше или вообще получить формулу для $a(N,k)$. Для $N=3$ может быть нарвемся на известную

[Руст]

Артамонов Ю.Н. писал(а):

Я имел в виду, что можно рассмотреть сначала тривиальные случаи. Например, для множества $\{1,2\}$, правило, по которому получаются допустимые последовательности очень простое: необходимо и достаточно, чтобы первая и последняя цифра были разными.
Всегда приходим к одной из двух последовательностей $\{1,2,1,2....1,2\}$ или $\{2,1,2,1...2,1\}$

Что значит допустимая посследовательность?
Среди тех,что получаются удвоениями уже много слов для алфабита из двух букв.
Необходимых условий много. Я уже говорил о "непрерывности". Общее упорядочение. Если начать с некоторого места, где стоит k и вычеркнуть все числа не превосходящие k, то будет встречаться первый раз в естественном порядке k+1,k+2,... Аналогичное ему двойственное необходимое условие в обратном порядке.
Но вы под допустимым, даже не это (удовлетворение необходимому условию) имеете в виду.

[juna]

Я не совсем понял, что вы хотите уточнить. Допустимая последовательтность - такая, которая может быть получена по правилам maxal из возможных перестановок $\{1,2..N\}$. Если $N=2$, то перестановки всего две: $\{1,2\}$ и $\{2,1\}$. Для всех допустимых последовательностей из единиц и двоек в этом случае сформулированное правило необходимо, достаточно и тривиально.
Здесь, конечно, следует поправиться по количеству возможных последовательностей длины $k$, поскольку, по условию нужно использовать хоть раз каждую цифру.

[Руст]

Вроде уже договорились считать исходную последовательность 1,2,...,n Порядок вычисляется сразу и не имеет никакого отношения, какую букву обозначим первой, второй и т.д.
Поэтому допустимых последовательностей длины 4 из алфабита 2 всего:
1112, 1122,1212,1222.

[juna]

Так я тоже считал для 1,2, .., n, а потом умножал на n!. см. для n=3.
т.е. для n=3, k=4 - это 1123, 1223, 1233 - три штуки.

[maxal]

Артамонов Ю.Н. писал(а):

$a(3,6)=22\cdot 3!=132$ среди $3^6=729$ возможных

Из 1,2,3 у меня получилась только 21 допустимая последовательность длины 6.
А почему у вас 22?
Я что-то пропустил?

1 1 1 1 2 3 
1 1 1 2 2 3 
1 1 1 2 3 3 
1 1 2 1 2 3 
1 1 2 2 2 3 
1 1 2 2 3 3 
1 1 2 3 2 3 
1 1 2 3 3 3 
1 2 1 1 2 3 
1 2 1 2 2 3 
1 2 1 2 3 3 
1 2 2 1 2 3 
1 2 2 2 2 3 
1 2 2 2 3 3 
1 2 2 3 2 3 
1 2 2 3 3 3 
1 2 3 1 2 3 
1 2 3 2 2 3 
1 2 3 2 3 3 
1 2 3 3 2 3 
1 2 3 3 3 3

[juna]

Вы скорее всего правы, я там, возможно, не вычеркнул повторяющиеся. Во всяком случае, пересчитал, и новой последовательности, сверх ваших, не получил.
Т.е. допустимые последовательности длины 6 получаются из допустимых длины 3, 4, 5 путем удвоения 3, 2, 1 цифры соответственно, но при таких удвоениях могут встречаться повторения, которые нужно исключать.
P.S. Хорошо бы было составить программку.

[maxal]

Программу я написал. Получилась такая последовательность для длин 3,...,18:
1, 3, 8, 21, 54, 138, 355, 924, 2432, 6461, 17301, 46657, 126656, 345972, 950611, 2626253

[juna]

Интересная последовательность получилась. Пытался найти производящую функцию в виде полинома, по аналогии с подходящими известными $\frac{1}{(1-x)(1-2x-x^2-x^3-x^4)}=a_0+a_1x+a_2x^2+…$, но здесь известно, что $\lim\limits_{n\to\infty}\frac {a_{n}}{a_{n+1}}\to x_0$, где $x_0$ - корень полинома.
Для искомой же последовательности отношение ближайших видимо возрастает, во всяком случае на приведенной последовательности.
Можно ли в этом убедиться, расширив приведенную последовательность, например, до 40 членов?
Добавлено
Можно высказать гипотезу: $\lim\limits_{k\to\infty}\frac{a(N,k+1)}{a(N,k)}=N$
Добавлено
В принципе производящую функцию легко подобрать:
$\frac{1}{(1-x)(1-2x-x^{2}-x^{3}-3x^{6}-12x^{7}-30x^{8}-68x^{9}-164x^{10}-433x^{11}-1199x^{12}-3352x^{13}-9338x^{14}-25952x^{15})}$
Покрывает все члены приведенной последовательности. В реале полином видимо бесконечен.

[Руст]

Почему ищете производящую функцию без числителя. По всей видимости она рациональная функция.

[juna]

По сути, я лишь перевернул функцию, т.е. нашел ${(\sum{a_i}x^i)}^{-1}$.
Если производящая функция - отношение двух полиномов, то они имеют достаточно высокую степень и искать в лоб бессмысленно. Это следует из того, что отношение соседних членов последовательности не стабилизировалось. Поэтому я просил расширить до 40 членов.

[juna]

Решил вернуться к этой забытой теме.
Продолжим рассматривать последовательность для $N=3$.
Попробуем задать грамматику, порождающую язык удвоенных последовательностей.
$G(\{1, 2, 3\}, \{A, B, C, S\},\sigma, S)$
$\sigma :$
$\\S\to ABC\\A\to1|AA\\ B\to 2|AB|BB\\ C\to 3|CC|BC|ABC\\CA \to CACA$
Необходимость вроде есть, а вот достаточность - ?
Хотелось бы, чтобы указали последовательность, которую нельзя породить по этим правилам.
Получилась контекстно-зависимая грамматика.
Мне кажется, что контекстно-свободной построить не удастся, а значит простой распознаватель для этого языка получить также не получится.

[maxal]

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

Получилась такая последовательность для длин 3,...,18:
1, 3, 8, 21, 54, 138, 355, 924, 2432, 6461, 17301, 46657, 126656, 345972, 950611, 2626253

В OEIS она живет здесь: A135473

Кстати, эта последовательность была упомянута в числе 8 "ненавистных" последовательностей (которые кажутся простыми, но не поддаются попыткам анализа) в статье:
N. J. A. Sloane "Eight Hateful Sequences"
Эта статья написана в форме письма к Мартину Гарднеру, знакомящего его (вместе с читателями) с 8-ю "ненавистными" последовательностями.

[juna]

Последнее правило существенно и нужно, например, для вывода следующей цепочки:$12313123$

[maxal]

juna в сообщении #191186 писал(а):

Последнее правило существенно и нужно, например, для вывода следующей цепочки:$12313123$

Продемонстрируйте вывод этой строки в своей грамматике.