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!
Best 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.