I have a list of numbers: $[a_1, a_2, a_3, a_4, ... a_n]$ and a target value, $t$.
I need to figure out how many ways the numbers in the set can be chosen to have a sum of $t$, where each element is included $0$ or more times.
I came to the equation $x_1a_1 + x_2a_2 + ... x_na_n = t$ where $x_i, a_i \geq 0$
The number of solutions to this equation, is exactly the number I am looking for. I have seen this type of problem, similar to the coin problem, but I'm not sure how exactly it works with these unknown & variable coefficients in front of each term. Any help / guidance would be appreciated - thanks so much in advance :)
Since you included the tag generating-functions, here is how generating functions can be applied. The answer you seek is the coefficient of $x^t$ in $$ (1-x^{a_1})^{-1}(1-x^{a_2})^{-1}\cdots(1-x^{a_n})^{-1} $$ By factoring out $(1-x)^{-1}$ from each factor, this can be written in the form $$ (1-x)^{-n}(1+x+\dots+x^{a_1-1})^{-1}\cdots(1+x+\dots+x^{a_n-1})^{-1} $$ I think the most efficient way to extract the coefficient of $x^t$ is the following:
Compute $P(x)=(1+x+\dots+x^{a_1-1})\cdots(1+x+\dots+x^{a_n-1})$ using repeated direct convolution, possibly using FFT multiplication if the $a_n$ are large enough. The generation function is $(1-x)^{-n}\cdot 1/P(x)$.
Use https://math.stackexchange.com/a/2924299/177399 to compute the first $t+1$ coefficients of $1/P(x)$, and call this answer $1/P(x)=\sum_{i=0}^\infty c_i x^i$.
Since $(1-x)^{-n}=\sum_{j=0}^\infty \binom{n+j-1}{j}x^j$, the final answer is $\sum_{k=0}^t c_k \binom{t-k+j-1}{t-k}$.