Пусть 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(30) = T(33) можно посчитать, используя рекуррентное соотношение, (путь для сильных духом — ответ будет достаточно большим) или посмотреть в таблицу для чисел трибоначчи.
Очевидно, 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