Количество последовательностей.

[Vaprus]

У нас есть k различных символов. Вопрос, как посчитать количество последовательностей длины n, содержащих подпоследовательность длины m<n. Вопрос, как вывести формулу, а не при помощи программы, а то было бы слишком просто. Есть у кого-нибудь идеи?

[arseniiv]

Vaprus в сообщении #649623 писал(а):

У нас есть k различных символов. Вопрос, как посчитать количество последовательностей длины n, содержащих подпоследовательность длины m<n.

$k^n$, если $n\ne 0$. (У пустой последовательности нет подпоследовательностей длины $-1$ и меньше, поэтому при нулевом $n$ ответ — тоже ноль.)

[alcoholist]

Vaprus в сообщении #649623 писал(а):

количество последовательностей длины $n$, содержащих подпоследовательность длины $m<n$

В чем состоит уточнение? Что имеется ввиду под "подпоследовательностью"?

[ИСН]

видимо, некая конкретная подпоследовательность ("слово").

[bot]

Ну, не совсем - слово (лучше подслово) входит плотненько, а здесь может и в разрядку, хотя это и несущественно, если разрядка зафиксирована.

[arseniiv]

Пока не сказано иное, разве не правильнее понимать любое слово?

[Dan B-Yallay]

Нет смысла упоминать о "любом" слове в постановке задачи.

[arseniiv]

Нет никакого. Но ТС так и не появился!