2D partitions

[hv at crypt.org]

Earlier I wrote:
: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
[...]
: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 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.

I understand a bit better how to extend this: we can find matrices
such that f(a, b) = F_a * P_a ^ (b - 1) * U_a:

F_1 = [ 1 ]

P_1 = [ 2 ] U_1 = [ 1 ]


F_2 = [ 1 1 ]

P_2 = [ 2 3 ] U_2 = [ 1 ]
      [ 3 4 ]       [ 1 ]


F_3 = [ 1 1 1 0 1 1 ]

P_3 = [ 2 3 3 1 3 4 ]  U_3 = [ 1 ]
      [ 3 4 5 0 5 6 ]        [ 1 ]
      [ 1 0 2 0 0 0 ]        [ 0 ]
      [ 2 5 2 2 5 6 ]        [ 1 ]
      [ 3 5 5 0 4 6 ]        [ 1 ]
      [ 4 6 6 0 6 8 ]        [ 1 ]

In the above, assume we are dealing with a rectangle 3 wide x n high.
Then the *_3 matrices encapsulate the 6 possible combinations of regions
represented by the last row, respectively:
  aaa, aab, aba (connected), aba (unconnected), abb, abc

'aba (connected)' means that the two 'a's are connected into a single
region via the previous rows; the unconnected variant is the '0' in F_3 -
these are not valid partitions in isolation, but may become so with
the addition of subsequent rows.

That makes it easy to calculate the numbers:
  f(3, n) = <4, 74, 1434, 27780, 538150, 10424872, 201947094, 3912050356, 
             75782907270, 1468040672696, ...>
.. which is not in OEIS.

The matrices rapidly get larger: for f(4, n) I think there are 22 functions
to consider (plus a couple of impossible ones such as 'abab with both a-a
and b-b connected'), and 104 for f(5, n). So now I just need to work out
how to automate construction of the matrices, which should keep me busy
for a while. (And if that isn't enough, it may be possible to extend the
approach to address the 3D partition problem.)

Hugo