The number of tilings of a block with blocks (Q1114699)

A rectangle with positive integer sides k and n is called a \(k\times n\) block, or simply a block if k and n are not to be specified. A \(k\times n\) block subdivided into sub-blocks is said to be tiled with blocks. The so-called divide-and-conquer method gives one way of generating tilings of blocks. Here tilings are produced by a finite number of applications of the following basic step: select a sub-block of the tiling and cut it into two similar blocks. Let g(k,n) (resp. d(k,n)) denote the number of tilings (resp. divide-and-conquer tilings) of a \(k\times n\) block with blocks. The paper discusses various properties of these numbers g(k,n) and d(k,n). For fixed k the sequences \((g(k,n))_ n\) and \((d(k,n))_ n\) satisfy linear homogeneous difference equations with constant coefficients. This can be used to obtain asymptotic formulas for g(k,n) and d(k,n). In particular the limits \[ \lim_{k,n\to \infty}(g(k,n))^{1/kn}=\gamma \quad and\quad \lim_{k,n\to \infty}(d(k,n))^{1/kn}=\delta \] are shown to exist; it is conjectured that \(\gamma\neq \delta\).