Как найти количество чисел от 1 до 10^9, имеющих сумму цифр = x?
Не можете найти закономерность - сделайте перебор.
Я не думаю, что какая-то закономерность найдется. Просто решите задачу, которая выглядит как-то так: Найти все наборы из N чисел, дающие число X, первое число не нулевое. Решив эту задачу получить ответ для вашей очень легко.
Другой вариант конечно ещё проще, просто пробежать все числа и посчитать сумму чисел.
Плюс первого решения в том,  что ограничение 10^9 легко преодолевается и не надо думать о переполнениях и прочем.