A223395 4 X 4 square grid graph coloring a rectangular array: number of n X 1 0..15 arrays where 0..15 label nodes of the square grid graph and every array movement to a horizontal or vertical neighbor moves along an edge of this graph.

16, 48, 152, 488, 1576, 5096, 16488, 53352, 172648, 558696, 1807976, 5850728, 18933352, 61269608, 198272616, 641623656, 2076337768, 6719170152, 21743691368, 70364063336, 227702892136, 736862037608, 2384535643752, 7716519437928

Offset

1,1

Comments

Column 1 of A223402.

Links

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

Formula

Empirical: a(n) = 3*a(n-1) + 2*a(n-2) - 4*a(n-3).

Conjectures from Colin Barker, Aug 20 2018: (Start)

G.f.: 8*x*(2 - 3*x^2) / ((1 - x)*(1 - 2*x - 4*x^2)).

a(n) = (8 + (11-5*sqrt(5))*(1-sqrt(5))^n + (1+sqrt(5))^n*(11+5*sqrt(5))) / 5.

(End)

Example

Some solutions for n=3:
.12....9....5....0...10....2....5....0....7....1...10....6...12...11...15....2
..8...13....6....1....9....3....6....4....3....0....9...10...13...10...11....1
.12...12....2....2....8....2....5....5....2....1...10...11....9...11...10....0
Vertex neighbors:
0 -> 1 4
1 -> 0 2 5
2 -> 1 3 6
3 -> 2 7
4 -> 0 5 8
5 -> 4 1 6 9
6 -> 5 2 7 10
7 -> 6 3 11
8 -> 4 9 12
9 -> 8 5 10 13
10 -> 9 6 11 14
11 -> 10 7 15
12 -> 8 13
13 -> 12 9 14
14 -> 13 10 15
15 -> 14 11

Crossrefs

Cf. A223402.

Sequence in context: A211598 A235541 A109098 * A202329 A223599 A223692

Adjacent sequences: A223392 A223393 A223394 * A223396 A223397 A223398

Keyword

nonn

Author

R. H. Hardin, Mar 19 2013

Status

approved