OFFSET
2,1
COMMENTS
The strong product of K2 and Cn can be regarded as the King's graph on a 2*n cylindrical (or equivalently toroidal) chessboard.
The Kneser graph construction of the Petersen graph relates this to the number of closed walks on the Petersen graph.
More generally, the number of c-colorings of the strong product of Km and Cn is equal to (m!)^n * (c choose m) * (number of closed walks of length n on K(c,m)).
If n is prime then a(n) is divisible by n, since the cyclic group of order n acts on the colorings, partitioning them into orbits of size n. More generally, n divides a(n) for any Carmichael number n, due to the closed form.
LINKS
Indranil Ghosh, Table of n, a(n) for n = 2..1000
Wolfram MathWorld, Graph Strong Product
Index entries for linear recurrences with constant coefficients, signature (4,20,-48).
FORMULA
a(n) = 6^n + 4*(-4)^n + 5*2^n.
a(n) = 10 * 2^n * A091000(n).
a(n) = 4*a(n-1)+20*a(n-2)-48*a(n-3). G.f.: -120*x^2*(4*x-1) / ((2*x-1)*(4*x+1)*(6*x-1)). - Colin Barker, Oct 20 2013
EXAMPLE
For n = 2, the graph is the complete graph K4, which has a(4) = 120 different 5-colorings corresponding to ordered 4-subsets of {1,2,3,4,5}.
For n = 3, the graph is the complete graph K6, which cannot be 5-colored, so a(3) = 0. Equivalently, there are no closed walks of length 3 on the Petersen graph.
MATHEMATICA
Table[2^n(3^n+4(-2)^n+5), {n, 2, 25}]
LinearRecurrence[{4, 20, -48}, {120, 0, 2400}, 24] (* or *) Drop[CoefficientList[Series[-120*x^2*(4*x - 1) / ((2*x - 1) * (4*x + 1) * (6*x - 1)), {x, 0, 25}], x], 2] (* Indranil Ghosh, Mar 03 2017 *)
PROG
(PARI) a(n) = (2^n) * (3^n + 4*(-2)^n + 5) \\ Indranil Ghosh, Mar 03 2017
(Python) def A229031(n) : return (2**n) * (3**n + 4*(-2)**n +5) # Indranil Ghosh, Mar 03 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Adam P. Goucher, Sep 11 2013
STATUS
approved