1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of solutions to summation

  1. Mar 12, 2009 #1
    What is the general formula for a1 + a2 + a3 + .... + an = A, where all the variables a_i and A are non-negative integers.
  2. jcsd
  3. Mar 12, 2009 #2
    There isn't an easier way to add numbers than to add them, unless the numbers are special in some way (eg, part of a arithmetic/geometric series)
  4. Mar 13, 2009 #3
    ahhhh... sorry, completely scrwed up the question. I meant,

    What is the general formula for the Number Of Solutions Tn to a1 + a2 + a3 + ... + an = k, where all variables are non-negative integers?

    :P, sorry for the mistake.

    However, I have a solution, but I am convinced that i had read an easier formula somewhere.

    This is my argument

    1. a = k, with only one variable, has only one solution. So T1 = 1

    2. a + b = k, has k + 1 solutions, as a can take any value from 0 to k, and the corresponding b will be fixed. T2 = k + 1

    [tex]T_{2} = \sum_{k ' = 0} ^k 1[/tex]

    3. a + b + c = k

    a + b can take any value from 0 to k, and corresponding c will be fixed. Suppose a + b = k'. Then from the above argument no. 2, no. of solutions are k' + 1. Thus to get total no. of solutions of a+b+c = k, we must sum k' over all possible k's

    [tex] T_{3} = \sum_{k' = 0} ^k (k' + 1)[/tex]

    [tex] = T_{3} = \sum_{k'' = 0} ^k \sum_{k' = 0} ^{k''} 1[/tex]

    4. for a+b+c+d = k, we can divide it into a+b+c = k', then into a+b = k'', and solve it similarly like above.

    Thus in general we'll have n-1 such summations over variables k', k'', k''' etc..., i.e

    [tex]T_{n} = \sum_{k^{n-1} = 0} ^k \sum_{k^{n-2} = 0} ^{k^{n-1}}............ \sum_{k'' = 0} ^{k'''} \sum_{k' = 0} ^{k^{''}} 1[/tex]

    However, I am sure I have read an easier formula somewhere. Could someone list that down?
  5. Mar 13, 2009 #4
    Last edited by a moderator: Apr 24, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook