Ответ:

а) третьего типа: 2970715; четвертого типа: 3905077

б)

3. Используя метод рекуррентного соотношения для подсчёта количество волнистых чисел, можно составить рекуррентную формулу для любой конфигурации знаков ”<”,”>”,””,””,”=". Какой знак на текущем шаге вычисления рекуррентного соотношения можно легко определять по остатку от деления текущего i-2 () на количество различных знаков до повторения.

Например, выведем формулу для нахождения количества волнистых чисел типа:

Количество различных знаков до повторения - 3.

q (n,k1,k2) - количество n-значных волнистых чисел данного типа, начинающихся с цифры k1 и заканчивающиеся на цифру k2.

Начальные значения , т.е. есть только по одному однозначному волнистому числу, начинающемуся на i и заканчивающемуся на i ().

Пусть , тогда по остатку от деления i-2 на 3 определяем текущий знак:

Если (i-2) mod 3=0, является суммой всех количеств i-1-значные волнистых чисел данного типа, которые начинаются на k1 и у которых последняя цифра меньше либо равна k2.

Если (i-2) mod 3=1, равно количеству i-1-значных волнистых чисел данного типа, которые начинаются на k1 и у которых последняя цифра равна k2.

Если (i-2) mod 3=2, является суммой всех количеств i-1-значные волнистых чисел данного типа, которые начинаются на k1 и у которых последняя цифра больше либо равна k2.

В итоге получаем формулу:

и

Количеством n-значных чисел данного типа будет:

Составим таблицу некоторых значений q (n,k,k2)