2D partitions

hv at crypt.org hv at crypt.org
Tue Sep 6 20:17:14 CEST 2005


Consider the ways in which we may partition an a x b rectangle into
regions, defined for this purpose as orthogonally connected sets of
unit squares.

A region is defined by the squares comprising it (rather than the
connections).

I looked at two functions:
  f(a, b) counts the number of partitions
  g(a, b) counts the same, after discarding mirror/rotate symmetries

For example, f(2, 2) is 12:

+--+--+  +--+--+  +--+--+  +--+--+  +--+--+  +--+--+
|  |  |  |     |  |  |  |  |  |  |  |  |  |  |     |
+--+--+  +--+--+  +  +--+  +--+--+  +--+  +  +--+--+
|  |  |  |  |  |  |  |  |  |     |  |  |  |  |     |
+--+--+  +--+--+  +--+--+  +--+--+  +--+--+  +--+--+

+--+--+  +--+--+  +--+--+  +--+--+  +--+--+  +--+--+
|  |  |  |  |  |  |     |  |     |  |  |  |  |     |
+  +  +  +  +--+  +  +--+  +--+  +  +--+  +  +     +
|  |  |  |     |  |  |  |  |  |  |  |     |  |     |
+--+--+  +--+--+  +--+--+  +--+--+  +--+--+  +--+--+

.. while g(2, 2) is 5:

+--+--+  +--+--+  +--+--+  +--+--+  +--+--+
|  |  |  |     |  |     |  |  |  |  |     |
+--+--+  +--+--+  +--+--+  +  +--+  +     +
|  |  |  |  |  |  |     |  |     |  |     |
+--+--+  +--+--+  +--+--+  +--+--+  +--+--+

On this basis, f(1, n) is trivially 2^(n-1), since each of the n - 1
possible connections may independently be connected or separate.

Calculated values of g(1, n) agree with A005418(n) (checked up to n=18),
which makes sense:
  ID Number: A005418
  Name: Number of n-bead black-white reversible strings; [...]

Calculated values of f(2, n) agree with A078469(n) (checked up to n=9):
  ID Number: A078469
  Name: Number of different compositions of the ladder graph L_n.
.. which if I understand correctly is the same thing.

Calculated values of g(2, n) up to n=9 give:
  2, 5, 29, 143, 780, 4546, 27269, 166070, 1017690
.. which is not in OEIS. Since this is the only test of my program's
ability to discern the full set of symmetries, it is difficult for me
to guarantee the results; I've confirmed up to g(2, 3) by hand, and
I'll try to check g(2, 4) as well.

I'd like to construct fuller tables for f() and g(), but the approach
of my current program for generating connected regions will not extend
to 3 x n rectangles, so it'll need more work.

Thoughts and suggestions welcome,

Hugo





More information about the SeqFan mailing list