Number of solutions to summation

[praharmitra]

What is the general formula for a1 + a2 + a3 + ... + an = A, where all the variables a_i and A are non-negative integers.

 

[qntty]

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)

 

[praharmitra]

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

$$T_{2} = \sum_{k ' = 0} ^k 1$$

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

$$T_{3} = \sum_{k' = 0} ^k (k' + 1)$$

$$= T_{3} = \sum_{k'' = 0} ^k \sum_{k' = 0} ^{k''} 1$$


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

$$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$$


However, I am sure I have read an easier formula somewhere. Could someone list that down?

 

[yyat]

I think you can simplify the sum to a polynomial expression using these formulas:http://en.wikipedia.org/wiki/Sum#Identities"
Specifically, the sum
$$\sum_{k=0}^nk^i$$
can be expressed as a polynomial in n.