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;
}