A dyadic interval is an interval of the form [j/2k,(j+ 1)/2k], where j and k are integers, and a dyadic rectangle is a rectangle with sides parallel to the axes whose projections on the axes are dyadic intervals. Let un count the number of ways of partitioning the unit square into 2n dyadic rectangles, each of area 2-n. One has u0 = 1, u1 = 2 and un = 2un-1 2 - un-24. This paper determines an asymptotic formula for a solution to this nonlinear recurrence for generic real initial conditions. For almost all real initial conditions there are real constants ω and β (depending on u0, u1) with ω > 0 such that for all sufficiently large n one has the exact formula un = ω2ng(βλn), where λ = 2√5 - 4 ≈ 0.472, and g(z) = ∑j=0 ∞ cjzj, in which c0 = (-1 + √5)/2, c1 = (2 - √5)/2, all coefficients cj lie in the field (√5), and the power series converges for z < 0.16. These results apply to the initial conditions u0 = 1, u1 = 2 with ω ≈ 1.845 and β ≈ 0.480. The exact formula for un then holds for all n ≥ 2. The proofs are based on an analysis of the holomorphic dynamics of iterating the rational function R(z) = 2 - 1/z2.
- Asymptotic enumeration
- Holomorphic dynamics
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics