A068254 -id:A068254 - cp's OEIS frontend

A182406 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the square grid graph G_(k,k).

1, 0, 2, 0, 2, 3, 0, 2, 18, 4, 0, 2, 246, 84, 5, 0, 2, 7812, 9612, 260, 6, 0, 2, 580986, 6000732, 142820, 630, 7, 0, 2, 101596896, 20442892764, 828850160, 1166910, 1302, 8, 0, 2, 41869995708, 380053267505964, 50820390410180, 38128724910, 6464682, 2408, 9

Offset: 1

Alois P. Heinz, Apr 27 2012

The square grid graph G_(n,n) has n^2 = A000290(n) vertices and 2*n*(n-1) = A046092(n-1) edges. The chromatic polynomial of G_(n,n) has n^2+1 = A002522(n) coefficients.

			Square array A(n,k) begins:
  1,   0,       0,           0,                 0, ...
  2,   2,       2,           2,                 2, ...
  3,  18,     246,        7812,            580986, ...
  4,  84,    9612,     6000732,       20442892764, ...
  5, 260,  142820,   828850160,    50820390410180, ...
  6, 630, 1166910, 38128724910, 21977869327169310, ...

Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, Chromatic Polynomial

Columns k=1-7 give: A000027, A091940, A068239*2, A068240*2, A068241*2, A068242*2, A068243*2.
Rows n=1-20 give: A000007, A007395, A068253*3, A068254*4, A068255*5, A068256*6, A068257*7, A068258*8, A068259*9, A068260*10, A068261*11, A068262*12, A068263*13, A068264*14, A068265*15, A068266*16, A068267*17, A068268*18, A068269*19, A068270*20.
Cf. A182368.

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.

Original entry on oeis.org

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

R. H. Hardin, Feb 20 2013

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

			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

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

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

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]

cp's OEIS Frontend

A182406 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is the number of n-colorings of the square grid graph G_(k,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs