Locally Restricted Compositions II. General Restrictions and Infinite Matrices
Open Access
- 7 January 2009
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 16 (1) , R108
Abstract
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.
Keywords
This publication has 8 references indexed in Scilit:
- Pattern avoidance in compositions and multiset permutationsAdvances in Applied Mathematics, 2006
- Locally Restricted Compositions I. Restricted Adjacent DifferencesThe Electronic Journal of Combinatorics, 2005
- Combinatorics of geometrically distributed random variables: run statisticsTheoretical Computer Science, 2003
- On Carlitz CompositionsEuropean Journal of Combinatorics, 1998
- Nonlinear Functional Analysis1985
- Central and local limit theorems applied to asymptotic enumeration II: Multivariate generating functionsJournal of Combinatorial Theory, Series A, 1983
- Central and local limit theorems applied to asymptotic enumerationJournal of Combinatorial Theory, Series A, 1973
- Linear Operators. Part I: General Theory.The American Mathematical Monthly, 1960