$Find the generating function$

Question

$Find the generating function$

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

25

Report

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

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

1.7K

Iamjustjerry

0

What is the meaning of ∏ here?
Alessandro Iraci

0

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

$Find the generating function$

Answer

Related Questions

Search