Количество слов длины $k$ с некоторым ограничением

[mgtriffid]

Здравствуйте!

Как часть более сложной задачи, возник вопрос:

Сколько существует двоичных слов длины $k$ таких, что в них нет подслов, состоящих только из единиц, длины меньше $n$? (разумеется, $k>n$).

В принципе, достаточно даже знать хотя бы старший член.

Думал полторы недели, пока получаются только ужасно огромные суммы.

Приношу извинения за (возможно) корявую формулировку.

[bot]

Не понимаю формулировку. Если нет коротких подслов, состоящих только из единиц, то не может быть и длинных.

Так что ли?

Требуется найти количество всех бинарных слов длины $k>n$, в которых любая единичка содержится в подслове из $n$ единиц.

[mgtriffid]

Да, Вы правы. Любая единичка содержится в подслове из $n$ единиц. Спасибо за поправку!

[sup]

Ниже в примере $n=2$.
Пусть у нас в строке длины $k$ ровно $l$ "сплошных" групп из 1. Например, в строке
001111011011100111111 их 4. Добавим в строку спец. символы # в начале и конце всякой такой группы:
00#1111#0#11#0#111#00#111111#
Таким образом сейчас в строке $k+2l$ символов. Из каждой 1-группы выбрасываем $n$ единиц
00#11#0##0#1#00#1111#
Осталось $k+2l-nl$ символов. Из 0-групп зажатых между двумя # выбрасываем один 0.
00#11####1#0#1111#
Таких нулей $l-1$. Осталось $K=k+2l-nl-l+1=k+1+l-nl$ символов.
Заменяем 0 и 1 на *, получим
**#**####*#*#****#
Я утверждаю, что по этой строке исходная восстанавливается однозначно.
Сколько таких строк? Очевидно - $C_K^{2l}$.
Осталось просуммировать это дело по $l$.

[bot]

Только что взялся посчитать и зашёл написать, а тут уже есть. Получилось похоже, но не так:
$\sum\limits_{l=0}^{[\frac{k+1}{2n}]}C_{k+1-l(n-1)}^{2l+1}$
Что-то не верится, что это одно и то же. Тогда кто-то ошибся.

[TOTAL]

bot в сообщении #384899 писал(а):

Тогда кто-то ошибся.

Кто-то может проверить для $k=4, n=3.$

[bot]

Да я уже проверил на коленке по дороге домой. Ошибся я - по-дурному, а и другой раз ещё дурнее: в верхнем пределе суммирования.
После поправки всё совпало.