Задание по дискретной математике Сколько существует последовательностей длины n из цифр от 1 до 9, в которых каждый блок из одинаковых нечётных чисел имеет чётную длину?
Пример подходящей последовательности: 67788111144455555528
Пример не подходящей последовательности: 11233455677899333552

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи можно воспользоваться динамическим программированием.

Пусть dp[i][j][k] - количество последовательностей длины i, заканчивающихся на числе j и содержащих k блоков одинаковых нечетных чисел длиной, не превышающей 2.

Имеем следующие рекуррентные соотношения:
dp[i][j][k] = сумма по всем предыдущим числам j' (от 1 до 9), отличным от j, dp[i-1][j'][k] (если k=0) или dp[i-1][j'][k-1] (если k>0)

Начальные условия:
dp[1][j][0] = 1 (для всех j от 1 до 9)
dp[1][j][1] = 0

Вычисляем значения dp[i][j][k] для всех i, j, k от 2 до n и суммируем все значения dp[n][j][k] для всех j от 1 до 9 и для всех k от 0 до 2, чтобы получить искомое количество последовательностей.

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