##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Kevin Woods

#### Oberlin College

## Solving Lattice Point Problems Using Rational Generating Functions

##### Abstract:

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?

Host: Jeff Remmel

### November 10, 2009

### 3:00 PM

### AP&M 7321

****************************