Edward Bender ; Rodney Canfield ; Zhicheng Gao

Locally Restricted Compositions IV. Nearly Free Large Parts and GapFreeness
dmtcs:2997 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2012,
DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

https://doi.org/10.46298/dmtcs.2997
Locally Restricted Compositions IV. Nearly Free Large Parts and GapFreeness
Authors: Edward Bender ^{1}; Rodney Canfield ^{2}; Zhicheng Gao ^{3}
NULL##NULL##NULL
Edward Bender;Rodney Canfield;Zhicheng Gao
1 Department of Mathematics [San Francisco]
2 Department of Computer Science [Athens GA]
3 School of Mathematics and Statistics [Ottawa]
We define the notion of $t$free for locally restricted compositions, which means roughly that if such a composition contains a part $c_i$ and nearby parts are at least $t$ smaller, then $c_i$ can be replaced by any larger part. Two wellknown examples are Carlitz and alternating compositions. We show that large parts have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. Based on this we obtain asymptotic formulas for the probability of being gap free and for the expected values of the largest part and number distinct parts, all accurate to $o(1)$.
Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)