Bruce Sagan (Michigan State and Rutgers)

Rational Generating Functions and
Compositions of an Integer

Abstract for the Colloquium
2006 March 24

A composition of the nonnegative integer n is a way of writing n as an ordered sum of positive integers. So, the compositions of 3 are 1+1+1, 1+2, 2+1, and 3 itself. It is well known (and easy to prove) that if cn is the number of compositions of n then cn = 2n-1 for n at least 1, and c0 = 1. Equivalently, we have the generating function
    Sumn≥0   cn xn = (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.

This is joint work with Anders Björner.


To the Combinatorics Seminar Web page.