map colouring (2)

[hv at crypt.org]

Consider the number of ways it is possible to colour an (a x b) chessboard.

I consider two types of variation:
1) allow all colourings ('C'), or only "map colourings" (M) such that no two
orthogonally adjacent squares contain the same colour

2) count symmetric equivalents separately ('A') or count any set of 
symmetric equivalents as a single colouring ('S')

Then for each of these four functions:
  f(a, b) = f(b, a)
  f(a, 0) = 1
and additionally:
  CA(a, b) = A000110(ab)   (the Bell numbers)
  CS(1, n) = (A000110(n) + A080107(n))/2
(as mentioned by both Guenter and David Wilson)
  MA(1, n) = CA(1, n - 1) = A000110(n - 1).
  MS(1, n) = CS(1, n - 1) = (A000110(n - 1) + A080107(n - 1))/2

I'd expect other such congruences to be available for the finding, but
I'm not sure how best to present the data below in a form useful to EIS.

Time of calculation is roughly proportional to ((ab)! / 2^(ab)); I have
calculated all values for ab <= 16, but I anticipate the time to calculate
values for ab between 17 and 20 will range from 8.5 hours to 600 days, so
don't expect much more from the current algorithm.

If anyone is interested in the code used (200 lines of C), you can find
it at http://www.crypt.org/hv/puzzle/colourings.c

Hugo
---
CS(a, b):
\a  0          1          2         3          4
b\
  +---------------------------------------------
0 | 1          1          1         1          1
1 | 1          1          2         4         11
2 | 1          2          7        74       1158
3 | 1          4         74      2966    1060401
4 | 1         11       1158   1060401 1310397193
5 | 1         32      29743 345947706
6 | 1        117    1058530
7 | 1        468   47763673
8 | 1       2152 2620356635
9 | 1      10743
10| 1      58487
11| 1     340390
12| 1    2110219
13| 1   13830235
14| 1   95475556
15| 1  691543094
16| 1 5240285139

MA(a, b):
\a  0          1         2        3         4
b\
  +------------------------------------------
0 | 1          1         1        1         1
1 | 1          1         1        2         5
2 | 1          1         4       34       500
3 | 1          2        34     2052    278982
4 | 1          5       500   278982 455546040
5 | 1         15     10900 68162042
6 | 1         52    322768
7 | 1        203  12297768
8 | 1        877 580849872
9 | 1       4140
10| 1      21147
11| 1     115975
12| 1     678570
13| 1    4213597
14| 1   27644437
15| 1  190899322
16| 1 1382958545

MS(a, b):
\a  0         1         2        3        4
b\
  +----------------------------------------
0 | 1         1         1        1        1
1 | 1         1         1        2        4
2 | 1         1         3       15      156
3 | 1         2        15      355    70928
4 | 1         4       156    70928 57019242
5 | 1        11      2880 17073282
6 | 1        32     81698
7 | 1       117   3081008
8 | 1       468 145265004
9 | 1      2152
10| 1     10743
11| 1     58487
12| 1    340390
13| 1   2110219
14| 1  13830235
15| 1  95475556
16| 1 691543094