Сколько можно составить слов длины n из русских букв, таких что в них есть слово X?

Question

[Владимир Петриго]

Добрый день.

Слушаю курс по дискретной математике и в задачнике очень часто встречаются задания вроде "Сколько можно составить слов длины n из русских букв, что в нем есть слово X?" или "Сколько можно составить слов длины n из русских букв, что в нем нет слова X?". Правильно ли я понимаю, что в первом случае задача сводится к нахождению всех размещений с повторением оставшихся n - len(x) букв?
То есть, например, количество слов длины 11, содержащих подслово "привет":
Слово "привет" - длина 6
Ещё 5 символов могут быть перед "привет", либо 4 символа до и 1 после, 3 до – 2 после и т.д.
Получаем следующий результат:


Верно ли я рассуждаю?

Answer 1

[localghost]

Возможно, чего-то не понял, но откуда у вас степени ниже пятой? Если, к примеру, 4 символа перед, а 1 после - вы считаете это как 33^4 + 33? Почему, чем это отличается от случая просто 5 символов перед?

По-моему, следует считать так: кроме "привет" есть еще пять букв. Вариантов набрать эти пять букв - 33^5. Когда у нас уже есть пять букв, слово "привет" можно впихнуть туда шестью разными способами. Итого 6 * 33^5.

Кроме того, в общем случае надо учесть, что некоторые "слова" мы могли посчитать не один раз. Скажем, если всего букв 12, то "приветпривет" посчитан лишний раз. Здесь, кажется, такого нет.

Comments

[Владимир Петриго]

Да, спасибо.. Я как всегда напутал.

[localghost]

Не за что. Придет с практикой :)