Сколько слов длины

ИЗМЕНЕНО ДЛЯ ДОБАВЛЕНИЯ : На этот вопрос теперь по существу дан ответ; пожалуйста, смотрите эту запись в блоге для более подробной информации. Спасибо всем, кто разместил комментарии и ответы здесь.

---

ОРИГИНАЛЬНЫЙ ВОПРОС

Это, надеюсь, более умная и информированная версия вопроса, который я задал на MathOverflow. Когда я задал этот вопрос, я даже не знал названия области математики, в которой находилась моя проблема. Теперь я почти уверен, что она лежит в «Алгоритмической комбинаторике с частичными словами». (Недавняя книга на эту тему здесь .)

Я хочу составить список слов по букв. Каждое слово имеет длину ровно . Дело в том, что если находится в списке, где - это подстановочный знак / символ безразличия, то больше никогда не появится в списке. (То же самое верно, если или если и, следовательно, запрещенное подслово - .)$l$$k$$a \lozenge ^j b$$\lozenge$$a \lozenge ^j b$$a=b$$j=0$$ab$

Пример, где и :$k=4$$l=5$

$abcd$
$bdce$
$dcba$ <- запрещено, потому что появился в строке над <- запрещено, потому появился в первой строке$dc$
$aeed$$a \lozenge \lozenge d$

Литература по «частичным словам, которых можно избежать», которые я нашел, была бесконечной - в конце концов, некоторый шаблон слов неизбежен, если размер слова достаточно велик. Я хотел бы найти окончательные версии таких теорем. Итак, вопрос:

При условии, что в алфавите из букв есть частичное слово формы , сколько слов длины его избегают и могут ли они быть явно созданы за полиномиальное время?$a \lozenge^j b$$l$$k$

Я не ожидаю, что вышеупомянутый вопрос будет трудным, и, если нет тонкости, которую я пропускаю, я мог бы вычислить это сам. Настоящая причина, по которой я размещаю информацию на этом сайте, заключается в том, что мне нужно знать гораздо больше о свойствах таких списков слов для моего приложения, поэтому я надеюсь, что кто-то может ответить на следующий вопрос:

Это было изучено в целом? Какие документы рассматривают не только то, является ли частичное слово неизбежным, но и «сколько времени это займет», прежде чем оно станет неизбежным?

Спасибо.

Вот особый случай: количество двоичных слов длины $k$ таким образом, что два не появляются последовательно $F(k+3)$, где $F(n)$ это $n^{th}$ Число Фибоначчи (начиная с $F(1)=1, F(2)=1$). Доказательство - через представительство Zeckendorf .

РЕДАКТИРОВАТЬ: Мы можем расширить этот начальный частный случай в немного больший частный случай $a\lozenge^0a$, Рассмотрим строки длины$k$ по алфавиту размера $l+1$ такое что письмо $a$не появляется дважды подряд. Позволять$f(k)$быть количеством таких строк (которые мы будем называть «действительными»). Мы утверждаем, что:

$$f(k) = l*f(k-1) + l*f(k-2)$$ $$f(0) = 1, f(1) = l+1$$ Интуиция заключается в том, что мы можем построить правильную строку длины $k$ либо: а) примыкает к любому из $l$ буквы, которые не являются $a$ допустимая строка длины $k-1$или б) к письму $a$ а затем любое другое письмо, кроме $a$ допустимая строка длины $k-2$,

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

$$f(k) = \sum_{i=0}^{k} {{k+1-i}\choose{i}} l^{k-i}$$ где мы понимаем ${{n}\choose{i}} = 0$ когда $i>n$,

РЕДАКТИРОВАТЬ № 2: Давайте выберем еще один случай - $\lozenge^0 b, a \neq b$, Мы будем называть строки более$l$элемент, который не содержит подстроки $ab$, "действительный" и пусть $S_k$ обозначим множество допустимых строк длины $k$, Далее давайте определимся$T_k$ быть подмножеством $S_k$ состоящий из строк, начинающихся с $b$ а также $U_k$ быть теми, кто не начинается с $b$, Наконец, пусть$f(k) = |S_k|$, $g(k) = |T_k|$, $h(k) = |U_k|$,

Мы наблюдаем, что $g(0)=0, h(0)=1, f(0)=1$ а также $g(1)=1, h(1)=l-1, f(1)=l$, Далее мы выводим следующие рецидивы:

$$\begin{eqnarray} g(k+1) &=& f(k) \\ h(k+1) &=&(l-1)*h(k) + (l-2)*g(k) \end{eqnarray}$$ Первое связано с тем, что добавление $b$ к началу любого элемента $S_k$ производит элемент $T_{k+1}$, Второе происходит из наблюдения, что мы можем построить элемент$U_{k+1}$ добавив любой символ, но $b$ к передней части любого элемента $U_{k}$ или добавив любой символ, кроме $a$ или $b$ к передней части любого элемента в $T_k$,

Далее мы переставляем рекуррентные уравнения для получения:

$$\begin{eqnarray} f(k+1) &=& g(k+1) + h(k+1) \\ &=& f(k) + (l-1)*h(k) + (l-2)*g(k) \\ &=& f(k) + (l-1)*f(k) - g(k) \\ &=& l*f(k) - f(k-1) \end{eqnarray}$$

Мы можем получить довольно непрозрачное решение в этой замкнутой форме для этого повторения, немного покопавшись в генерируемой функции или, если нам лень, направиться прямо к Wolfram Alpha . Однако, немного погуглив и поглядывая в OEIS , мы обнаруживаем, что на самом деле имеем:

$$f(k) = U_k(l/2)$$ где $U_k$ это $k^{th}$ Чебышевский многочлен второго рода (!).

Совершенно другой подход к первому вопросу повторно использует ответы на недавний вопрос о генерации слов на обычном языке : достаточно применить эти алгоритмы для длины$k$ на обычном языке $\Sigma^\ast a\Sigma^j b\Sigma^\ast$ где $\Sigma$ is the alphabet.

Обновлено: этот ответ неверен :

при условии, $j$исправлено, мы можем посчитать количество способов паттерна$a\lozenge^j b$ могут быть сопоставлены: первый $a$ символ может быть сопоставлен в некоторой позиции $1\leq i\leq k-j-1$, и у нас есть $l^{i-1}$ возможности до этого момента, $l^j$ между $a$ а также $b$, а также $l^{k-j-i-1}$ для оставшейся части строки, таким образом, в общей сложности

$$\sum_{i=1}^{k-j-1}l^{i-1}\cdot l^{j}\cdot l^{k-j-i-1}=(k-j-1)l^{k-2}$$ случаев. Как отметил Цуёси Ито в комментариях, это количество не совпадает с количеством разных слов$a\lozenge^j b$поскольку одно слово может соответствовать одному и тому же шаблону по-разному. Например$aa$ соответствует три раза в $aaaa$, $ab$ два раза в $abab$, а также $a\lozenge b$ два раза в $aabb$, Мы можем попытаться подсчитать количество способов сопоставления с образцами несколько раз и показать выражение «включение-исключение», но способы, которыми может перекрываться шаблон, делают это слишком длинным.

---

По первому вопросу, при том понимании, что $j$ не фиксируется, то есть мы хотим избежать встраивания слова $ab$:

• или $a$ первый символ никогда не появляется, что составляет $(l-1)^k$ возможные слова,
• или $a$ появляется первым в некоторой позиции $1\leq i\leq k$тогда мы не можем использовать $b$ в оставшейся части слова: есть $(l-1)^{i-1}$ выбор фактора до $a$, а также $(l-1)^{k-i}$ выбор для остатка, давая в общей сложности $\sum_{i=1}^k(l-1)^{i-1}\cdot(l-1)^{k-i}=k(l-1)^{k-1}$возможные слова Будь то$a=b$ не имеет значения.

По второму вопросу мне нечего предложить; Существует связь с встраиванием слов, но результаты, которые я знаю о плохих последовательностях для леммы Хигмана, применяются не сразу.