login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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 A118960

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 7 08:08 EDT 2020. Contains 336274 sequences. (Running on oeis4.)