cp's OEIS Frontend

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

%I A229031 #27 Feb 16 2025 08:33:20
%S A229031 120,0,2400,3840,63360,215040,1943040,9031680,64665600,346030080,
%T A229031 2243911680,12792299520,79437987840,465890181120,2838290104320,
%U A229031 16857940623360,101834835886080,608260231004160,3660556491816960,21919358464819200,131692072607416320,789448748118835200,4739507238312345600,28425784430470103040
%N A229031 Number of 5-colorings of the strong product of the complete graph K2 and the cycle graph Cn.
%C A229031 The strong product of K2 and Cn can be regarded as the King's graph on a 2*n cylindrical (or equivalently toroidal) chessboard.
%C A229031 The Kneser graph construction of the Petersen graph relates this to the number of closed walks on the Petersen graph.
%C A229031 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)).
%C A229031 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.
%H A229031 Indranil Ghosh, <a href="/A229031/b229031.txt">Table of n, a(n) for n = 2..1000</a>
%H A229031 Wolfram MathWorld, <a href="https://mathworld.wolfram.com/GraphStrongProduct.html">Graph Strong Product</a>
%H A229031 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,20,-48).
%F A229031 a(n) = 6^n + 4*(-4)^n + 5*2^n.
%F A229031 a(n) = 10 * 2^n * A091000(n).
%F A229031 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
%e A229031 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}.
%e A229031 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.
%t A229031 Table[2^n(3^n+4(-2)^n+5),{n,2,25}]
%t A229031 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 *)
%o A229031 (PARI) a(n) = (2^n) * (3^n + 4*(-2)^n + 5) \\ _Indranil Ghosh_, Mar 03 2017
%o A229031 (Python) def A229031(n) : return (2**n) * (3**n + 4*(-2)**n +5) # _Indranil Ghosh_, Mar 03 2017
%K A229031 nonn,easy
%O A229031 2,1
%A A229031 _Adam P. Goucher_, Sep 11 2013