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

Solution 1:

We have to count the words of length $7$ over the alphabet $\{0,1,2,\ldots,9\}$ which sum to $31$. (Allowing leading zeros automatically takes care of the numbers having less than seven decimal places.) This number can be realized as coefficient of $x^{31}$ in the expansion of $$F(x):=(1+x+x^2+\ldots+x^9)^7\ ,$$ because expanding $F$ according to the distributive law produces $10^7$ terms with coefficient $1$, each of them coming from one of the mentioned words, and then these terms can be collected according to increasing powers of $x$. The binomial series gives $$F(x)=\left({1-x^{10}\over 1-x}\right)^7=\bigl(1-7x^{10}+21x^{20}-35x^{30}-\ldots\bigr)\sum_{k=0}^\infty {7+k-1\choose k} x^k\ .$$ Summing the coefficients of the resulting $x^{31}$-terms we obtain $$N={37\choose 31}-7{27\choose 21}+21{17\choose 11}-35{7\choose 1}=512\,365\ .$$

Solution 2:

One approach is to use stars and bars with inclusion-exclusion

$x_1 \; to \; x_7$ is there because there can be maximum $7$ digits ($7$ "cells"), with $0 \le x_i \le 9$

Using the formula $\binom{n+k-1}{k-1},\; with\; n = 31, k = 7,$
and excluding invalid cases by forcibly putting $10$ in combos of one or more "cells", and reducing the sum to be obtained accordingly, we get

$\binom{37}6 - \binom71\binom{27}6 + \binom72\binom{17}6 - \binom73\binom76 = 512,365$