Locally Restricted Compositions II. General Restrictions and Infinite Matrices

• Published in: The Electronic journal of combinatorics 2009-08, Vol.16 (1)
• Main Authors: Bender, Edward A., Canfield, E. Rodney
• Format: Article
• Language: English
• ISSN: 1077-8926; 1077-8926
• DOI: 10.37236/197

We study compositions $\vec{\bf c}=(c_1,\dots,c_k)$ of the integer $n$ in which the value $c_i$ of the $i$th part is constrained based on previous parts within a fixed distance of $c_i$. The constraints may depend on $i$ modulo some fixed integer $m$. Periodic constraints arise naturally when $m$-rowed compositions are written in a single row. We show that the number of compositions of $n$ is asymptotic to $Ar^{-n}$ for some $A$ and $r$ and that many counts can be expected to have a joint normal distribution with means vector and covariance matrix asymptotically proportional to $n$. Our method of proof relies on infinite matrices and does not readily lead to methods for accurate estimation of the various parameters. We obtain information about the longest run. In many cases, we obtain almost sure asymptotic estimates for the maximum part and number of distinct parts.