Find the total number of 7-digit

Question

Find the total number of 7-digit natural numbers whose digits sum is 20.

Solution: This is not a exactly answer, as well we can use a way to subtracts the cases when exists a digit greater than $9$.

Let $x_1,\cdots, x_7$ the digits.

As well there are ${25\choose 6}$ ways to give us the sums of numbers, but this permits $x_i>9$.

We need to analyze a few cases (or you can abbreviate this if you're awesomely intellectual, I'm not).

$Case~1)$ All the cases (ways) where $x_1>9$ and the others are less than or equal to $9$.

Then you need to write $x_1=9+x_1'$. And why is this a particular case? Because Stars and Bars here admits numbers equal to zero, and in this ways $0$ is permitted.

But see that this case counts ways that is not permitted by our hypothesis, is when$ (x_1,x_i,x_j,\cdots, x_{j+3})=(10,10,0,\cdots,0) $

To calculate the ways it's easy only have that $x_1'+x_2+\cdots +x_7= 11$

Then clearly all the ways are ${16\choose 6} - 6$

$Case~2)$ Some $x_i\neq x_1$ is greater than $9$.

This is only ${15\choose 6} $ but for individual digits, then all the ways are $6 {15\choose 6} $

This give us that the quantity of numbers such that the sum of digits is $20$ are:

$${25\choose 6}-\left({16\choose 6}+6 {15\choose 6}-6\right) $$

Correct

Answer 1

We count the number of integers $x$ with $1\,000\,000\leq x\leq 9\,999\,999$ which have a digit sum equal to $20$ with the help of generating functions. It is convenient to use the coefficient of operator $[x^{n}]$ to denote the coefficient of $x^n$ in a series.

We obtain \begin{align*} \color{blue}{[x^{20}]}&\color{blue}{\left(1+x+x^2+\cdots+x^9\right)^7-[x^{20}]\left(1+x+x^2+\cdots+x^9\right)^6}\tag{1}\\ &=[x^{20}]\left(\frac{1-x^{10}}{1-x}\right)^7-[x^{20}]\left(\frac{1-x^{10}}{1-x}\right)^6\tag{2}\\ &=[x^{20}]\left(1-7x^{10}+\binom{7}{2}x^{20}\right)\sum_{j=0}^\infty\binom{-7}{j}(-x)^j\\ &\qquad-[x^{20}]\left(1-6x^{10}+\binom{6}{2}x^{20}\right)\sum_{j=0}^\infty\binom{-6}{j}(-x)^j\tag{3}\\ &=\left([x^{20}]-7[x^{10}]+21[x^0]\right)\sum_{j=0}^\infty\binom{j+6}{6}x^j\\ &\qquad-\left([x^{20}]-6[x^{10}]+15[x^0]\right)\sum_{j=0}^\infty\binom{j+5}{5}x^j\tag{4}\\ &=\left(\binom{26}{6}-7\binom{16}{6}+21\binom{6}{6}\right)-\left(\binom{25}{5}-6\binom{15}{5}+15\binom{5}{5}\right)\tag{5}\\ &=\left(230\,230-56\,056+21\right)-\left(53\,130-18\,018+15\right)\\ &=174\,195-35\,127\\ &\,\,\color{blue}{=139\,068} \end{align*}

Comment:

• In (1) we count the strings with length $7$ consisting of digits from $0$ to $9$ with digit-sum $20$. Since numbers do not start with a leading zero, we subtract all strings of length $6$ with digit-sum $20$.

• In (2) we use the finite geometric series formula.

• In (3) we expand the numerator omitting terms which do not contribute to $[x^{20}]$ and we use the binomial series expansion.

• In (4) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

• In (5) we select the coefficients accordingly.