Locally restricted compositions. III: Adjacent-part periodic inequalities

Edward A. Bender ; E. Rodney Canfield

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

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.

Détail

DOI : 10.37236/417

Classification : 05A15, 05A16
Mots-clés : compositions of integers, alternating compositions, generating function, longest run