Expert: Scott A Wilson - 9/9/2008

Question
QUESTION: I'm developing some Killer Sudoku software and have come up with a requirement to find out how many combinations of the numbers 1 to 9 exist that sum to a given total, with no repetition of numbers allowed in any one combination, and with a specified number of digits in a combination.
i.e. find how many sets of N different digits (where N must be 1 to 9) add up to a total of T.

So if e.g. N=3 and T=8 then there are 2 combinations:
1,2,5
1,3,4

and if N=2 and T=13 then there are 3 combinations:
4,9
5,8
6,7

I have worked out that the total number of N digit combinations (regardless of total sum) is 9 choose N, and that the distribution of totals over this range appears to produce a bell curve, similar to a normal distribution.

I really need a formula to return the number of combinations as a function of N and T - ideally it could be extended to apply not just to a set of digits 1 to 9, but any sized set of digits 1 to S, where S is a square.
i.e. a function of N, T and S.

ANSWER: Also, note that the reason at 4 there are three choices is because we also have to worry about which ones a 2: 1,1,2, 1,2,1, or 2,1,1.
At 5, we could have a 1,1,3 in 3 orders and a 1,2,2 in 3 orders, for a total of 6 choices.

If the number of occurences needs to be cut down in these cases, note that if you have a,a,b, there are 3 choices and a,b,c there are  6 choices.

---------- FOLLOW-UP ----------

QUESTION: It looks like there might be some missing text from the start of your answer...

I also mentioned that there is no repetition of numbers allowed in any one combination, so 1,1,2 would be invalid, for example.
I take your point that e.g. 1,2,5 is equivalent to 1,5,2; 2,1,5; 2,5,1; 5,1,2 and 5,2,1 - it doesn't really matter to me if (N=3, T=8) returns 2 or 6 as I can work with either result.

So - is there a way of arriving at a formula for the number of combinations ?


Answer
The first response was apparently wrong since I allowed duplicates to occur.  I had tried to insert a spreadsheet before the answer you saw.

The best way I found to do this was to still use a spreadsheet to find the sums.  I implemented a technique for counting and put it in the first three columns.  I then sorted for duplicates and eliminated them.  At that point I found the sums and has the spreadsheet do the counting.  I divided the totals by 6, giving
1,1,2,3,4,5,7,7,8,8,8,7,7,5,4,3,2,1,1  Note that when the sum gets close to either end of a number that can come up, the number gets a little different since no duplicates are allowed.  Note that 1 and 7 occur twice, 6 doesn't occur, and 8 occurs three times in the middle.

The numbers I gave mean that there was 1 way to get a sum of 6, 1 way to get a some of 7, 2 ways to get a some of 8, 3 ways to get a some of 9, 4 ways to get a sum of 10, etc.   Note that the 8's are for 14, 15, and 16.

If you need more details on the spreadsheet, ask for them.  It did take several minutes to do it.  Of course, it probably took me longer to write this letter, but computing the spreadsheet took a lot more in depth thought.