Accession Number : AD0741189

Title :   A Procedure for Improving the Upper Bound for the Number of n-Ominoes.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Klarner,David A. ; Rivest,Ronald L.

Report Date : FEB 1972

Pagination or Media Count : 33

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)

Descriptors :   (*NUMERICAL ANALYSIS, SEQUENCES(MATHEMATICS)), COMBINATORIAL ANALYSIS, SEQUENCES(MATHEMATICS), GROUPS(MATHEMATICS), POWER SERIES, CONVERGENCE

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE