What is the fastest way to find different numbers of equations in integers?

Question

the equation looks like this:

x1 + x2 + x3 + x4 + ... + xk = n

and ( 0 <= n <= 1000, 0 <k <= 1000 )

Example:

n=3 and k=2 3+0=3 2+1=3 0+3=3 1+2=3 output: 4 // count of equations 

I can't think of anything, even the worst of 100 ways to do it.

Answer 1

 n = 0 -> 1 k = 1 -> 1 k = 2 -> n + 1 k > 2 -> func(n, k - 1) + func(n - 1, k - 1) + .... + func(0, k - 1) // 0 + ... 1 + ... n + 0 + ... + 0 

this way recursively ...

 int func(int n, int k) { assert (n >= 0); assert (k > 0); if (n == 0 || k == 1) { return 1; } else if (k == 2) { return n + 1; } else { int sum = 0; for (int i = 0; i <= n; i++) { sum += func(i, k - 1); } return sum; } } 

to eliminate excess calculation

 int result[NMAX + 1][KMAX + 1] = {0}; int func(int n, int k) { assert (n >= 0); assert (k > 0); if (n == 0 || k == 1) { return 1; } else if (k == 2) { return n + 1; } else if (result[n][k] != 0) { return result[n][k]; } else { int sum = 0; for (int i = 0; i <= n; i++) { sum += func(i, k - 1); } result[n][k] = sum; return sum; } } 

Answer 2

It sounds like a second theorem on stars and bars .

For any pair of natural numbers k and n, the number of different k-sets of non-negative integers whose sum is n is given by a binomial coefficient ( ^{k + n - 1} _{psub>) ...}

(I changed n and k from the description on Wikipedia according to your question.)

So, in the example that you gave with n = 3 and k = 2, the answer is ( ^{2 + 3 - 1} ₃ ) = ( ⁴ ₃ ) = 4! / ((4 - 3)! & Times; 3!) = 4 .

Therefore, if you pre-cache factorials, you can quickly perform calculations for any of your k and n values.

Answer 3

This is more like a math problem.
Suppose you have k-1 | s and n Os. | S divided these Os into k sections. For example, if k = 3 and n = 8, then it can be split in this way

 OOO | O | OOOO 

The first section x1 has 3 Os, the second section x2 has 1 O, and x3 has 4 Os, i.e. 3 + 1 + 4 = 8. Thus, the equation counter represents the number of combinations | s and Os, or C (k + n - 1, n).