Locally restricted compositions. II: General restrictions and infinite matrices

Edward A. Bender ; E. Rodney Canfield

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

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.

Détail

DOI : 10.37236/197

Classification : 05A15, 05A16
Mots-clés : compositions, restrictions, periodic constraints