Задача
ALG-B1-M05-P013 Сколько последовательностей
#13
★★★★☆ Уровень 4 из 5
Сколько последовательностей \(a_1,\ldots,a_n\) натуральных чисел имеют минимальный член не больше \(4\) и \(|a_{i+1}-a_i|\le1\)?
Зафиксируйте разности и минимальный член.
Разностная последовательность имеет \(n-1\) членов, каждый из которых равен \(-1,0,1\), всего \(3^{n-1}\) вариантов.
Для каждой разностной последовательности все исходные последовательности получаются прибавлением одной и той же константы ко всем членам. Ровно по одной из них имеет минимум \(1,2,3,4\). Поэтому ответ \(4\cdot3^{n-1}\).
Это подготовка к более трудной задаче с запрещёнными значениями.