DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Drew Sills, Rutgers University, asills {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Rational generating functions and compositions

Speaker: Bruce Sagan, Michigan State University

Date: October 20, 2005 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A composition of the nonnegative integer $n$ is a way of writing $n$ as an ordered sum. So the compositons of 3 are 1+1+1, 1+2, 2+1, and 3 itself. It is well-known and easy to prove that if $c_n$ is the number of compositions of $n$ then $c_n=2^{n-1}$ for $n\ge1$ and $c_0=1$. Equivalently, we have the generating function $\sum_{n\ge0} c_n x^n = \frac{1-x}{1-2x}$ which is a rational function. We show that this is a special case of a more general family of rational functions associated with compositions. Our techniques include the use of formal languages. Surprisingly, identities from the theory of hypergeometric series are needed to do some of the computations.

(Joint work with Anders Bjorner)