элементарная комбинаторика, алфавит из трех букв, кол-во сло

[ОЛЬГА1313]

В алфавите племени Мумба-Юмба всего три буквы. Смысл имеют слова, в
записи которых среди любых трех подряд идущих букв ровно две – различные.
Сколько двадцатибуквенных слов в языке племени Мумба-Юмба имеют
смысл?

[PAV]

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

[ОЛЬГА1313]

У меня другое соображение. По всем раскладам видно, что в этих словах каждые две буквы одинаковые. Пусть эти одинаковые буквы обозначим как а, в, с. Тогда в слове сочетания этих букв например ававававав, асасасасас, авсавсавса и т.д. Т.е. получается 10 ячеек, в каждой по две одинаковые буквы. Теперь надо применить какую-то формулу, которую я не могу вспомнить и нигде найти. Помогите, пожалуйста!

[PAV]

То, что Вы написали, я не понимаю. Что означает

ОЛЬГА1313 писал(а):

в этих словах каждые две буквы одинаковые

Рекомендую все-таки подумать над тем путем, который я наметил выше, из него получается очень простое и понятное решение.

[Руст]

Пусть f(n) количество слов c n буквами, окончивающихся на 2 одинаковые буквы, g(n) на 2 разные буквы. Тогда f(n+1)=g(n),g(n+1)=2f(n)+g(n),f(3)=6=g(3). Отсюда g(n)=2^n+2(-1)^n. Общее количество слов f(n)+g(n)=3*2^(n-1).

[PAV]

Руст

Ответ не такой, хотя рассуждение в целом правильное. У меня получается $9\cdot2^{n-2}$

Например, для n=3 на самом деле 18 слов, а у Вас получается 12

[Руст]

Да, я неправильно посчитал начальное условие g(3)=12, а не 6.

[Руст]

Проще сразу указать, что слово из n букв расширяется до слова из n+1 букв двумя способомами независимо от окончания. Количество подходящих двухбуквенных 9 (любые слова из 3 буквенного алфабита).

[PAV]

Руст писал(а):

Проще сразу указать, что слово из n букв расширяется до слова из n+1 букв двумя способомами независимо от окончания. Количество подходящих двухбуквенных 9 (любые слова из 3 буквенного алфабита).

Да, я ровно это решение и имел в виду.