A222144 -id:A222144 - cp's OEIS frontend

A198906 T(n,k) = number of n X k 0..4 arrays with values 0..4 introduced in row major order and no element equal to any horizontal or vertical neighbor.

1, 1, 1, 2, 4, 2, 5, 33, 33, 5, 15, 380, 1211, 380, 15, 51, 4801, 50384, 50384, 4801, 51, 187, 62004, 2125425, 6907736, 2125425, 62004, 187, 715, 804833, 89793204, 948656912, 948656912, 89793204, 804833, 715, 2795, 10459180, 3794115705

Offset: 1

R. H. Hardin, Oct 31 2011

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

			Table starts
.....1..........1...............2....................5
.....1..........4..............33..................380
.....2.........33............1211................50384
.....5........380...........50384..............6907736
....15.......4801.........2125425............948656912
....51......62004........89793204.........130292546801
...187.....804833......3794115705.......17895005957823
...715...10459180....160319061892.....2457786852894234
..2795..135958401...6774239755817...337564362706067534
.11051.1767426404.286243775060868.46362726246946052884
...
Some solutions with values 0 to 4 for n=6, k=4:
..0..1..0..1....0..1..0..1....0..1..0..1....0..1..0..1....0..1..0..1
..1..0..1..0....1..0..1..0....1..0..1..0....1..0..1..0....1..0..1..0
..0..1..0..2....0..1..0..2....0..1..0..2....0..1..0..2....0..1..0..2
..2..0..2..0....2..0..3..0....2..0..2..3....2..0..1..0....2..0..1..3
..3..2..1..4....0..1..0..4....0..4..0..2....3..2..4..3....0..3..4..2
..2..4..2..1....2..4..3..1....1..3..1..4....1..0..1..2....4..0..1..4

Andrew Howroyd, Table of n, a(n) for n = 1..378 (terms 1..127 from R. H. Hardin)

Columns 1-7 are A007581(n-2), A198900, A198901, A198902, A198903, A198904, A198905.
Main diagonal is A198899.
Cf. A207997 (3 colorings), A198715 (4 colorings), A222144 (labeled 5 colorings), A198982 (6 colorings), A198723 (7 colorings), A198914 (8 colorings), A207868 (unlimited).

A222444 T(n,k) = number of n X k 0..3 arrays with entries increasing mod 4 by 0, 1 or 2 rightwards and downwards, starting with upper left zero.

Original entry on oeis.org

1, 3, 3, 9, 21, 9, 27, 147, 147, 27, 81, 1029, 2403, 1029, 81, 243, 7203, 39285, 39285, 7203, 243, 729, 50421, 642249, 1500183, 642249, 50421, 729, 2187, 352947, 10499787, 57289767, 57289767, 10499787, 352947, 2187, 6561, 2470629, 171655443

Offset: 1

R. H. Hardin, Feb 20 2013

1/4 the number of 4-colorings of the grid graph P_n X P_k. - Andrew Howroyd, Jun 26 2017

			Table starts
......1..........3...............9..................27.......................81
......3.........21.............147................1029.....................7203
......9........147............2403...............39285...................642249
.....27.......1029...........39285.............1500183.................57289767
.....81.......7203..........642249............57289767...............5110723191
....243......50421........10499787..........2187822609.............455924913093
....729.....352947.......171655443.........83550197745...........40672916404629
...2187....2470629......2806303725.......3190677470643.........3628419487925547
...6561...17294403.....45878770089.....121847980727187.......323690312271131451
..19683..121060821....750047661027....4653221950068669.....28876324830999722133
..59049..847425747..12262131106083..177700725073710285...2576049100980154511889
.177147.5931980229.200467073061765.6786168386579878383.229808641254065144560647
...
Some solutions for n=3, k=4:
..0..0..0..2....0..0..2..0....0..2..0..0....0..2..0..2....0..0..2..3
..1..2..2..3....0..2..3..1....2..2..2..0....0..0..0..2....0..2..3..1
..2..2..3..1....2..0..1..3....2..2..0..0....2..0..1..3....1..2..0..1

Andrew Howroyd, Table of n, a(n) for n = 1..496 (terms 1..180 from R. H. Hardin)
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Vertex Coloring
Wikipedia, Graph Coloring

Columns 1-7 are A000244(n-1), A169634(n-1), A222439, A222440, A222441, A222442, A222443.
Main diagonal is A068254.
Cf. A078099 (3 colorings), A198715 (unlabeled 4 colorings), A222144 (5 colorings), A222281 (6 colorings), A222340 (7 colorings), A222462 (8 colorings).

T(n,k) = 6*A198715(n,k) - 3 for n*k>1. - Andrew Howroyd, Jun 27 2017
Empirical for column k:
k=1: a(n) = 3*a(n-1).
k=2: a(n) = 7*a(n-1).
k=3: a(n) = 18*a(n-1) - 27*a(n-2).
k=4: a(n) = 45*a(n-1) - 267*a(n-2) + 263*a(n-3).
k=5: a(n) = 118*a(n-1) - 2811*a(n-2) + 22255*a(n-3) - 53860*a(n-4) - 54747*a(n-5) + 269406*a(n-6) - 175392*a(n-7).
k=6: [order 13]
k=7: [order 32]

A222281 T(n,k) = number of n X k 0..5 arrays with no entry increasing mod 6 by 5 rightwards or downwards, starting with upper left zero.

Original entry on oeis.org

1, 5, 5, 25, 105, 25, 125, 2205, 2205, 125, 625, 46305, 194485, 46305, 625, 3125, 972405, 17153945, 17153945, 972405, 3125, 15625, 20420505, 1513010465, 6354787485, 1513010465, 20420505, 15625, 78125, 428830605, 133450391205

Offset: 1

R. H. Hardin, Feb 14 2013

1/6 the number of 6-colorings of the grid graph P_n X P_k. - Andrew Howroyd, Jun 26 2017

			Table starts
........1................5......................25..........................125
........5..............105....................2205........................46305
.......25.............2205..................194485.....................17153945
......125............46305................17153945...................6354787485
......625...........972405..............1513010465................2354171487645
.....3125.........20420505............133450391205..............872117822449905
....15625........428830605..........11770577485085...........323081602357856985
....78125.......9005442705........1038187247574145........119687637492011211885
...390625.....189114296805.......91570083319317865......44339047670574481807485
..1953125....3971400232905.....8076654937439905005...16425682631297501047982145
..9765625...83399404891005...712376276332499775685.6084998755694142903356375385
.48828125.1751387502711105.62832938018547611186345
...
Some solutions for n=3, k=4:
..0..0..0..0....0..0..0..0....0..0..0..0....0..3..0..0....0..0..0..0
..4..2..0..1....1..2..0..4....0..0..0..1....0..0..3..1....0..2..3..0
..0..4..1..4....1..4..1..2....3..4..4..1....3..0..4..4....4..5..1..3

Andrew Howroyd, Table of n, a(n) for n = 1..325 (terms 1..111 from R. H. Hardin)

Columns 1-7 are A000351(n-1), 5*A009965(n-1), A222276, A222277, A222278, A222279, A222280.
Main diagonal is A068256.
Cf. A078099 (3 colorings), A222444 (4 colorings), A222144 (5 colorings), A198982 (unlabeled 6 colorings), A222340 (7 colorings), A222462 (8 colorings).

T(n, k) = 5 * (24*A198982(n,k) - 12*A198715(n,k) - 8*A207997(n,k) - 3) for n*k > 1. - Andrew Howroyd, Jun 27 2017

A222340 T(n,k) = number of n X k 0..6 arrays with no entry increasing mod 7 by 6 rightwards or downwards, starting with upper left zero.

Original entry on oeis.org

1, 6, 6, 36, 186, 36, 216, 5766, 5766, 216, 1296, 178746, 923526, 178746, 1296, 7776, 5541126, 147918906, 147918906, 5541126, 7776, 46656, 171774906, 23691810366, 122408393436, 23691810366, 171774906, 46656, 279936, 5325022086

Offset: 1

R. H. Hardin, Feb 15 2013

1/7 the number of 7-colorings of the grid graph P_n X P_k. - Andrew Howroyd, Jun 26 2017

			Table starts
.......1.............6...................36........................216
.......6...........186.................5766.....................178746
......36..........5766...............923526..................147918906
.....216........178746............147918906...............122408393436
....1296.......5541126..........23691810366............101297497221786
....7776.....171774906........3794659477146..........83827445649884946
...46656....5325022086......607781352505806.......69370328359709445996
..279936..165075684666....97346856728146986....57406526220963704077986
.1679616.5117346224646.15591808593304758846.47506035082750189614687546
...
Some solutions for n=3, k=4:
..0..0..2..0....0..2..2..0....0..0..0..0....0..2..0..0....0..2..0..0
..0..5..3..0....0..2..5..0....0..1..5..0....0..5..0..0....0..0..5..0
..3..1..4..5....4..4..2..3....3..6..1..4....2..2..2..2....4..1..3..4

Andrew Howroyd, Table of n, a(n) for n = 1..325 (terms 1..84 from R. H. Hardin)

Columns 1-6 are A000400(n-1), A222335, A222336, A222337, A222338, A222339.
Main diagonal is A068257.
Cf. A078099 (3 colorings), A222444 (4 colorings), A222144 (5 colorings), A222281 (6 colorings), A198723 (unlabeled 7 colorings), A222462 (8 colorings).

T(n, k) = 6 * (120*A198723(n,k) - 60*A198906(n,k) - 40*A198715(n,k) - 15*A207997(n,k) - 4) for n*k > 1. - Andrew Howroyd, Jun 27 2017

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

N. J. A. Sloane, Dec 05 2002

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

			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

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.

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

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

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;

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

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

More terms from Alois P. Heinz, Mar 23 2009

A222462 T(n,k) = number of n X k 0..7 arrays with no entry increasing mod 8 by 7 rightwards or downwards, starting with upper left zero.

Original entry on oeis.org

1, 7, 7, 49, 301, 49, 343, 12943, 12943, 343, 2401, 556549, 3418807, 556549, 2401, 16807, 23931607, 903055069, 903055069, 23931607, 16807, 117649, 1029059101, 238535974201, 1465295106499, 238535974201, 1029059101, 117649, 823543

Offset: 1

R. H. Hardin, Feb 21 2013

1/8 the number of 8-colorings of the grid graph P_n X P_k. - Andrew Howroyd, Jun 26 2017

			Table starts
......1.............7..................49........................343
......7...........301...............12943.....................556549
.....49.........12943.............3418807..................903055069
....343........556549...........903055069..............1465295106499
...2401......23931607........238535974201...........2377584520856755
..16807....1029059101......63007686842527........3857863258420747009
.117649...44249541343...16643060295393343.....6259760185235726701945
.823543.1902730277749.4396153388210813341.10157072698503130798653535
...
Some solutions for n=3, k=4:
..0..4..2..3....0..0..0..4....0..4..6..1....0..4..0..4....0..2..6..2
..0..0..5..6....0..0..4..6....0..0..1..5....0..0..6..0....0..0..2..3
..0..0..0..1....0..0..5..1....0..0..3..5....0..0..0..1....0..0..3..5

Andrew Howroyd, Table of n, a(n) for n = 1..276 (terms 1..83 from R. H. Hardin)

Columns 1-5 are A000420(n-1), 7*43^(n-1), A222459, A222460, A222461.
Main diagonal is A068258.
Cf. A078099 (3 colorings), A222444 (4 colorings), A222144 (5 colorings), A222281 (6 colorings), A222340 (7 colorings), A198914 (unlabeled 8 colorings).

T(n, k) = 7 * (720*A198914(n,k) - 360*A198982(n,k) - 240*A198906(n,k) - 90*A198715(n,k) - 24*A207997(n,k) - 5) for n*k > 1. - Andrew Howroyd, Jun 27 2017
Empirical for column k:
k=1: a(n) = 7*a(n-1).
k=2: a(n) = 43*a(n-1).
k=3: a(n) = 270*a(n-1) - 1547*a(n-2).
k=4: a(n) = 1689*a(n-1) - 108775*a(n-2) + 1672631*a(n-3).
k=5: a(n) = 10754*a(n-1) - 8060499*a(n-2) + 2219242223*a(n-3) - 245682627864*a(n-4) + 5798947687589*a(n-5) + 448113231493438*a(n-6) - 2763020698450992*a(n-7).

A068255 1/5 the number of colorings of an n X n square array with 5 colors.

Original entry on oeis.org

1, 52, 28564, 165770032, 10164078082036, 6584229526795818280, 45062665956031451017237456, 3258395057698765483724093981321824, 2489232886416012985921659124731697904597044, 20091032492258710696689787524926465967570325433558752

Offset: 1

R. H. Hardin, Feb 24 2002

nonn

Jean-François Alcover, Table of n, a(n) for n = 1..14

Main diagonal of A222144.

Cf. A068239-A068305, A000332, A002417, A027441, A182368, A182406.

A222144 = Cases[Import["https://oeis.org/A222144/b222144.txt", "Table"], {, }][[All, 2]];
a[n_] := A222144[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 14}] (* Jean-François Alcover, Sep 23 2019 *)

a(8)-a(10) from Alois P. Heinz, Apr 27 2012

A222139 Number of n X 3 0..4 arrays with no entry increasing mod 5 by 4 rightwards or downwards, starting with upper left zero.

Original entry on oeis.org

16, 676, 28564, 1206964, 50999956, 2154990196, 91058563924, 3847656513844, 162581749707796, 6869850581244916, 290283793189916884, 12265868026121849524, 518291141165452870036, 21900260661415244606836

Offset: 1

R. H. Hardin, Feb 09 2013

nonn

Column 3 of A222144.

			Some solutions for n=3:
  0 2 4    0 1 1    0 1 4    0 0 2    0 1 3    0 0 0    0 3 4
  1 2 0    2 4 1    1 4 0    2 2 2    3 1 1    3 3 1    2 3 4
  1 3 1    3 1 2    3 0 1    3 0 2    1 4 1    3 1 1    2 0 1

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A222144.

Empirical: a(n) = 45*a(n-1) - 116*a(n-2).
Conjectures from Colin Barker, Mar 14 2018: (Start)
G.f.: 4*x*(4 - 11*x) / (1 - 45*x + 116*x^2).
a(n) = (2^(-1-n)*((45-sqrt(1561))^n*(-433+11*sqrt(1561)) + (45+sqrt(1561))^n*(433+11*sqrt(1561)))) / (29*sqrt(1561)).
(End)

A222138 Number of nX2 0..4 arrays with no entry increasing mod 5 by 4 rightwards or downwards, starting with upper left zero.

Original entry on oeis.org

4, 52, 676, 8788, 114244, 1485172, 19307236, 250994068, 3262922884, 42417997492, 551433967396, 7168641576148, 93192340489924, 1211500426369012, 15749505542797156, 204743572056363028, 2661666436732719364

Offset: 1

R. H. Hardin Feb 09 2013

nonn

Column 2 of A222144

			Some solutions for n=3
..0..1....0..2....0..3....0..2....0..3....0..1....0..3....0..3....0..1....0..1
..0..3....0..0....3..3....0..2....0..0....2..2....1..1....1..1....3..3....0..2
..0..0....0..3....4..0....0..0....0..3....0..3....1..3....2..4....4..0....3..0

R. H. Hardin, Table of n, a(n) for n = 1..210

Empirical: a(n) = 13*a(n-1)

A222140 Number of n X 4 0..4 arrays with no entry increasing mod 5 by 4 rightwards or downwards, starting with upper left zero.

Original entry on oeis.org

64, 8788, 1206964, 165770032, 22767656980, 3127020364012, 429480137694664, 58986884432558548, 8101544704688334244, 1112705429924911477552, 152824358676750267429220, 20989638386627725143014812

Offset: 1

R. H. Hardin, Feb 09 2013

nonn

Column 4 of A222144.

			Some solutions for n=3:
..0..0..1..2....0..0..1..2....0..1..1..2....0..0..1..4....0..1..1..2
..0..3..4..2....0..3..4..2....1..4..1..3....1..1..4..0....0..3..4..0
..0..1..1..2....2..3..0..3....3..0..1..1....1..2..4..1....2..0..2..0

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A222144.

Empirical: a(n) = 153*a(n-1) - 2197*a(n-2) + 6434*a(n-3).

Empirical g.f.: 4*x*(16 - 251*x + 752*x^2) / (1 - 153*x + 2197*x^2 - 6434*x^3). - Colin Barker, Mar 14 2018

cp's OEIS Frontend

A198906 T(n,k) = number of n X k 0..4 arrays with values 0..4 introduced in row major order and no element equal to any horizontal or vertical neighbor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A222444 T(n,k) = number of n X k 0..3 arrays with entries increasing mod 4 by 0, 1 or 2 rightwards and downwards, starting with upper left zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A222281 T(n,k) = number of n X k 0..5 arrays with no entry increasing mod 6 by 5 rightwards or downwards, starting with upper left zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A222340 T(n,k) = number of n X k 0..6 arrays with no entry increasing mod 7 by 6 rightwards or downwards, starting with upper left zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A222462 T(n,k) = number of n X k 0..7 arrays with no entry increasing mod 8 by 7 rightwards or downwards, starting with upper left zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A068255 1/5 the number of colorings of an n X n square array with 5 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A222139 Number of n X 3 0..4 arrays with no entry increasing mod 5 by 4 rightwards or downwards, starting with upper left zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A222138 Number of nX2 0..4 arrays with no entry increasing mod 5 by 4 rightwards or downwards, starting with upper left zero.

Views

Author