2
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Bladt Oct 29 '17 at 23:05
  • 2
    $\begingroup$ @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. $\endgroup$ – Joffan Oct 29 '17 at 23:15

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.