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

Author

Adam P. Goucher, Sep 11 2013

Keywords

• nonn
• easy

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.

Examples

			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.
		

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

Programs

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

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

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