Научно-исследовательская работа школьников в РБ (стр. 6 из 8)
а) первого типа: 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 |
| k |  |  |  |  |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 7722 | 28182 | 190740 | 796521 |
| 2 | 6412 | 23310 | 157926 | 659835 |
| 3 | 5131 | 18564 | 125922 | 526449 |
| 4 | 3906 | 14053 | 95449 | 399334 |
| 5 | 2771 | 9907 | 67382 | 282126 |
| 6 | 1766 | 6271 | 42711 | 178971 |
| 7 | 936 | 3300 | 22506 | 94380 |
| 8 | 330 | 1155 | 7887 | 33099 |
| 9 | 0 | 0 | 0 | 0 |
| | 28974 | 104742 | 710523 | 2970715 |
Составим таблицу некоторых значений r (n,k,k2)
| k |  |  |  |  |  |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 10 | 45 |
| 2 | 1 | 2 | 3 | 29 | 126 |
| 3 | 1 | 3 | 6 | 56 | 235 |
| 4 | 1 | 4 | 10 | 90 | 365 |
| 5 | 1 | 5 | 15 | 130 | 510 |
| 6 | 1 | 6 | 21 | 175 | 665 |
| 7 | 1 | 7 | 28 | 224 | 826 |
| 8 | 1 | 8 | 36 | 276 | 990 |
| 9 | 1 | 9 | 45 | 330 | 1155 |
 | 10 | 45 | 165 | 1320 | 4917 |
| k |  |  |  |  |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 285 | 1155 | 9042 | 33099 |
| 2 | 810 | 3300 | 25806 | 94380 |
| 3 | 1531 | 6271 | 48982 | 178971 |
| 4 | 2406 | 9907 | 77289 | 282126 |
| 5 | 3396 | 14053 | 109502 | 399334 |
| 6 | 4499 | 18564 | 144486 | 526449 |
| 7 | 5586 | 23310 | 181236 | 659835 |
| 8 | 6732 | 28182 | 218922 | 796521 |
| 9 | 7887 | 33099 | 256938 | 934362 |
| | 33099 | 137841 | 1072203 | 3905077 |
Ответ:
а) третьего типа: 2970715; четвертого типа: 3905077
б)
3. Используя метод рекуррентного соотношения для подсчёта количество волнистых чисел, можно составить рекуррентную формулу для любой конфигурации знаков ”<”,”>”,”
”,” ”,”=". Какой знак на текущем шаге вычисления рекуррентного соотношения можно легко определять по остатку от деления текущего i-2 ( 
) на количество различных знаков до повторения.Например, выведем формулу для нахождения количества волнистых чисел типа:
Количество различных знаков до повторения - 3.