|
%I #54 Jun 28 2017 02:11:11
%S 1,2,2,4,6,4,8,18,18,8,16,54,82,54,16,32,162,374,374,162,32,64,486,
%T 1706,2604,1706,486,64,128,1458,7782,18150,18150,7782,1458,128,256,
%U 4374,35498,126534,193662,126534,35498,4374,256,512,13122,161926,882180,2068146,2068146,882180,161926,13122,512
%N Array T(m,n) read by antidiagonals: T(m,n) = number of ways of 3-coloring an m X n grid (m >= 1, n >= 1).
%C 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
%C 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
%C Also the number of Miura-ori foldings [Ginepro-Hull]. - _N. J. A. Sloane_, Aug 05 2015
%D 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
%D Michael S. Paterson (Warwick), personal communication.
%H Andrew Howroyd, <a href="/A078099/b078099.txt">Table of n, a(n) for n = 1..1128</a> (terms 1..120 from R. J. Mathar)
%H J. Ginepro, T. C. Hull, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Hull/hull.html">Counting Miura-ori Foldings</a>, Journal of Integer Sequences, Vol. 17, 2014, #14.10.8
%H R. J. Mathar, <a href="http://vixra.org/abs/1511.0225">Counting 2-way monotonic terrace forms...</a>, vixra 1511.0225 (2015), Table T_{n x m}
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexColoring.html">Vertex Coloring</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Graph_coloring">Graph Coloring</a>
%F Let M[1] = [1], M[m+1] = [ 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).
%F T(3,n) = A052913(n). T(4,n) = 2*A078100(n).
%F 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
%e Array begins:
%e 1 2 4 8 16 32 64 128 256 512 ...
%e 2 6 18 54 162 486 1458 4374 13122 ...
%e 4 18 82 374 1706 7782 35498 161926 ...
%e 8 54 374 2604 18150 126534 882180 ...
%e 16 162 1706 18150 193662 ...
%e 32 486 7782 126534 ...
%e 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).
%e For the 2 X 2 case, the colorings are
%e 12 12 12 13 13 13
%e 21 23 31 31 32 21
%p 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);
%p 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:
%p T := proc(m,n) evalm( v[m] &* W[m]^(n-1) &* t(v[m]) ); end;
%t 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 *)
%Y Cf. A207997, A020698, A078100. Main diagonal is A068253. Other diagonals produce A078101 and A078102.
%Y Cf. A222444 (4 colorings), A222144 (5 colorings), A222281 (6 colorings), A222340 (7 colorings), A222462 (8 colorings).
%K nonn,tabl
%O 1,2
%A _N. J. A. Sloane_, Dec 05 2002
%E More terms from _Alois P. Heinz_, Mar 23 2009
|
