Locally Restricted Compositions IV. Nearly Free Large Parts and Gap-Freeness

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 well-known examples are Carlitz and alternating compositions. We sh...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2012-01, Vol.DMTCS Proceedings vol. AQ,... (Proceedings), p.233-242
Main Authors: Bender, Edward, Canfield, Rodney, Gao, Zhicheng
Format: Article
Language:English
Subjects:
[info.info-cg] computer science [cs]/computational geometry [cs.cg]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[math.math-co] mathematics [math]/combinatorics [math.co]
Combinatorics
Computational Geometry
Computer Science
Data Structures and Algorithms
Discrete Mathematics
distinct parts
gaps
largest part
Mathematics
restricted compositions
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 well-known 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)$.
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.2997