A229031 Number of 5-colorings of the strong product of the complete graph K2 and the cycle graph Cn.

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.

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

Sequence in context: A156415 A073836 A242836 * A221406 A267428 A156739

Adjacent sequences: A229028 A229029 A229030 * A229032 A229033 A229034

Keyword

nonn,easy

Author

Adam P. Goucher, Sep 11 2013

Status

approved