Количество 6значных чисел где 7ки группами

[2old]

1. Посчитать все шестизначные числа такие, в которых семерки идут группами (либо их вообще нет).
(Например: $772771$, $777177$, $345890$ допустимые, а $711111$, $777173$ недопустимые)
2. Посчитать все шестизначные числа такие, в которых семерки есть и идут группами.

Пусть $a_n$ количество n-буквенных слов, в которых если есть семерки, то идут группами и они начинаюся не с $0$. Пусть $b_n$ количество n-буквенных слов, в которых если есть семерки, то они идут группами и они начинаются с $0$. Ответ на вопрос 1 задачи есть $a_6$, на вопрос 2 $a_6-8\cdot9^5$.

Рассмотрим $a_n$. Если начинается с $7$, то и вторая цифра должна быть семерка. Третья может быть $0$ и может быть любая другая. Получаем, $a_{n-2}+b_{n-2}$. Если начинается не $7$, т.е. c $\{1,2,3,4,5,6,8,9\}$ -- $0$ не может быть по определению $a_{n}$, имеем $8$ вариантов. Вторая цифра может быть любая, тогда получаем $8(a_{n-1}+b_{n-1})$.
Итого:

$$a_n=a_{n-2}+b_{n-2}+8(a_{n-1}+b_{n-1})$$

Рассмотрим $b_n$.
Вторая цифра может быть любой, так что тут

$$b_n=b_{n-1}+a_{n-1}$$

Заметим, что $a_{n-1}=b_{n}-b_{n-1}$. Т.е. если мы научимся вычислять (или найдем в замкнутой форме) последовательность $b_n$, то по ней последовательность $a_n$ восстанавливается тут же.

Первое уравнение с учетом $b_n=b_{n-1}+a_{n-1}$ переформулирется как:

$$a_n=b_{n-1}+8b_{n}$$

Или, что тоже самое:

$$a_{n-1}=b_{n-2}+8b_{n-1}$$

И исключая $a_{n-1}$ получаем:

$$b_{n}-b_{n-1}=b_{n-2}+8b_{n-1}$$

В итоге:

$$b_{n}=b_{n-2}+9b_{n-1}$$

Это линейное реккурентное уравнение. Легко получить замкнутое выражение, но корни иррациональные, поэтому просто вычислим до $b_7$ и получим $a_6=b_7-b_6$.
$b_1=1$ (единственное однозначное с первым $0$ это $0$)
$b_2=9$ (единcтвенное двузначное с первым $0$ и с $7$ это $07$, не подходит, остальные подходят, $00,01,02,03,04,05,06,08,09$)
$b_3=1+9\cdot9=1+9^2=82$
$b_4=b_2+9b_3=9+9(1+9^2)=2\cdot9+9^3=747$
$b_5=b_3+9b_4=1+9^2+9(2\cdot9+9^3)=1+3\cdot9^2+9^4=6805$
$b_6=b_4+9b_5=61992$
$b_7=b_5+9b_6=564733$

И наконец:

$$a_6=b_7-b_6=502741$$

Всего шестизначных чисел, где 7ки либо отсутствуют, либо идут блоками $a_6=502741$, шестизначных чисел, где обязательно 7ки есть и идут блоками $a_6-8\cdot9^5=30349$

Где-то я ошибаюсь. Правильный $a_6=505449$. Помогите разобраться, пожалуйста.

[whitefox]

Возможна только одна либо две группы семёрок. В первом случае группа может иметь размер: $2, 3, 4, 5, 6.$ Во втором либо $(2,2),$ либо $(2,3).$ Рассмотрите каждый случай по отдельности. Сколько, например, положений может иметь единственная группа длины два? Для каждого такого положения возможно либо $8\cdot9^3,$ либо $9^4$ чисел (первый случай когда 7-ка не в самой левой позиции, так как первая цифра не может быть нулём).

[2old]

whitefox
Спасибо, так я умею, хотелось мое решение довести до конца

[ewert]

whitefox в сообщении #1031402 писал(а):

Для каждого такого положения возможно либо $8\cdot9^3,$ либо $9^4$ чисел (первый случай когда 7-ка не в самой левой позиции, так как первая цифра не может быть нулём).

Проще допустить начальный ноль и вычесть из количества шестизначных комбинаций количество пятизначных. Там много чего сократится, и останется лишь $5\cdot9^4+9^6-9^5+2\cdot9+3\cdot9^2-9$.

[whitefox]

ewert в сообщении #1031570 писал(а):

Там много чего сократится, и останется лишь $5\cdot9^4+9^6-9^5+2\cdot9+3\cdot9^2-9$

Можно и ещё подсократить — $85031_9$

[ewert]

whitefox в сообщении #1031574 писал(а):

Можно и ещё подсократить — $85031_9$

Ну я-то выписал слагаемые, остающиеся после только буквального сокращения (потому даже не стал объединять $2\cdot9-9$).

И, кстати, Ваше замечательное сокращение чуток сбито.

[whitefox]

ewert в сообщении #1031576 писал(а):

И, кстати, Ваше замечательное сокращение чуток сбито.

Что Вы имеете ввиду?

[ewert]

whitefox в сообщении #1031579 писал(а):

Что Вы имеете ввиду?

А чему равен его остаток от деления на девять?...

[whitefox]

А, ну да
$850310_9$