Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities

Abstract

We study compositions $c_1,\dots,c_k$ of the integer $n$ in which adjacent parts may be constrained to satisfy some periodic inequalities, for example $$ c_{2i}>c_{2i+1} < c_{2i+2} \mbox{(alternating compositions).} $$ The types of inequalities considered are $ < $, $\le$, $>$, $\ge$ and $\ne$. We show how to obtain generating functions from which various pieces of asymptotic information can be computed. There are asymptotically $Ar^{-n}$ compositions of $n$. In a random uniformly selected composition of $n$, the largest part and number of distinct parts are almost surely asymptotic to $\log_{1/r}(n)$. The length of the longest run is almost surely asymptotic to $C\log_{1/r}(n)$ where C is an easily determined rational number. Many other counts are asymptotically normally distributed. We present some numerical results for the various types of alternating compositions.