Assume I have coins of four different denominations $d_i$, say $1$, $2$, $5$ and $10$. One problem that could be asked is how many different ways there are to get to $20$ by adding up exactly $3$ of these coins, where each one may be taken an unlimited amount. In that case, the solution would be to find the coefficient of $x^{20}$ in $(x^1 + x^2 + x^5 + x^{10})^3$, which in this case becomes $3$.

I could also ask how many ways there are to take $3$ coins and get less than $20$, which is just the sum of the coefficients of all powers of $x$ less than $20$, which in this particular example becomes $51$.

Now, let's say I take each coin through a function and change each value $d_i$ to some $f(d_i)$. My question is the following: is there a general way to count how many of the above $51$ combinations of coins would still sum to less than $20$ when the combinations are done with $f(d_i)$ replacing each $d_i$ in the sum?

Any help is appreciated!

  • $\begingroup$ You should state the problem more clearly (are there unlimited coins?), as someone may think that there is no way to add them up to 20 (the total of 4 coins is just 18) $\endgroup$ – user061703 Mar 8 '18 at 12:23
  • $\begingroup$ Ah, yes, there is an unlimited amount of each coins. Thank you, will update! $\endgroup$ – Carl-Fredrik Nyberg Brodda Mar 8 '18 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.