## Abstract

A dyadic interval is an interval of the form [j/2^{k},(j+ 1)/2^{k}], 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 u_{n} count the number of ways of partitioning the unit square into 2^{n} dyadic rectangles, each of area 2^{-n}. One has u_{0} = 1, u_{1} = 2 and u_{n} = 2u_{n-1} ^{2} - u_{n-2}^{4}. 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 u_{0}, u_{1}) with ω > 0 such that for all sufficiently large n one has the exact formula u_{n} = ω^{2n}g(βλ^{n}), where λ = 2√5 - 4 ≈ 0.472, and g(z) = ∑_{j=0} ^{∞} c_{j}z^{j}, in which c_{0} = (-1 + √5)/2, c_{1} = (2 - √5)/2, all coefficients c_{j} lie in the field (√5), and the power series converges for z < 0.16. These results apply to the initial conditions u_{0} = 1, u_{1} = 2 with ω ≈ 1.845 and β ≈ 0.480. The exact formula for u_{n} 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/z^{2}.

Original language | English (US) |
---|---|

Pages (from-to) | 481-499 |

Number of pages | 19 |

Journal | Discrete Mathematics |

Volume | 257 |

Issue number | 2-3 |

DOIs | |

State | Published - Nov 28 2002 |

## Keywords

- Asymptotic enumeration
- Holomorphic dynamics

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics