Еще одна школьная задачка - Public forum of MSU united student networks

Заметим, что из предыдущего разряда может переноситься или один или ноль. Поэтому у удвоенного числа каждая цифра или удвоенная цифра обычного, либо удвоенная цифра + 1.
Назовем цифру "накрытой", если в ее разряд единица переносится. Справа от каждой накрытой стоит одна из цифр 5, 6, 7, 8, 9.
Рассмотрим 5 пар 0, 5; 1, 6; 2, 7; 3, 8; 4, 9. В каждой паре оба при удвоении дают одинаковую последнюю цифру, поэтому в нашем исходном числе для каждой такой пары одна цифра должна быть накрыта, а вторая нет. Назовем такие числа правильно накрывающимися.
Любое подходящее число должно быть правильно накрывающимся с первой цифрой не более 4.
С другой стороны любое такое число будет подходящим, поскольку совпадение цифр может возникнуть только при удвоении двух цифр из одной пары.
Значит надо подсчитать число правильно накрывающихся чисел с первой цифрой 4 или менее.

Найдем 5 мест для цифр 5, 6, 7, 8, 9 из 9 возможных. При этом слева от них будут накрытые цифры. Для каждой ненакрытой из них должна найтись накрытая парная цифра.

Значит если мы выберем 5 мест для этих 5 цифр и при этом k из них окажутся накрытыми, то расставить их можно будет 5! способами, а остальные 5 цифр k! (5-k)! способами.
Итого надо посчитать число выбора 5 мест из 9 с k накрытиями, умножить на 5! k! (5-k)! и сложить по k от 0 до 4.

Выборы 5 мест с k накрытиями можно считать руками.
0 накрытий это всего один способ.
1 накрытие - это одна пара и 3 одиночных числа на 9 позициях, т.е. выбираем 4 позиции из 8 и выбираем одну, на которой будет пара. 4С^4_8
2 накрытия - это одна тройка и две одиночных (3 С^3_7) или две пары и одна одиночная (3 С^3_7)
3 накрытия - это четверка и одиночный (2 С^2_6) или тройка и двойка (2 C^2_6)
4 накрытия - это пятерка (C^1_5)

Итого нам необходимо выбрать для 5 6 7 8 9 пять мест из девяти возможных позиций. Для каждой такой расстановки если k из этих цифр