کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655190 | 1632937 | 2015 | 31 صفحه PDF | دانلود رایگان |
Zeckendorf proved any integer can be decomposed uniquely as a sum of non-adjacent Fibonacci numbers, FnFn. Using continued fractions, Lekkerkerker proved the average number of summands of an m∈[Fn,Fn+1)m∈[Fn,Fn+1) is essentially n/(φ2+1)n/(φ2+1), with φ the golden ratio. This result has been generalized by many, often using Markov processes, to show that for any positive linear recurrence the number of summands in decompositions for integers in [Gn,Gn+1)[Gn,Gn+1) converges to a Gaussian distribution. Below we instead follow and further develop the combinatorial approach of Miller and Wang, and show its power in handling related questions. Specifically, we prove that the probability of a gap larger than the recurrence length converges to decaying geometrically, and that the distribution of the smaller gaps depends in a computable way on the coefficients of the recurrence. These results hold both for the average over all m∈[Gn,Gn+1)m∈[Gn,Gn+1) and almost surely for the gap measure associated to individual m . These techniques also determine the distribution of the longest gap between summands, which we prove is similar to the distribution of the longest gap between heads in tosses of a biased coin. It is a double exponential strongly concentrated about the mean, and is on the order of lognlogn with computable constants depending on the recurrence.
Journal: Journal of Combinatorial Theory, Series A - Volume 135, October 2015, Pages 130–160