as an example, consider the following problem. given positive integers $a_1,…,a_d$ that are relatively prime, let s be the set of integers that can be written as a nonnegative integer combination of these $a_i$. we can think of the $a_i$ as denominations of postage stamps and s as the postal rates that can be paid exactly using these denominations. what can we say about the structure of this set, s? what is the largest integer not in s (called the frobenius number)? how many positive integers are not in s? we attack these problems using the generating function $f_s(x)$, defined to be the sum, over all elements s of s, of the monomials $x^s$. we will build up the general theory of computing generating functions – for this and other problems – and then use these generating functions to answer questions we’re interested in. we will approach these problems from an algorithmic perspective: what can we do in polynomial time?