cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

A207997 T(n,k) = number of n X k 0..2 arrays with new values 0..2 introduced in row major order and no element equal to any horizontal or vertical neighbor (colorings ignoring permutations of colors).

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 4, 9, 9, 4, 8, 27, 41, 27, 8, 16, 81, 187, 187, 81, 16, 32, 243, 853, 1302, 853, 243, 32, 64, 729, 3891, 9075, 9075, 3891, 729, 64, 128, 2187, 17749, 63267, 96831, 63267, 17749, 2187, 128, 256, 6561, 80963, 441090, 1034073, 1034073, 441090, 80963
Offset: 1

Views

Author

R. H. Hardin, Feb 22 2012

Keywords

Comments

Number of colorings of the grid graph P_n X P_k using a maximum of 3 colors up to permutation of the colors. - Andrew Howroyd, Jun 26 2017

Examples

			Table starts
..1....1.....2.......4.........8.........16...........32............64
..1....3.....9......27........81........243..........729..........2187
..2....9....41.....187.......853.......3891........17749.........80963
..4...27...187....1302......9075......63267.......441090.......3075255
..8...81...853....9075.....96831....1034073.....11045757.....117997043
.16..243..3891...63267...1034073...16932816....277458045....4547477370
.32..729.17749..441090..11045757..277458045...6978332618..175605187731
.64.2187.80963.3075255.117997043.4547477370.175605187731.6787438272198
...
Some solutions for n=4, k=3:
..0..1..2....0..1..0....0..1..0....0..1..2....0..1..2....0..1..2....0..1..0
..2..0..1....2..0..2....1..0..2....1..2..1....2..0..1....1..2..1....1..2..1
..0..2..0....0..1..0....2..1..0....0..1..2....0..2..0....0..1..2....2..0..2
..1..0..1....1..2..1....1..0..1....1..2..0....2..0..2....2..0..1....1..2..0

Links

Crossrefs

Cf. A020698 (column 3), A078100 (column 4), A207994 (column 5), A207995 (column 6), A207996 (column 7).
Main diagonal is A207993.
Cf. A198715 (4 colorings), A198906 (5 colorings), A198982 (6 colorings), A198723 (7 colorings), A198914 (8 colorings), A207868 (unlimited).

Formula

2*T(n,m) = A078099(n,m) for m>1. - R. J. Mathar, Nov 23 2015

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).

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane, Dec 05 2002

Keywords

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

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

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).

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(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

Extensions

More terms from Alois P. Heinz, Mar 23 2009
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.