$Find the generating function$

Question

We have coins of these types: 1, 5, 10, 25, 50 cents and $1.

Find the generating function $\sum_{i=0}^{\infty } a_{i} x^{i} $ where $a_{i}$ is the number of ways you can pay $i$ cents with the coins.

Discrete Mathematics

Iamjustjerry

Report

Answer 1

Answers can be viewed only if

The questioner was satisfied and accepted the answer, or
The answer was disputed, but the judge evaluated it as 100% correct.

View the answer

Let $V = \{1, 5, 10, 25, 50, 100\}$. The generating function is \[ \prod_{n \in V} (1+x^n +x^{2n} + \dots) = \prod_{n \in V} \frac{1}{1-x^n}. \] In fact, the coefficient $a_i$ of $x^i$ in the product is the number of ways one can write $i = \sum_{n \in V} b_n \cdot n$ for some choice of non-negative integers $b_n$, which is the same as the number of ways one can pay $i$ cents with the given coins.

Alessandro Iraci

Iamjustjerry

What is the meaning of ∏ here?
Alessandro Iraci

It's the product. Just like Σ, but it's a product instead.

$Find the generating function$

Answer

Related Questions

Search