Jason Gao (Carleton)
Locally restricted compositions

A composition of a positive integer $n$ is a sequence of positive integers whose sum is $n$. Let $c_n$ be the total number of compositions of $n$. It is well known that $c_n=2^{n-1}$ and hence the corresponding generating function is a simple rational function. Carlitz first studied compositions whose adjacent parts are distinct. It turns out that there is no simple closed formula for the number of such compositions, and the corresponding generating function is not algebraic. Bender and Canfield studied compositions whose adjacent parts satisfy more general restricted conditions and they showed, under some mild conditions, that the number of such compositions is asymptotic to $Cr^n$ for some positive constants $C$ and $r$. However, their approach (using infinite transfer matrices) does not seem to give efficient ways of computing the values of $C$ and $r$. In this talk, we will derive functional equations for the generating functions of two special types of locally restricted compositions, and discuss the kernal method for solving these functional equations. We will also compare this approach with the inclusion-exclusion approach.