login
A229031
Number of 5-colorings of the strong product of the complete graph K2 and the cycle graph Cn.
1
120, 0, 2400, 3840, 63360, 215040, 1943040, 9031680, 64665600, 346030080, 2243911680, 12792299520, 79437987840, 465890181120, 2838290104320, 16857940623360, 101834835886080, 608260231004160, 3660556491816960, 21919358464819200, 131692072607416320, 789448748118835200, 4739507238312345600, 28425784430470103040
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.
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
Sequence in context: A156415 A073836 A242836 * A221406 A267428 A156739
KEYWORD
nonn,easy
AUTHOR
Adam P. Goucher, Sep 11 2013
STATUS
approved