A222444 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

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

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]

EXAMPLE

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

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).

Sequence in context: A099465 A099094 A222169 * A206492 A007683 A316220

Adjacent sequences: A222441 A222442 A222443 * A222445 A222446 A222447

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Feb 20 2013

STATUS

approved