How many ways to represent a number from a given set of numbers

Question

I want to know in how many ways can we represent a number x as a sum of numbers from a given set of numbers {a1.a2,a3,...}. Each number can be taken more than once.

For example, if x=4 and a1=1,a2=2, then the ways of representing x=4 are:

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2

Thus the number of ways =5.

I want to know if there exists a formula or some other fast method to do so. I can't brute force through it. I want to write code for it.

Note: x can be as large as 10^18. The number of terms a1,a2,a3,… can be up to 15, and each of a1,a2,a3,… can also be only up to 15.

Answer 1

Calculating the number of combinations can be done in O(log x), disregarding the time it takes to perform matrix multiplication on arbitrarily sized integers.

The number of combinations can be formulated as a recurrence. Let S(n) be the number of ways to make the number n by adding numbers from a set. The recurrence is

S(n) = a_1*S(n-1) + a_2*S(n-2) + ... + a_15*S(n-15),

where a_i is the number of times i occurs in the set. Also, S(n)=0 for n<0. This kind of recurrence can be formulated in terms of a matrix A of size 15*15 (or less is the largest number in the set is smaller). Then, if you have a column vector V containing

S(n-14) S(n-13) ... S(n-1) S(n),

then the result of the matrix multiplication A*V will be

S(n-13) S(n-12) ... S(n) S(n+1).

The A matrix is defined as follows:

0    1    0    0    0    0    0    0    0    0    0    0    0    0    0
0    0    1    0    0    0    0    0    0    0    0    0    0    0    0
0    0    0    1    0    0    0    0    0    0    0    0    0    0    0
0    0    0    0    1    0    0    0    0    0    0    0    0    0    0
0    0    0    0    0    1    0    0    0    0    0    0    0    0    0
0    0    0    0    0    0    1    0    0    0    0    0    0    0    0
0    0    0    0    0    0    0    1    0    0    0    0    0    0    0
0    0    0    0    0    0    0    0    1    0    0    0    0    0    0
0    0    0    0    0    0    0    0    0    1    0    0    0    0    0
0    0    0    0    0    0    0    0    0    0    1    0    0    0    0
0    0    0    0    0    0    0    0    0    0    0    1    0    0    0
0    0    0    0    0    0    0    0    0    0    0    0    1    0    0
0    0    0    0    0    0    0    0    0    0    0    0    0    1    0
0    0    0    0    0    0    0    0    0    0    0    0    0    0    1
a_15 a_14 a_13 a_12 a_11 a_10 a_9  a_8  a_7  a_6  a_5  a_4  a_3  a_2  a_1 

where a_i is as defined above. The proof that the multiplication of this matrix with a vector of S(n_14) ... S(n) works can be immediately seen by performing the multiplication manually; the last element in the vector will be equal to the right hand side of the recurrence with n+1. Informally, the ones in the matrix shifts the elements in the column vector one row up, and the last row of the matrix calculates the newest term.

In order to calculate an arbitrary term S(n) of the recurrence is to calculate A^n * V, where V is equal to

S(-14) S(-13) ... S(-1) S(0) = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.

In order to get the runtime down to O(log x), one can use exponentiation by squaring to calculate A^n.

In fact, it is sufficient to ignore the column vector altogether, the lower right element of A^n contains the desired value S(n).

In case the above explanation was hard to follow, I have provided a C program that calculates the number of combinations in the way I described above. Beware that it will overflow a 64-bits integer very quickly. You'll be able to get much further with a high-precision floating point type using GMP, though you won't get an exact answer.

Unfortunately, I can't see a fast way to get an exact answer for numbers such at x=10^18, since the answer can be much larger than 10^x.

#include <stdio.h>
typedef unsigned long long ull;

/*  highest number in set */
#define N 15

/*  perform the matrix multiplication out=a*b */
void matrixmul(ull out[N][N],ull a[N][N],ull b[N][N]) {
  ull temp[N][N];
  int i,j,k;
  for(i=0;i<N;i++) for(j=0;j<N;j++) temp[i][j]=0;
  for(k=0;k<N;k++) for(i=0;i<N;i++) for(j=0;j<N;j++)
    temp[i][j]+=a[i][k]*b[k][j];
  for(i=0;i<N;i++) for(j=0;j<N;j++) out[i][j]=temp[i][j];
}

/*  take the in matrix to the pow-th power, return to out */
void matrixpow(ull out[N][N],ull in[N][N],ull pow) {
  ull sq[N][N],temp[N][N];
  int i,j;
  for(i=0;i<N;i++) for(j=0;j<N;j++) temp[i][j]=i==j;
  for(i=0;i<N;i++) for(j=0;j<N;j++) sq[i][j]=in[i][j];
  while(pow>0) {
    if(pow&1) matrixmul(temp,temp,sq);
    matrixmul(sq,sq,sq);
    pow>>=1;
  }
  for(i=0;i<N;i++) for(j=0;j<N;j++) out[i][j]=temp[i][j];
}

void solve(ull n,int *a) {
  ull m[N][N];
  int i,j;
  for(i=0;i<N;i++) for(j=0;j<N;j++) m[i][j]=0;
  /*  create matrix from a[] array above */
  for(i=2;i<=N;i++) m[i-2][i-1]=1;
  for(i=1;i<=N;i++) m[N-1][N-i]=a[i-1];
  matrixpow(m,m,n);
  printf("S(%llu): %llu\n",n,m[N-1][N-1]);
}

int main() {
  int a[]={1,1,0,0,0,0,0,1,0,0,0,0,0,0,0};
  int b[]={1,1,1,1,1,0,0,0,0,0,0,0,0,0,0};
  solve(13,a);
  solve(80,a);
  solve(15,b);
  solve(66,b);
  return 0;
}

Answer 2

Since order in sum is important it holds:

S( n, {a_1, ..., a_k} ) = sum[ S( n - a_i, {a_1, ..., a_k} ) for i in 1, ..., k ].

That is enough for dynamic programming solution. If values S(i, set) are created from 0 to n, than complexity is O( n*k ).

Edit: Just an idea. Look at one summation as a sequence (s_1, s_2, ..., s_m). Sum of first part of sequence will be larger than n/2 at one point, let it be for index j:

s_1 + s_2 + ... + s_{j-1} < n / 2,
s_1 + s_2 + ... + s_j = S >= n / 2.

There are at most k different sums S, and for each S there are at most k possible last elements s_j. All of possibilities (S,s_j) split sequence sum in 3 parts.

s_1 + s_2 + ... + s_{j-1} = L,
s_j,
s_{j+1} + ... + s_m = R.

It hold n/2 >= L, R > n/2 - max{a_i}. With that, upper formula have more complicated form:

S( n, set ) = sum[ S( n-L-s_j, set )*S( R, set ) for all combinations of (S,s_j) ].

I'm not sure, but I think that with each step it will be needed to 'create' range of S(x,set) values where range will grow linearly by factor max{a_i}.

Edit 2: @Andrew samples. It is easy to implement first method and it works for 'small' x. Here is python code:

def S( x, ai_s ):
  s = [0] * (x+1)
  s[0] = 1
  for i in xrange(1,x+1):
    s[i] = sum( s[i-ai] if i-ai >= 0 else 0 for ai in ai_s )
  return s[x]

S( 13, [1,2,8] )
S( 15, [1,2,3,4,5] )

This implementation has problem with memory for large x (>10^5 in python). Since only last max(a_i) values are needed it is possible to implement it with circular buffer.

These values grow very fast, e.g. S(100000, [1,2,8] ) is ~ 10^21503.

Answer 3

If you want to find all possible ways of representing a number N from a given set of numbers then you should follow a dynamic programming solution as already proposed.

But if you just want to know the number of ways, then you are dealing with the restricted partition function problem.

The restricted partition function p(n, dm) ≡ p(n, {d1, d2, . . . , dm}) is a number of partitions of n into positive integers {d1, d2, . . . , dm}, each not greater than n.

You should also check the wikipedia article on partition function without restrictions where no restrictions apply.

PS. If negative numbers are also allowed then there probably are (countably )infinite ways to represent your sum.

1+1+1+1-1+1
1+1+1+1-1+1-1+1
etc...

PS2. This is more a math question than a programming one