The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A078099 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). 12
 1, 2, 2, 4, 6, 4, 8, 18, 18, 8, 16, 54, 82, 54, 16, 32, 162, 374, 374, 162, 32, 64, 486, 1706, 2604, 1706, 486, 64, 128, 1458, 7782, 18150, 18150, 7782, 1458, 128, 256, 4374, 35498, 126534, 193662, 126534, 35498, 4374, 256, 512, 13122, 161926, 882180, 2068146, 2068146, 882180, 161926, 13122, 512 (list; table; graph; refs; listen; history; text; internal format)
 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] = [ 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(3,n) = A052913(n). T(4,n) = 2*A078100(n). 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 Cf. A207997, A020698, A078100. Main diagonal is A068253. Other diagonals produce A078101 and A078102. Cf. A222444 (4 colorings), A222144 (5 colorings), A222281 (6 colorings), A222340 (7 colorings), A222462 (8 colorings). Sequence in context: A059474 A252828 A208314 * A264872 A303306 A347797 Adjacent sequences: A078096 A078097 A078098 * A078100 A078101 A078102 KEYWORD nonn,tabl AUTHOR N. J. A. Sloane, Dec 05 2002 EXTENSIONS More terms from Alois P. Heinz, Mar 23 2009 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 21 03:47 EDT 2024. Contains 374463 sequences. (Running on oeis4.)