Is there a formula for solving problems such as: If there are n coin denominations x1,x2...xn that total p cents, what is the possible number of combinations of coins that total less than or equal to p.? Where n and p are positive real numbers, of course.


On a side note, wikipedia says: "There is an explicit formula for the Frobenius number when there are only two different coin denominations. If the number of coin denominations is three or more, no explicit formula is known; but, for any fixed number of coin denominations, there is an algorithm computing the Frobenius number in polynomial time (in the logarithms of the coin denominations forming an input)."


Does anyone know what the algorithm that wikipedia mentions is? I know it cannot be written explicitly and mathematically (as per wikipedia), but can anyone write it in another format?



Variations of the Frobenius coin problem
Presumably the algorithm to compute the number of ways to change exactly $p$ cents (call it $n\_p$) is to write down the generating function:


$G(z) = \prod\_{i=1}^\infty \dfrac{1}{1-z^{x\_i}},$ then $n\_p$ is then simply the coefficient of $z^p.$ To get the answer to the question you are asking, just sum the coefficients from $0$ to $p.$ 


