4
$\begingroup$

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 $\{a_1.a_2,a_3,...\}$. Each number can be taken more than once.

For example, if $x=4$ and $a_1=1, a_2=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 $a_1,a_2,a_3,\dots$ can be up to $15$, and each of $a_1,a_2,a_3,\dots$ can also be only up to $15$.

  • 0
    ...and if you just want to count the number of possible compositions: `subsetCompositionsCount[n_Integer, vec_List] := Total[Apply[Multinomial, Map[Length, Split[Flatten[MapThread[ConstantArray, {vec, #}]]]]] & /@ FrobeniusSolve[vec, n]] /; VectorQ[vec, IntegerQ] && Apply[And, Thread[vec <= n]]` does the trick.2011-11-06

2 Answers 2

1

Let $c(x)$ be the number of sequences that sum to $x$. How precisely do you need to know $c(x)$? These things tend to grow exponentially, so we should expect $c(10^{18})$ to have about a billion billion digits, up to some smallish factor. An exact answer will be practically impossible to compute. But you can possibly get at least the exact number of digits and the first few significant digits by this method:

Since the order of the term matters to you, the ${1,2}$ case is easy to solve: $c(x)$ is simply the $x+1$th Fibonacci number. You can see this because the last term in a sum totalling $x$ must be either $1$ or $2$, so therefore $c(x)=c(x-1)+c(x-2)$, which is the recurrence formula for the Fibonacci numbers. This agrees with your brute-force solution for $c(4)$, because $F_5=5$.

This suggests a general plan of writing down the linear recurrence that arises from your set of terms. In general the solutions of such a recurrence are linear combinations of exponential functions, whose bases are the roots of the characteristic polynomial. For large $x$ such as $10^{18}$, the term with the largest base will dominate all others completely, so we can just ignore all of the others. The trick is then just to find its coefficient.

One way to do this would be to set $c(x)=0$ for $-15\le x<0$ and $c(0)=0$, and then solve 16 linear equations in 16 unknowns.

Another way is simply to run the recurrence up to $c(N)$ for some $N$ between, say, 100 and 1000, and assume that by that time all of the smaller bases have faded into insignificance. Then we can estimate the coefficient as $\frac{c(N)}{r^N}$, and our approximation for large $x$ is $\log c(x) \approx \log c(N) +(x-N)\log r$ It is necessary to work with logarithms in this step, because even $c(1000)$ is likely to overflow the hardware floating-point representation in your computer. In fact, one could choose $N$ adaptively such that $c(N)$ is around $2^{500}$.

You can use $\frac{c(N)}{c(N-1)}$ as a first approximation of $r$ and refine it using Newton-Raphson iteration on the characteristic polynomial.

Special cases: If the numerically largest root of the characteristic polynomial is complex, the recurrence can have oscillating solutions that are never dwarfed by the exponential term. I think the only way this can happen is if the $a_i$s share a divisor $\ne 1$. So start by dividing out the greatest common divisor from the $a_i$s as well as from $x$.

If the largest root of the characteristic polynomial is a multiple root, the growth rates from the master theorem look slightly different. I think this cannot happen when the recurrence is constructed from your problem, but it is probably worth checking for explicitly when you have found $r$.

  • 0
    Yup, very sorry for that. I didn't even realize that it would change the entire course of the solution. I was just dazzled on how such problems could be solved in less than linear time. I didn't even know that things like exponentiation and transition matrix of a linear recurrence exist. My bad.2011-11-16
4

Edited in the light of Byron's correction to the original:

The answer is the coefficient of $u^x$ in the expansion of $\sum_{y=0}^x(u^{a_1}+u^{a_2}+\cdots+u^{a_r})^y$ which can be helpful if there is something special about $a_1,a_2,\dots,a_r$ enabling you to simplify this expression; otherwise, it's just a rewording of your problem. But this means your problem is no easier than that of finding a particular coefficient in this expansion, which suggests that most of the time there is no method significantly better than brute force; it's just a question of how cleverly you can arrange for the force to be applied.

As for making it "solvable in a few seconds," you may be asking for too much. Let's look in some detail at a very small example of what you want to do: how many ways to get 100 with 2s, 3s, and 5s?

Well, there's one way using just 5s. You could use 17 5s and 5 3s; there are 22-choose-5 ways to do that. Or you could use 14 5s and 10 3s; 24-choose-10 ways. Carrying on, we see that if you use just 3s and 5s, there are $1+{22\choose5}+{24\choose10}+\cdots+{32\choose30}$ ways. Now there's a similar formula for using just 2s and 5s, and another one for just 2s and 3s. Now what if we use 2s, 3s, and 5s? We could use 19 5s, a 3, and a 2; that gets you a multinomial coefficient, 21-choose-19,1,1. Then there's a 22-choose-18,2,2, and there's a 23-choose-17,3,3 and a 24-choose-17,1,6 and so on and so forth. A simple formula? Maybe, but I don't see it. Although I'd be interested to see what Henning's method does with this example.

  • 0
    @Gerry You have to remove the "1+" under the power of $y$. Alternatively, summing over all 0\leq y<\infty, the generating function is $1/(1-u^{a_1}-\cdots -u^{a_r})$.2011-11-07