A207997 T(n,k) = number of n X k 0..2 arrays with new values 0..2 introduced in row major order and no element equal to any horizontal or vertical neighbor (colorings ignoring permutations of colors).

1, 1, 1, 2, 3, 2, 4, 9, 9, 4, 8, 27, 41, 27, 8, 16, 81, 187, 187, 81, 16, 32, 243, 853, 1302, 853, 243, 32, 64, 729, 3891, 9075, 9075, 3891, 729, 64, 128, 2187, 17749, 63267, 96831, 63267, 17749, 2187, 128, 256, 6561, 80963, 441090, 1034073, 1034073, 441090, 80963

Offset

1,4

Comments

Number of colorings of the grid graph P_n X P_k using a maximum of 3 colors up to permutation of the colors. - Andrew Howroyd, Jun 26 2017

Links

R. H. Hardin, Table of n, a(n) for n = 1..544

R. J. Mathar, Counting 2-way monotonic terrace forms over rectangular landscapes, vixra:1511.0225, eq. (33)-(35).

Eric Weisstein's World of Mathematics, Grid Graph

Eric Weisstein's World of Mathematics, Vertex Coloring

Wikipedia, Graph Coloring

Formula

2*T(n,m) = A078099(n,m) for m>1. - R. J. Mathar, Nov 23 2015

Example

Table starts
..1....1.....2.......4.........8.........16...........32............64
..1....3.....9......27........81........243..........729..........2187
..2....9....41.....187.......853.......3891........17749.........80963
..4...27...187....1302......9075......63267.......441090.......3075255
..8...81...853....9075.....96831....1034073.....11045757.....117997043
.16..243..3891...63267...1034073...16932816....277458045....4547477370
.32..729.17749..441090..11045757..277458045...6978332618..175605187731
.64.2187.80963.3075255.117997043.4547477370.175605187731.6787438272198
...
Some solutions for n=4, k=3:
..0..1..2....0..1..0....0..1..0....0..1..2....0..1..2....0..1..2....0..1..0
..2..0..1....2..0..2....1..0..2....1..2..1....2..0..1....1..2..1....1..2..1
..0..2..0....0..1..0....2..1..0....0..1..2....0..2..0....0..1..2....2..0..2
..1..0..1....1..2..1....1..0..1....1..2..0....2..0..2....2..0..1....1..2..0

Crossrefs

Cf. A020698 (column 3), A078100 (column 4), A207994 (column 5), A207995 (column 6), A207996 (column 7).

Main diagonal is A207993.

Cf. A198715 (4 colorings), A198906 (5 colorings), A198982 (6 colorings), A198723 (7 colorings), A198914 (8 colorings), A207868 (unlimited).

Sequence in context: A247936 A231150 A274858 * A304489 A034800 A082771

Adjacent sequences: A207994 A207995 A207996 * A207998 A207999 A208000

Keyword

nonn,tabl

Author

R. H. Hardin, Feb 22 2012

Status

approved