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 c_n is the number of compositions of n then c_n = 2n-1 for n at least 1, and c₀ = 1. Equivalently, we have the generating function
    Sum_n≥0   c_n xⁿ = (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.