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

Добрый день.

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

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы