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 GapFreenessArticle
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)
Funder: Natural Sciences and Engineering Research Council of Canada
References
3 Documents citing this article
Zhicheng Gao;Andrew MacFie, 2021, Locally restricted compositions over a finite group, European Journal of Combinatorics, 97, pp. 103386, 10.1016/j.ejc.2021.103386.
Clemens Heuberger;Daniel Krenn;Stephan G. Wagner, 2015, Canonical Trees, Compact PrefixFree Codes, and Sums of Unit Fractions: A Probabilistic Analysis, SIAM Journal on Discrete Mathematics, 29, 3, pp. 16001653, 10.1137/15m1017107, https://doi.org/10.1137/15m1017107.
Edward A. Bender;Zhicheng Gao, 2014, Part Sizes of Smooth Supercritical Compositional Structures, Combinatorics, Probability & Computing, 23, 5, pp. 686716, 10.1017/s0963548314000315.