2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I am confused by your solution. My personal recommendation would be going the route of formal power series. $\endgroup$ Dec 16, 2019 at 14:52
  • $\begingroup$ In case 1, you should use $x_1=10+x_1'$, otherwise $x_1'$ cannot be zero . $\endgroup$
    – Vasili
    Dec 16, 2019 at 15:19

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.