map colouring (2)
hv at crypt.org
hv at crypt.org
Thu Mar 17 04:49:37 CET 2005
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
More information about the SeqFan
mailing list