Криптоландия и слова.

В Криптоландии используется алфавит, состоящий из четырёх латинских букв a,b,c,d. Любая последовательность букв алфавита будет словом криптоландского языка при выполнении единственного ограничения: если в последовательности есть хоть одна буква "a", то тогда в ней обязательно должны встретиться две буквы "a" подряд. Например, последовательности baacda,aabb,ddd являются словами, а последовательности bcadda,abba – не являются. Найдите число слов длины 8 в криптоландском языке.

• Решение

Решение

Множество всех последовательностей длины k состоит из m^k последовательностей. Это множество разбивается на три непересекающихся между собой подмножества: 1.Последовательностей, не содержащих a. 2.Последовательностей, содержащих a, но не содержащих двух подряд идущих таких букв. 3.Последовательностей, содержащих a, в которых встречаются две подряд идущие такие буквы. Чтобы решить задачу, нужно найти число последовательностей во втором подмножестве и вычесть его из числа m^k. В свою очередь, множество последовательностей второго типа можно разбить на непересекающиеся подмножества, в которые входят последовательности, содержащие 1,2,…,⌊(k+1)/2⌋ (целая часть снизу) букв "a". Отсюда несложно получить формулу для числа последовательностей второго типа:

 ∑C_t(m-1)^k-t,

Здесь суммирование ведется по всем t от 1 до ⌊(k+1)/2⌋,а C_t - число сочетаний из k+1-t по t.
• Ответ

Ответ

27466