Determine the number of positive integer x where $x\leq 9,999,999$ and the sum of the digits in x equals 31.

Question

Determine the number of positive integer x where $$x\le 9,999,999$$ and the sum of the digits in x equals 31

How do you approach this question?

TEXTBOOK SOLUTION:

Let x be written in base 10. The answer to this problem is the number of nonnegative integer solutions to $$x_1+x_2+x_3+x_4+x_5+x_6+x_7 = 31,\text{ } 0\le x_i,\text{ } 1\le i\le7 \text{ but } x_j \gt 9$$

How does this make sense?, why are there 7 terms of x. This could be arbitrary large, no? Maybe a bad question? Or a bad solution?

Answer 1

Consider the number of digits in x and partitions of 31 into that many numbers where the maximum value in a part is 9. For example, consider that any 3 digit number will have at most 27 for the sum of its digits and so thus the cases to consider are 4,5,6 and 7 digits. This would be my suggestion as well as considering what re-arranging can be done at times along with adding zeros for the 4,5, and 6 cases as one could take a number like 4,999 which does add up to 31 and add zeroes into the number that complicates this a bit.

Answer 2

Inclusion-exclusion feels like it could become messy here.

My first attempt would probably be dynamic programming, building tables of the number of sequences of $n$ digits with sum $k$ for smaller $n$ (and $0\le k\le 31$) first.