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)