Digit Sum Invariant

Relevant wiki: Integer Equations - Stars and Bars

Let the number be

$N = \overline{d_1d_2d_3d_4d_5d_6}$

where $0 \leq d_i < 10$ represents each digit. Note that leading $0$ 's is allowed as $N$ can be any number between $1$ and $10^6$ . For example, $34$ will be encoded as $000034$ .

We want the sum of digits equal to 12. In other words,

$d_1+d_2+d_3+d_4+d_5+d_6 = 12$

The number of combinations of $(d_1, d_2, \dots , d_6)$ can be computed using the stars and bars technique, which gives ${17 \choose 5} = 6188$ .

However, there are cases where $d_i\geq 10$ . We should remove these cases. Furthermore, there cannot be cases such that more than one digit is greater or equal to 10 because their sum will exceed 12. Hence the cases for each digit greater or equal to 10 is mutually exclusive. Suppose $d_1 \geq 10$ , then we transform $d_1'=d_1-10$

$d_1' + 10 + d_2 + d_3 + d_4 + d_5 + d_6 = 12 \rightarrow d_1' + d_2 + d_3+d_4+d_5+d_6 = 2$

Again by using the stars and bars technique, the number of combinations is ${7 \choose 5}=21$ . Apply the same to all 6 digits and we have a total of $21 \times 6 = 126$ such cases. Hence the answer is

$6188-126 = 6062$

The solution is equal to the coefficient of $x^{12}$ in the expression $(x^0+x^1+x^2+x^3+x^4+ \dots +x^9)^{6}$

You can make wolfram-alpha do the work by entering

expand (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^6

and then picking out the coefficient of $x^{12}$ which is $\boxed{6062}$

Explanation

A little thought shows that the problem is equivalent to the number of compositions of 12 into 6 heaps with no heap being greater than 9, and with the possibility of some heaps being zero. The relationship between compositions and binomial-like coefficients is given here .