A222340 -id:A222340

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

Search: a222340 -id:a222340

Displaying 1-10 of 12 results found.

page 1 2

A198723

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

+10
15

1, 1, 1, 2, 4, 2, 5, 34, 34, 5, 15, 499, 2027, 499, 15, 52, 10507, 232841, 232841, 10507, 52, 203, 272410, 34003792, 173549032, 34003792, 272410, 203, 876, 7817980, 5315840795, 141168480719, 141168480719, 5315840795, 7817980, 876, 4111

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

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

LINKS

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

EXAMPLE

Table starts

.....1............1...................2.......................5

.....1............4..................34.....................499

.....2...........34................2027..................232841

.....5..........499..............232841...............173549032

....15........10507............34003792............141168480719

....52.......272410..........5315840795.........116492275674072

...203......7817980........846047363854.......96356630422085931

...876....234638905.....135284283124811....79732515488691835557

..4111...7176366133...21658679381667910.65980773070548173552412

.20648.221220625936.3468618095206638077

...

Some solutions with all values 0 to 6 for n=3, k=3:

..0..1..2....0..1..2....0..1..2....0..1..2....0..1..2....0..1..0....0..1..2

..3..2..4....2..3..1....3..4..5....1..3..4....3..4..3....2..3..4....3..4..3

..4..5..6....4..5..6....6..2..4....5..0..6....1..5..6....5..4..6....5..6..2

CROSSREFS

Columns 1-7 are A056273(n-1), A198717, A198718, A198719, A198720, A198721, A198722.

Main diagonal is A198716.

Cf. A207997 (3 colorings), A198715 (4 colorings), A198906 (5 colorings), A198982 (6 colorings), A222340 (labeled 7 colorings), A198914 (8 colorings), A207868 (unlimited).

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Oct 29 2011

STATUS

approved

A222144

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

+10
14

1, 4, 4, 16, 52, 16, 64, 676, 676, 64, 256, 8788, 28564, 8788, 256, 1024, 114244, 1206964, 1206964, 114244, 1024, 4096, 1485172, 50999956, 165770032, 50999956, 1485172, 4096, 16384, 19307236, 2154990196, 22767656980, 22767656980

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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

FORMULA

T(n,k) = 4 * (6*A198906(n,k) - 3*A207997(n,k) - 2) for n*k > 1. - Andrew Howroyd, Jun 27 2017

EXAMPLE

Table starts

.......1.............4...................16.........................64

.......4............52..................676.......................8788

......16...........676................28564....................1206964

......64..........8788..............1206964..................165770032

.....256........114244.............50999956................22767656980

....1024.......1485172...........2154990196..............3127020364012

....4096......19307236..........91058563924............429480137694664

...16384.....250994068........3847656513844..........58986884432558548

...65536....3262922884......162581749707796........8101544704688334244

..262144...42417997492.....6869850581244916.....1112705429924911477552

.1048576..551433967396...290283793189916884...152824358676750267429220

.4194304.7168641576148.12265868026121849524.20989638386627725143014812

...

Some solutions for n=3, k=4:

..0..0..1..1....0..0..0..0....0..0..0..0....0..0..0..0....0..0..1..1

..1..1..2..2....1..1..1..2....0..1..3..3....0..2..2..0....0..1..2..3

..3..4..0..0....1..3..1..3....2..2..0..1....0..2..2..2....1..4..2..3

CROSSREFS

Columns 1-7 are A000302(n-1), A222138, A222139, A222140, A222141, A222142, A222143.

Main diagonal is A068255.

Cf. A078099 (3 colorings), A222444 (4 colorings), A198906 (unlabeled 5 colorings), A222281 (6 colorings), A222340 (7 colorings), A222462 (8 colorings).

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Feb 09 2013

STATUS

approved

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.

+10
14

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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

FORMULA

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]

EXAMPLE

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

CROSSREFS

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

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Feb 20 2013

STATUS

approved

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.

+10
13

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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

FORMULA

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

EXAMPLE

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

CROSSREFS

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

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Feb 14 2013

STATUS

approved

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

+10
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] = 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

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

KEYWORD

nonn,tabl

AUTHOR

N. J. A. Sloane, Dec 05 2002

EXTENSIONS

More terms from Alois P. Heinz, Mar 23 2009

STATUS

approved

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.

+10
11

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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

FORMULA

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

EXAMPLE

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

CROSSREFS

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

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Feb 21 2013

STATUS

approved

A068257

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

+10
3

1, 186, 923526, 122408393436, 433110977725751106, 40908457493732914322944536, 103146129375410533061371714364918916, 6942544711174164051575906086886643368922134556, 12474132532762777585883439690925675118905860580968258566406

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

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

MATHEMATICA

A222340 = Cases[Import["https://oeis.org/A222340/b222340.txt", "Table"], {_, _}][[All, 2]];

a[n_] := A222340[[2 n^2 - 2 n + 1]];

Table[a[n], {n, 1, 13}] (* Jean-François Alcover, Sep 23 2019 *)

CROSSREFS

Main diagonal of A222340.

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

KEYWORD

nonn

AUTHOR

R. H. Hardin, Feb 24 2002

EXTENSIONS

a(7)-a(9) from Alois P. Heinz, Apr 27 2012

STATUS

approved

A222335

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

+10
2

6, 186, 5766, 178746, 5541126, 171774906, 5325022086, 165075684666, 5117346224646, 158637732964026, 4917769721884806, 152450861378428986, 4725976702731298566, 146505277784670255546, 4541663611324777921926

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

Column 2 of A222340

LINKS

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

FORMULA

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

EXAMPLE

Some solutions for n=3

..0..4....0..4....0..1....0..3....0..4....0..0....0..4....0..1....0..3....0..0

..1..6....3..1....5..3....5..1....5..6....3..3....1..5....3..5....0..3....3..3

..3..0....5..5....5..1....1..2....5..1....0..0....4..6....5..1....1..6....5..0

KEYWORD

nonn

AUTHOR

R. H. Hardin Feb 15 2013

STATUS

approved

A222336

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

+10
2

36, 5766, 923526, 147918906, 23691810366, 3794659477146, 607781352505806, 97346856728146986, 15591808593304758846, 2497301950787699442426, 399986762028752524653486, 64064904024834487199387466

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

Column 3 of A222340.

LINKS

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

FORMULA

Empirical: a(n) = 165*a(n-1) - 774*a(n-2).

Empirical g.f.: 6*x*(6 - 29*x) / (1 - 165*x + 774*x^2). - Colin Barker, Mar 15 2018

EXAMPLE

Some solutions for n=3:

..0..0..2....0..0..1....0..0..1....0..0..2....0..0..3....0..0..2....0..0..5

..3..3..0....0..1..2....1..2..5....1..1..6....2..2..5....3..0..3....0..3..6

..1..1..4....5..3..6....6..6..1....4..1..2....4..0..0....0..3..4....3..5..3

CROSSREFS

Cf. A222340

KEYWORD

nonn

AUTHOR

R. H. Hardin, Feb 15 2013

STATUS

approved

A222337

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

+10
2

216, 178746, 147918906, 122408393436, 101297497221786, 83827445649884946, 69370328359709445996, 57406526220963704077986, 47506035082750189614687546, 39313010520733216994188515036, 32532978041867113135439462852106

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

Column 4 of A222340.

LINKS

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

FORMULA

Empirical: a(n) = 873*a(n-1) - 38091*a(n-2) + 387974*a(n-3).

Empirical g.f.: 6*x*(36 - 1637*x + 16884*x^2) / (1 - 873*x + 38091*x^2 - 387974*x^3). - Colin Barker, Mar 15 2018

EXAMPLE

Some solutions for n=3:

..0..0..2..0....0..2..2..0....0..2..0..0....0..2..0..0....0..2..2..0

..0..3..5..0....0..3..3..0....0..5..3..0....0..0..2..0....0..3..4..0

..0..3..1..1....2..3..3..5....3..3..4..4....3..5..6..3....0..3..0..1

CROSSREFS

Cf. A222340.

KEYWORD

nonn

AUTHOR

R. H. Hardin, Feb 15 2013

STATUS

approved

page 1 2

Search completed in 0.013 seconds