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

1, 1, 1, 2, 4, 2, 5, 34, 34, 5, 15, 500, 2052, 500, 15, 52, 10900, 278982, 278982, 10900, 52, 203, 322768, 68162042, 455546040, 68162042, 322768, 203, 877, 12297768, 26419793726, 1625686993918, 1625686993918, 26419793726, 12297768, 877

Offset

1,4

Comments

Table starts

...1.........1..............2.................5.................15

...1.........4.............34...............500..............10900

...2........34...........2052............278982...........68162042

...5.......500.........278982.........455546040......1625686993918

..15.....10900.......68162042.....1625686993918.103204230192540988

..52....322768....26419793726.10764437129618296

.203..12297768.15002771641712

.877.580849872

Links

Andrew Howroyd, Table of n, a(n) for n = 1..231 (terms 1..49 from R. H. Hardin)

Eric Weisstein's World of Mathematics, Grid Graph.

Eric Weisstein's World of Mathematics, Vertex Coloring.

Wikipedia, Graph Coloring.

Example

Some solutions for n=5 k=3
..0..1..0....0..1..2....0..1..0....0..1..0....0..1..2....0..1..0....0..1..0
..1..0..1....1..0..3....1..0..1....1..0..1....1..2..0....1..0..1....1..0..1
..0..1..0....0..1..0....0..1..0....2..1..0....0..1..2....0..2..3....0..1..2
..1..0..1....1..0..1....1..0..1....0..2..3....1..0..1....1..0..1....1..0..1
..0..1..0....0..1..0....2..1..0....1..3..0....2..1..0....0..1..0....0..1..0

Crossrefs

Columns 1..5 are A000110(n-1), A207864, A207865, A207866, A207867.

Main diagonal is A207863.

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

Cf. A207981, A208001 (knight), A208021 (king), A208054, A208096, A208301.

Sequence in context: A198982 A198723 A198914 * A135690 A010241 A366839

Adjacent sequences: A207865 A207866 A207867 * A207869 A207870 A207871

Keyword

nonn,tabl

Author

R. H. Hardin, Feb 21 2012

Status

approved