How do I find the number of combinations of numbers that add to give a value?

Suppose I have an equation something like a+b+c+d = 33, where a,b,c,d are positive integers between 1 and 10 ... how do I determine mathematically the number of solutions within those constraints? I know it must involve something like n!/(n-r!)r! ...

Also, how would I modify it to account for more or less additions (a+b+c+d+e+f, for example) or if the integers were 1-100 etc?

Thanks! Been driving me mental ...

Update:

Incidentally ... I chose 33 at random here. Obviously in the example this could be any number from 4 to 40. And zero is excluded from the values of a,b,c,d ...

Update 2:

Thanks for the answers (it wasn't me who gave the thumbs down, only just checked!). I'm not sure I completely understand the generating functions but I'll look at it some more. One thing about the 'stars and bars' suggestion, if you plot a graph of number of combinations versus the sum, you get what looks like a Gaussian. It's symmetric about some value. If you do a+b+c+d = 11 then that's 10*9*8 / 6 = 120. And since the first sum has to be 4 (1+1+1+1) and the last has to be 40 (10+10+10+10)

Update 3:

Then (40-33)+4 = 11 ... so I think there's something in the stars and bars but you have to partition somehow.

2 Answers

Relevance
  • Anonymous
    4 years ago
    Favourite answer

    You could use generating functions

    (z + z² + z³ + ... + z^10)^4

    = [z (1 - z^10)/(1 - z)]^4

    = z^4 (1 - 4 z^10 + 6 z^20 - 4 z^30 + z^40) (1 + z + z² + ...)^4

    We use (1 + z + z² + ...)^n = 1 + C(n,1) z + C(n+1,2) z² + C(n+2,3) z³ + ...

    = z^4 (1 - 4 z^10 + 6 z^20 - 4 z^30 + z^40) (1 + C(4,1) z + C(5,2) z² + C(6,3) z³ + .... )

    We need the coefficient of z^33

    we have z^4 in front, so we still need z^29 :

    C(32,29) - 4 C(22,19) + 6 C(12,9) = 4960 - 6160 + 1320 = 120

    So there are 120 solutions to the first example equation you gave.

  • nbsale
    Lv 6
    4 years ago

    I missed the part where the number must be <= 10. My answer only covers the part without that constraint.

    This is a standard "stars and bars" problem. It gets that name from the way it's solved.

    How many solutions are there to a+b+c+d = 33, where a b c and d are all >= 1?

    Line up 33 stars. Divide them into sets by putting 3 bars into the 32 spaces between them. You can do that in 32C3 ways, since there are that many ways to choose the 3.

    32C3 = 32x31x30 / 6 = 4960

    EDIT: Yes, I agree with the thumbs down. I misread the question, so this isn't helpful. Sorry.

    I did write a program to check the answer, and 120 is indeed correct.

    Edit 2.

    This isn't a general solution, but for 33, there are only 11 possible combinations for a,b,c, and d. You can list them, then count the number of permutations for each and add them up. I did that, and here's how you get 120:

    10 10 10 3 with 4 permutations

    10 10 9 4 with 12 permutations

    10 10 8 5 with 12 permutations

    10 10 7 6 with 12 permutations

    10 9 9 5 with 12 permutations

    10 9 8 6 with 24 permutations

    10 9 7 7 with 12 permutations

    10 8 8 7 with 12 permutations

    9 9 9 6 with 4 permutations

    9 9 8 7 with 12 permutations

    9 8 8 8 with 4 permutations

    Sum of the permutations is 120.

Still have questions? Get answers by asking now.