A198710 -id:A198710 - cp's OEIS frontend

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

1, 1, 1, 2, 4, 2, 5, 25, 25, 5, 14, 172, 401, 172, 14, 41, 1201, 6548, 6548, 1201, 41, 122, 8404, 107042, 250031, 107042, 8404, 122, 365, 58825, 1749965, 9548295, 9548295, 1749965, 58825, 365, 1094, 411772, 28609241, 364637102, 851787199, 364637102

Offset: 1

R. H. Hardin, Oct 29 2011

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

			Table starts
....1........1............2...............5..................14
....1........4...........25.............172................1201
....2.......25..........401............6548..............107042
....5......172.........6548..........250031.............9548295
...14.....1201.......107042.........9548295...........851787199
...41.....8404......1749965.......364637102.........75987485516
..122....58825.....28609241.....13925032958.......6778819400772
..365...411772....467717288....531779578441.....604736581320925
.1094..2882401...7646461682..20307996787865...53948385378521909
.3281.20176804.125007943505.775536991678112.4812720805166620356
...
Some solutions with all values from 0 to 3 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..2..1....0..1..0..1....0..1..0..1....0..1..0..2....0..1..0..1
..1..2..0..3....2..0..3..0....2..0..1..0....1..2..1..3....1..2..3..0
..2..0..2..0....1..3..0..2....3..2..0..2....0..3..0..2....3..1..2..3
..3..2..0..1....3..2..1..0....0..3..2..1....3..1..3..0....1..3..1..0

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 A007051(n-2), A034494(n-1), A198710, A198711, A198712, A198713, A198714.
Main diagonal is A198709.
Cf. A207997 (3 colorings), A222444 (labeled 4 colorings), A198906 (5 colorings), A198982 (6 colorings), A198723 (7 colorings), A198914 (8 colorings), A207868 (unlimited).

A355882 Number of ways to 4-color a 3 X n grid ignoring the variations of two colors.

Original entry on oeis.org

3, 49, 801, 13095, 214083, 3499929, 57218481, 935434575, 15292923363, 250015887009, 4087377035361, 66822357687255, 1092443258415843, 17859774993929289, 291979981913499441, 4773425749606899135, 78038203981259699523, 1275805176423288314769

Offset: 1

Gerhard Kirchner, Jul 24 2022

See A355881 for a general formula.

			a(1) = 3, 4 colors 1,2,3,4: 121, 123, 124.
The first two colors do not vary.

Paolo Xausa, Table of n, a(n) for n = 1..800
Index entries for linear recurrences with constant coefficients, signature (18,-27).

Cf. A198710, A355881, A355883.

LinearRecurrence[{18, -27}, {3, 49}, 20] (* Paolo Xausa, Oct 03 2024 *)

G.f.: x*(3-5*x)/(1-18*x+27*x^2).
a(n) = 18*a(n-1) - 27*a(n-2) with a(1) = 3, a(2) = 49.
a(n) = 3^(n-7/2)*((12 + 5*sqrt(6))*(3 + sqrt(6))^n - (3 - sqrt(6))^n*(12 - 5*sqrt(6)))/(2*sqrt(2)). - Stefano Spezia, Jul 24 2022
a(n) = 2*A198710(n) - 1. - Hugo Pfoertner, Jul 24 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs