## Polyomino Enumerations

```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)
```