we have integer N = 1*n1+2*n2+3*n3+4*n4+5*n5+6*n6+7*n7+8*n8+9*n9 .
How to calculate total possible number of n1..n9 combinations?
n can be any positive integer including 0.
Also algo to generate all of that combinations?
Just to clarify your notation here, are you saying:
(1)
or
(2)
I believe you are referring to (2) here. Are you seeking a computer program that will input N and count all possible solutions - easy - or are you looking for a mathematical formula that will tell you how many solutions there are - hard?
Yes, I mean (2). I'm writing computer program where I need to esimate total number of possible solutions for given N and then rank all of them not trying the same combination twice. Actually the problem turns in to finding all possible combinations. Then is easy to count them. But how to eficiently find all possible combinations?
This question is equivalent to finding all possible partitions of N, restricting the number of terms to 9.
Start with
Define And you can see that . In other words, all possible partitions of the number N with no more than 9 terms. By construction, .
Example. Let N=8.
8
7 + 1
6 + 2
6 + 1 + 1
5 + 3
5 + 2 + 1
5 + 1 + 1 + 1
4 + 4
4 + 3 + 1
4 + 2 + 2
4 + 2 + 1 + 1
4 + 1 + 1 + 1 + 1
3 + 3 + 2
3 + 3 + 1 + 1
3 + 2 + 2 + 1
3 + 2 + 1 + 1 + 1
3 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 2
2 + 2 + 2 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
So you see, by indexing each partition of 8, you can directly get a solution to your equation from each one by letting for each i.
I am not familiar with resources from which to get free code, but I'm sure someone somewhere on the net can provide you with the code for a getPartitions(int N) method. You simply want to restrict yourself to those with no more than 9 terms.
*This code is relatively easy to implement, but in number theory, as you may know, the partition function P(n)="the number of partitions of n" is a famously complicated one. I don't think that limiting them to 9 terms makes it any simpler either.