1. ## Generating combinations

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?

2. ## Clarification

Just to clarify your notation here, are you saying:

(1) $N = n^1+2n^2+3n^3+4n^4+5n^5+6n^6+7n^7+8n^8+9n^9$

or

(2) $N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9$

I believe you are referring to (2) here. Are you seeking a computer program that will input N and count all possible solutions $(n_1,n_2,...,n_9)$ - easy - or are you looking for a mathematical formula $f(N)$ that will tell you how many solutions there are - hard?

3. Originally Posted by Media_Man
Just to clarify your notation here, are you saying:

(1) $N = n^1+2n^2+3n^3+4n^4+5n^5+6n^6+7n^7+8n^8+9n^9$

or

(2) $N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9$

I believe you are referring to (2) here. Are you seeking a computer program that will input N and count all possible solutions $(n_1,n_2,...,n_9)$ - easy - or are you looking for a mathematical formula $f(N)$ 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?

4. ## The Partition Problem

This question is equivalent to finding all possible partitions of N, restricting the number of terms to 9.

Start with $N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9$

Define $m_i=n_i+n_{i+1}+...+n_8+n_9$ And you can see that $N=m_1+m_2+m_3+m_4+m_5+m_6+m_7+m_8+m_9$. In other words, all possible partitions of the number N with no more than 9 terms. By construction, $n_i=m_{i} - m_{i+1} \geq 0$ .

Example. Let N=8.

$m_1+m_2+m_3+m_4+m_5+m_6+m_7+m_8+m_9$
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 $\rightarrow n_1=4-2=2, n_2=2-1=1, n_3=1-1=0, n_4=1-0=1$ $\rightarrow 1(2)+2(1)+3(0)+4(1)=8$
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 $n_i=m_i - m_{i+1}$ 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.

5. Thanks! Will try to implement this in code an see how it works. But idea looks very right!