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