 |
Abstract: A composition of the nonnegative interger
n is a way of writing n as an ordered sum of positive
integers. 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=1 if n=0, and 2^{n-1} if
n\ge1.
Equivalently, letting x be a variable,
we have the generating function (power series) \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
theory of formal languages from computer science. Surprisingly,
identities about hypergeometric series are needed to do some of the
computations.
This talk will be accessible to graduate students.
|