3
$\begingroup$

Number of natural numbers less than million with sum of the digits equal to $12$

My Try: obviously we need 6 places to filled with digits $0$ to $9$ such that sum of the digits is $12$

so the required number is number of non negative integral solutions of

$$x_1+x_2+x_3+x_4+x_5+x_6=12$$ which is nothing but $\binom{17}{5}$

Is this correct approach?

$\endgroup$
  • $\begingroup$ Why do we need $6$ places for the digits? Does $39$ not qualify? $\endgroup$ – user394255 Aug 21 '17 at 16:04
  • 4
    $\begingroup$ yes $x_1=x_2=x_3=x_4=0$ and $x_5=3$ and $x_6=9$ $\endgroup$ – Ekaveera Kumar Sharma Aug 21 '17 at 16:07
  • 1
    $\begingroup$ How do you get 17 choose 5 number of solutions? $\endgroup$ – 伽罗瓦 Aug 21 '17 at 16:10
  • $\begingroup$ @ntntnt Stars and bars, I believe ... $\endgroup$ – John Aug 21 '17 at 16:24
  • 1
    $\begingroup$ It is not enough, 10 and 11 are not digits. Furthermore, the first digit of a natural number can't be 0. $\endgroup$ – peterh says reinstate Monica Aug 21 '17 at 18:34
1
$\begingroup$

We seek the number of solutions of the equation in the nonnegative integers $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 12 \tag{1}$$ subject to the restrictions that $x_k \leq 9$ for $1 \leq k \leq 6$.

As you determined, if there were no restrictions, equation 1 has $$\binom{12 + 6 - 1}{6 - 1} = \binom{17}{5}$$ solutions in the nonnegative integers.

Suppose $x_1 > 9$. Then $x_1' = x_1 - 10$ is a nonnegative integer. Substituting $x_1' + 10$ for $x_1$ in equation 1 yields \begin{align*} x_1' + 10 + x_2 + x_3 + x_4 + x_5 + x_6 & = 12\\ x_1' + x_2 + x_3 + x_4 + x_5 + x_6 & = 2 \tag{2} \end{align*} Equation 2 is an equation with

$$\binom{2 + 6 - 1}{6 - 1} = \binom{7}{5}$$

solutions in the nonnegative integers. By symmetry, there are an equal number of solutions for each of the six variables that could exceed $9$. Hence, the number of solutions of equation 1 that do not satisfy the restrictions is

$$\binom{6}{1}\binom{7}{5}$$

so the number of natural numbers less than a million that have digit sum $12$ is

$$\binom{17}{5} - \binom{6}{1}\binom{7}{5}$$

$\endgroup$
  • $\begingroup$ @Joffan I am not sure why I got distracted by the issue of whether $0$ is a natural number since, as you point out, it is irrelevant to the question at hand. $\endgroup$ – N. F. Taussig Aug 21 '17 at 21:42
3
$\begingroup$

No, your approach is wrong.

You haven't applied the condition that $$x_i\le 9 ~\forall 1 \le i\le 6$$

A simple counter-example, which satisfies your equation but doesn't make any sense for the original question is $$x_1=x_2=x_3=x_4=x_5=0 ~~;~ x_6=12$$

For solving correctly, you need to approach this problem from the basics (You can easily do that if you know the derivation of the formula you just applied, using the multinomial theorem)

Can you proceed now?

$\endgroup$
3
$\begingroup$

Almost, we need to subtract the solutions in which one of the $x_i$ is $10,11$ or $12$.

There are $6\times 5+6\times \binom{5}{2}$ solutions in which one of the $x_i$ is $10$.

There are $6\times 5$ solutions in which one of the $x_i$ is $11$.

There are $6$ solutions in which one of the $x_i$ is $12$.

$\endgroup$
  • 1
    $\begingroup$ Did you mean $6 \cdot 5 + 6 \cdot \binom{5}{2}$? $\endgroup$ – N. F. Taussig Aug 21 '17 at 16:18
  • $\begingroup$ woops ty . ${}{}{}{}{}$ $\endgroup$ – Jorge Fernández Hidalgo Aug 21 '17 at 16:22
2
$\begingroup$

We can apply stars-and-bars twice in an inclusion-exclusion framework to get the answer, noting the constraint that any value-place can only have a maximum value of $9$.

Firstly to get the unconstrained partition of $12$ units among the 6 value-places, which you have already: $$\binom{12+5}{5} = 6188$$

Then we can "preload" each of the $6$ value-places in turn with the constraint-breaking $10$ units and run stars-and-bars again on the spare two units, to find out how many forbidden results are included above: $$6\cdot \binom {2+5}{5} = 126$$

giving $6188-126= \fbox{6062}$ as the total count of such numbers

Note that if we wanted to find how many numbers in the range have a digit sum of say $23$ we would need to account for cases where two of the value-places break constraint - these would need to be added back in, due to being subtracted out twice by the one-constraint count.

$\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.