OFFSET
1,2
COMMENTS
We assume the top left point gets color 1 (or, in other words, take the total number of colorings and divide by 3). The rule for coloring is that horizontally or vertically adjacent points must have different colors. - N. J. A. Sloane, Feb 12 2013
Equals half the number of m X n binary matrices with no 2 X 2 circuit having the pattern 0011 in any orientation. - R. H. Hardin, Oct 06 2010
Also the number of Miura-ori foldings [Ginepro-Hull]. - N. J. A. Sloane, Aug 05 2015
REFERENCES
Thomas C. Hull, Coloring Connections with Counting Mountain-Valley Assignments in (book) Origami^6: I. Mathematics, 2015, ed. Koryo Miura, Toshikazu Kawasaki, Tomohiro Tachi, Ryuhei Uehara, Robert J. Lang, Patsy Wang-Iverson, American Mathematical Soc., Dec 18, 2015, 368 pages
Michael S. Paterson (Warwick), personal communication.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1128 (terms 1..120 from R. J. Mathar)
J. Ginepro, T. C. Hull, Counting Miura-ori Foldings, Journal of Integer Sequences, Vol. 17, 2014, #14.10.8
R. J. Mathar, Counting 2-way monotonic terrace forms..., vixra 1511.0225 (2015), Table T_{n x m}
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Vertex Coloring
Wikipedia, Graph Coloring
FORMULA
Let M[1] = [1], M[m+1] = the block matrix [ [ M[m], M[m]' ], [ 0, M[m] ] ], W[m] = M[m] + M[m]', then T(m, n) = sum of entries of W[m]^(n-1) (the prime denotes transpose).
T(n,m) = T(m,n). T(1,n)= A000079(n-1). T(2,n)=A025192(n). T(5,n) = 2*A207994(n). T(6,n) = 2*A207995(n). - R. J. Mathar, Nov 23 2015
EXAMPLE
Array begins:
1 2 4 8 16 32 64 128 256 512 ...
2 6 18 54 162 486 1458 4374 13122 ...
4 18 82 374 1706 7782 35498 161926 ...
8 54 374 2604 18150 126534 882180 ...
16 162 1706 18150 193662 ...
32 486 7782 126534 ...
For the 1 X n case: the first point gets color 1, thereafter there are 2 choices for each color, so T(1,n) = 2^(n-1).
For the 2 X 2 case, the colorings are
12 12 12 13 13 13
21 23 31 31 32 21
MAPLE
with(linalg); t := transpose; M[1] := matrix(1, 1, [1]); Z[1] := matrix(1, 1, 0); W[1] := evalm(M[1]+t(M[1])); v[1] := matrix(1, 1, 1);
for n from 2 to 6 do t1 := stackmatrix(M[n-1], Z[n-1]); t2 := stackmatrix(t(M[n-1]), M[n-1]); M[n] := t(stackmatrix(t(t1), t(t2))); Z[n] := matrix(2^(n-1), 2^(n-1), 0); W[n] := evalm(M[n]+t(M[n])); v[n] := matrix(1, 2^(n-1), 1); od:
T := proc(m, n) evalm( v[m] &* W[m]^(n-1) &* t(v[m]) ); end;
MATHEMATICA
mmax = 10; M[1] = {{1}}; M[m_] := M[m] = {{M[m-1], Transpose[M[m-1]]}, {Array[0&, {2^(m-2), 2^(m-2)}], M[m-1]}} // ArrayFlatten; W[m_] := M[m] + Transpose[M[m]]; T[m_, 1] := 2^(m-1); T[1, n_] := 2^(n-1); T[m_, n_] := MatrixPower[W[m], n-1] // Flatten // Total; Table[T[m-n+1, n], {m, 1, mmax}, {n, 1, m}] // Flatten (* Jean-François Alcover, Feb 13 2016 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
N. J. A. Sloane, Dec 05 2002
EXTENSIONS
More terms from Alois P. Heinz, Mar 23 2009
STATUS
approved