Problem of the Week
Hilton Memorial Lecture
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.