A222444 T(n,k) = number of n X k 0..3 arrays with entries increasing mod 4 by 0, 1 or 2 rightwards and downwards, starting with upper left zero.

1, 3, 3, 9, 21, 9, 27, 147, 147, 27, 81, 1029, 2403, 1029, 81, 243, 7203, 39285, 39285, 7203, 243, 729, 50421, 642249, 1500183, 642249, 50421, 729, 2187, 352947, 10499787, 57289767, 57289767, 10499787, 352947, 2187, 6561, 2470629, 171655443

Offset: 1

Author

R. H. Hardin, Feb 20 2013

Keywords

• nonn
• tabl

Comments

1/4 the number of 4-colorings of the grid graph P_n X P_k. - Andrew Howroyd, Jun 26 2017

Examples

			Table starts
......1..........3...............9..................27.......................81
......3.........21.............147................1029.....................7203
......9........147............2403...............39285...................642249
.....27.......1029...........39285.............1500183.................57289767
.....81.......7203..........642249............57289767...............5110723191
....243......50421........10499787..........2187822609.............455924913093
....729.....352947.......171655443.........83550197745...........40672916404629
...2187....2470629......2806303725.......3190677470643.........3628419487925547
...6561...17294403.....45878770089.....121847980727187.......323690312271131451
..19683..121060821....750047661027....4653221950068669.....28876324830999722133
..59049..847425747..12262131106083..177700725073710285...2576049100980154511889
.177147.5931980229.200467073061765.6786168386579878383.229808641254065144560647
...
Some solutions for n=3, k=4:
..0..0..0..2....0..0..2..0....0..2..0..0....0..2..0..2....0..0..2..3
..1..2..2..3....0..2..3..1....2..2..2..0....0..0..0..2....0..2..3..1
..2..2..3..1....2..0..1..3....2..2..0..0....2..0..1..3....1..2..0..1
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..496 (terms 1..180 from R. H. Hardin)
• Eric Weisstein's World of Mathematics, Grid Graph
• Eric Weisstein's World of Mathematics, Vertex Coloring
• Wikipedia, Graph Coloring

Crossrefs

Columns 1-7 are A000244(n-1), A169634(n-1), A222439, A222440, A222441, A222442, A222443.

Main diagonal is A068254.

Cf. A078099 (3 colorings), A198715 (unlabeled 4 colorings), A222144 (5 colorings), A222281 (6 colorings), A222340 (7 colorings), A222462 (8 colorings).

Formula

T(n,k) = 6*A198715(n,k) - 3 for n*k>1. - Andrew Howroyd, Jun 27 2017

Empirical for column k:

k=1: a(n) = 3*a(n-1).

k=2: a(n) = 7*a(n-1).

k=3: a(n) = 18*a(n-1) - 27*a(n-2).

k=4: a(n) = 45*a(n-1) - 267*a(n-2) + 263*a(n-3).

k=5: a(n) = 118*a(n-1) - 2811*a(n-2) + 22255*a(n-3) - 53860*a(n-4) - 54747*a(n-5) + 269406*a(n-6) - 175392*a(n-7).

k=6: [order 13]

k=7: [order 32]