How many natural numbers below 1 million have their sum of digits equal to 18?

One way to solve this would be to make all possible cases in which the digits of the no. add up to 18 and then permute them as well as repeat this process for 1-digit, 2-digit... up till 6-digit.....but obviously thats a very cumbersome way to solve this problem. Anyone can help me out with a shorter solution?

Thanks in advance!!

  • $\begingroup$ An upper bound would be the number of multiples of nine. $\endgroup$ – JustKevin Nov 3 '16 at 18:11
  • $\begingroup$ These are just the ordered $6-$tuples of non-negative integers which sum to $18$. Stars and Bars gives us a way to count these. $\endgroup$ – lulu Nov 3 '16 at 18:20
  • $\begingroup$ @lulu nope, $11 + 2 +5$ doesn't correspond to any such number, because $11$ is not a digit. $\endgroup$ – Gabriel Burns Nov 3 '16 at 18:22
  • $\begingroup$ Aah!! Thanks Gabriel!! I tried using the multinomial approach for solving but it lead me to the wrong answer.....I knew I was missing something.....but couldnt get it and hence posted the question here. Sometimes simple things jump out of our mind.....Thanks a lot again!! $\endgroup$ – SirXYZ Nov 3 '16 at 18:24
  • $\begingroup$ @GabrielBurns you are correct, of course. Thanks for the correction (+1). $\endgroup$ – lulu Nov 3 '16 at 18:30

You can use a stars and bars approach to count the total number of (ordered) ways to add six numbers (possibly including zero) totaling $18$, then subtract $6$ times the number of ways to add six numbers totaling $8$ (thus removing the cases where one of the numbers is $\ge 10$).


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.