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$.
Best Answer
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.