Number of solutions to summation (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

What is the general formula for a1 + a2 + a3 + .... + an = A, where all the variables a_i and A are non-negative integers.
 
289
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)
 
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)
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?
 
316
0
Last edited by a moderator:

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top