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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4