Обусловьте количество последовательностей из нулей и единиц длины 30, в которых

Пусть 0(n) количество последовательностей длины n, заканчивающихся на 0, 1(n) количество последовательностей длины n, у которых на конце ровно одна единица, 11(n) количество последовательностей длины n, у которых на конце ровно две единицы.

Явно, 0(n + 1) = 0(n) + 1(n) + 11(n) ноль в конец можно приписать хоть какой последовательности; 1(n + 1) = 0(n), 11(n + 1) = 1(n)  если приписать на конец 1, то получится одна единица, если на конце был ноль, и две единицы, если на конце была одна единица.

Нас интересует t(n) = 0(n) + 1(n) + 11(n) общее количество последовательностей длины n. Получим рекуррентную формулу для t:
t(n + 3) = 0(n + 3) + 1(n + 3) + 11(n + 3) = 0(n + 3) + 0(n + 2) + 0(n + 1) = t(n + 2) + t(n + 1) + t(n)

t(1) = 2 (последовательности 0 и 1)
t(2) = 4 (00, 01, 10 и 11)
t(3) = 7 (000, 001, 010, 011, 100, 101, 110)

Получилась последовательность трибоначчи, сдвинутая на 3 (числа трибоначчи определяются так: T(0) = T(1) = 0, T(2) = 1, T(n + 3) = T(n + 2) + T(n + 1) + T(n))

t(30) = T(33) можно посчитать, используя рекуррентное соотношение, (путь для сильных духом ответ будет довольно великим) либо поглядеть в таблицу для чисел трибоначчи.

t(30) = T(33) = 98 950 096