Ответ:

а) первого типа: 11559469; второго типа: 13846117

б)

Лемма 2. Обозначим через t (n,k1,k2) - количество n-значных волнистых чисел третьего типа, начинающихся с цифры k1 и заканчивающиеся на цифру k2, r (n,k1,k2) - количество n-значных волнистых чисел четвертого типа, начинающихся с цифры k1 и заканчивающиеся на цифру k2. Тогда

и

Также и

Доказательство. Рассмотрим n-значные волнистые числа третьего типа.

Нетрудно заметить, как они получаются. Берутся все n-1-значные волнистые числа и, в зависимости от текущего знака (”", ”<”, ”>", ””), дописывается каждому числу цифра, меньшая, равная или большая последней, т.е. чтобы найти количество n-значных волнистых чисел, заканчивающихся на k, надо найти сумму всех количеств n-1-значных чисел заканчивающихся на цифры от 0 до k, или от 0 до k+1, или от k+1 до 9, или от k до 9.Т. к. на каждом шаге мы корректно вычисляем волнистые числа, то нет необходимости знать всё число: все зависит от последней цифры.

Следовательно, можно составить рекуррентную формулу, которая будет корректно вычислять количество n-значных волнистых чисел третьего типа начинающихся на цифру k1 и заканчивающихся на цифру k2.

Рассмотрим рекуррентную формулу для волнистых чисел третьего типа.

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

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

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

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

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

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

Аналогично, выводится рекуррентное соотношение для волнистых чисел четвертого типа.

Теорема 2. Количество n-значных волнистых чисел третьего типа:

и количество n-значных волнистых чисел четвертого типа:

.

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