A Procedure for Improving the Upper Bound for the Number of n-Ominoes.
Abstract
An n-omino is a plane figure composed of n unit squares joined together along their edges. Every n-omino is generated by joining the edge of a unit square to the edge of a unit square in some (n-1)-omino so that the new square does not overlap any squares. Let t(n) denote the number of n-ominoes, then it is known that the sequence ((t(n)) (sup 1/n); n = 1,2,...) increases to a limit theta, and 3.72 < theta < 6.75. A procedure exists for computing an increasing sequence of numbers bounded above by theta. (Chandra recently showed that the limit of this sequence is theta.) In the present work the authors give a procedure for computing a sequence of numbers bounded below by theta. Whether or not the limit of this sequence is theta remains an open question. By computing the first ten terms of our sequence, the authors have shown that theta < 4.65. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1972
- Accession Number
- AD0741189
Entities
People
- David A. Klarner
- Ronald L. Rivest
Organizations
- Stanford University