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).
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
Offset: 1
Examples
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
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
Crossrefs
Programs
-
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 *)
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
Extensions
More terms from Alois P. Heinz, Mar 23 2009
Comments