A popular computer game called "Tetris" involves manipulations of various clusters of four squares. The seven distinct types of clusters are illustrated below Clusters of connected squares like this were named "polyominoes" by Solomon Golomb. In particular, if four squares are joined together the result is called a tetromino. The game of Tetris uses all seven possible tetrominoes. Of course, there are only five distinct tetrominoes if you don't count reflections as being different. A pentomino consists of a cluster five squares, and with a little work you can verify that there are 12 distinct pentominoes, not counting rotations and reflections. Similarly, there are 35 distinct hexominoes, 107 distinct septominoes, and so on. We can work out the number of n-ominoes for fairly small values of n, but there is no known formula for the number of n-ominoes in general. For each n there are actually several numbers relating to the enumeration of n-ominoes The table below gives the values of the following functions for n = 1 to 12. e(n) = number of minimal rectangular envelopes (up to rotation) that enclose n contiguous squares. g(n) = number of n-ominoes, not counting rotations or reflections. h(n) = number of n-ominoes, not counting rotations. t(n) = total number of distinct n-ominoes. s(n) = number of n-ominoes that are invariant (up to rotation) under reflection. a(n) = number of elements of h(n) that contribute 1 element to t(n). b(n) = number of elements of h(n) that contribute 2 elements to t(n). c(n) = number of elements of h(n) that contribute 4 elements to t(n). Here's the table: n e(n) g(n) h(n) t(n) s(n) a(n) b(n) c(n) 1 1 1 1 1 1 1 0 0 2 1 1 1 2 1 0 1 0 3 2 2 2 6 2 0 1 1 4 3 5 7 19 3 1 3 3 5 4 12 18 63 6 1 3 14 6 6 35 60 216 10 0 12 48 7 8 108 196 760 20 0 12 184 8 11 369 704 2725 34 3 41 660 9 14 1285 2500 9910 70 2 42 2456 10 17 4655 9189 36446 121 0 155 9034 11 21 17073 33896 135268 250 0 158 33738 12 26 63600 126759 505861 441 9 574 126176 The values of s(n) seem closely related to the central binomial coefficients, but not exactly the same. Also, there are some obvious relations between these functions, such as h(n) = a(n) + b(n) + c(n) t(n) = a(n) + 2b(n) + 4c(n) s(n) = 2g(n) - h(n) 3a(n) + 2b(n) = 4h(n) - t(n) Notice that the clusters counted by a(n) have 4-way symmetry, which implies that every square (except the central square in in odd envelope) must appear four times. That's why a(n)=0 for every n congruent to 2 or 3 (mod 4). The number of minimal envelopes, e(n), can be expressed as 1 / n(n+1) n \ e(n) = --- | ------ + [(n+2)/2] - [sqrt(n)] - SUM [n/k] | 2 \ 2 k=1 / where [x] denotes the greatest integer LESS than x. (Note that [8]=7.) The summation on the right can be replaced by the sum of tau(k), k=1 to n-1, where tau is the "number-of-divisors" function, so we have the recurrence e(n) = e(n-1) + {n/2} - {tau(n-1)/2} where {x} signifies the least integer greater than or equal to x. This can be generalized to clusters of "cubes" in d dimensions. The number of distinct minimal envelopes containing n "cubes" in d dimensions is given by n-1 e_d(n) = SUM (A_d(k) - M_d(k)) k=0 where A_d(k) is the number of additive partitions of k into d or fewer positive integers, and M_d(k) is the number of multiplicative partitions of k into d or fewer proper factors (i.e., factors greater than 1). This can also be expressed by the recurrence formula e_d(n) = e_d(n-1) + A_d(n-1) - M_d(n-1)

Return to MathPages Main Menu