Каждая цифра делится на следующую, сколько таких чисел?

[Ktina]

Сколько существует семизначных чисел, в которых каждая цифра, кроме последней, делится на следующую за ней справа цифру?
(Кубок Памяти Колмогорова)

Кроме нудного перебора случаев мне в голову ничего не пришло. Очевидно, нулей в таком числе нет. Если первая цифра 1, то таким числом может быть только 1111111. Если первая цифра 2, 3, 5 или 7, то имеем по 7 вариантов. Если 4 или 9, то по 28 вариантов. Если 6, то 49, а если 8, то 84 варианта. Итого, 218.

Есть ли какой-нибудь обходной путь? И как обобщить задачу до $n$ - значных чисел?

[Xaositect]

Записать рекуррентные уравнения на $P_k(n)$ --- количество $n$-значных чисел с первой цифрой $k$, удовлетворяющих условию, и решить их. Получается $\frac16 n^3 + \frac52 n^2 + \frac{16}3 n + 1$.

[Ktina]

Xaositect в сообщении #868244 писал(а):

... $\frac16 n^3 + \frac52 n^2 + \frac{16}3 n + 1$.

Так 217 получается.

-- 27.05.2014, 01:54 --

Ой, там же $+1$ в конце, пардон