# How many 6 digit numbers have digits that sum to 27? (Build Up Counting)

We have 6 digit numbers 000000 to 999999, and we need to find all of the possible combinations of these 6 digit numbers that sum to 27.

000999, 999000, etc all work. I understand this will involve build up counting, so we'll need to use $n \choose k$ for this problem. I've tinkered around with it and realized the sum of a string with the same value digit follows the following pattern:

999999… 54

888888… 48

777777… 42

666666… 36

555555… 30

444444… 24

So to get the sum to 27, we’d have to subtract 1 from some of the digits in the 555555 string 3 times, giving us some combination of 555444. If we do +/– some values on each digit, we can make the same combinations of 27. I just don't know how I can use $n \choose k$ on this pattern, where I use 555444 and its combinations +/- different values on each digit.

I also found this post here, which shows the use of the stars and bars strategy for solving a similar problem. However, I'm confused about how stars and bars applies in this case, or what the summation of the $n \choose k$ setup would look like

If someone can guide me in the right direction, I would greatly appreciate it. Thank you!

## 1 Answer

Using inclusion-exclusion with stars and bars to separate $27$ units into the required digits will give the answer.

The raw separation of $27$ units into $6$ parts is given by $\binom{27+5}{5}$. However some of these options will involve a part that is greater than $9$, so we can "preload" each digit in turn with $10$ (to break this constraint) and observe that there are $\binom{17+5}{5}$ ways to distribute the remaining units, which we can subtract off the above result. However this will still subtracted off the cases where two digits broke the constraint; now we can pre-load 2 digits in $\binom 62$ combinations with constraint-breaking $10$ units and find that $\binom{7+5}{5}$ combinations have to be added back in (that were double-subtracted).

Giving $\binom{32}{5} - \binom 61 \binom{22}{5} + \binom 62 \binom{12}{5}$ as the total possibilities.

• I think we would have to add the condition that the first digit should be strictly bigger than 0, else we wouldn't really call it a 6 digit number. – Thomas Bladt Oct 29 '17 at 23:05
• @ThomasBladt The question explicitly allows such strings. Probably the simplest way to extend this answer to cover your proposed case would be to do it all again with only 5 digits. – Joffan Oct 29 '17 at 23:15