|
|
Составим таблицу некоторых значений g (n,k,k2)
k | ||||||
0 | 1 | 0 | 0 | 0 | 0 | |
1 | 1 | 1 | 9 | 45 | 285 | |
2 | 1 | 2 | 17 | 89 | 561 | |
3 | 1 | 3 | 24 | 131 | 820 | |
4 | 1 | 4 | 30 | 170 | 1055 | |
5 | 1 | 5 | 35 | 205 | 1260 | |
6 | 1 | 6 | 39 | 235 | 1430 | |
7 | 1 | 7 | 42 | 259 | 1561 | |
8 | 1 | 8 | 44 | 276 | 1650 | |
9 | 1 | 9 | 45 | 285 | 1695 | |
10 | 45 | 285 | 1695 | 10317 |
k | |||||
0 | 0 | 0 | 0 | 0 | |
1 | 1695 | 10317 | 62349 | 377739 | |
2 | 3345 | 20349 | 123003 | 745161 | |
3 | 4906 | 29820 | 180312 | 1092234 | |
4 | 6336 | 38471 | 232715 | 1409487 | |
5 | 7596 | 46067 | 278782 | 1688269 | |
6 | 8651 | 52403 | 317253 | 1920984 | |
7 | 9471 | 57309 | 347073 | 2101296 | |
8 | 10032 | 60654 | 367422 | 2224299 | |
9 | 10317 | 62349 | 377739 | 2286648 | |
62349 | 377739 | 2286648 | 13846117 |
Ответ:
а) первого типа: 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)
k | ||||||
0 | 1 | 0 | 0 | 0 | 0 | |
1 | 1 | 9 | 36 | 240 | 990 | |
2 | 1 | 8 | 28 | 196 | 826 | |
3 | 1 | 7 | 21 | 154 | 665 | |
4 | 1 | 6 | 15 | 115 | 510 | |
5 | 1 | 5 | 10 | 80 | 365 | |
6 | 1 | 4 | 6 | 50 | 235 | |
7 | 1 | 3 | 3 | 26 | 126 | |
8 | 1 | 2 | 1 | 9 | 45 | |
9 | 1 | 1 | 0 | 0 | 0 | |
10 | 45 | 120 | 870 | 3762 |
При использовании материалов активная ссылка на источник обязательна.