cp's OEIS Frontend

A384294 The number of Hamiltonian cycles in the concentric ring graph of order n.

%I A384294 #24 May 27 2025 01:14:13
%S A384294 6,12,30,34,56,108,150,244,418,642,1040,1712,2726,4412,7174,11554,
%T A384294 18696,30292,48950,79204,128202,207362,335520,542936,878406,1421292,
%U A384294 2299758,3720994,6020696,9741756,15762390,25504084,41266546,66770562,108037040,174807680,282844646,457652252,740496982,1198149154,1938646056
%N A384294 The number of Hamiltonian cycles in the concentric ring graph of order n.
%C A384294 The concentric ring graph of order n is a cubic graph with 4n vertices and 6n edges. If we name the vertices a_j,b_j,c_j,d_j for 0<=j<n, the edges are a_j--a_j', a_j--b_j, b_j--c_j, c_j--b_j', c_j--d_j, and d_j--d_j', where j'=(j+1)mod n.
%C A384294 When n=5 it is isomorphic to the graph of the dodecahedron, which Hamilton used when he first considered "Hamiltonian cycles".
%D A384294 Donald E. Knuth, Prefascicle 8a of The Art of Computer Programming (planned to become part of Volume 4C).
%H A384294 Don Knuth, <a href="/A384294/b384294.txt">Table of n, a(n) for n = 3..100</a>
%H A384294 <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,2,-2,-2,-1,1,1).
%F A384294 a(n) = 2*Lucas(n) - 2 + 2*n*[Mod(n,3)==2], where [ ] denotes the Iverson bracket.
%F A384294 G.f.: -2*x^3*(3+3*x+6*x^2-10*x^3-10*x^4-3*x^5+4*x^6+4*x^7) / ( (x^2+x-1)*(x-1)^2*(1+x+x^2)^2 ). - _R. J. Mathar_, May 26 2025
%e A384294 The a[3]=6 cycles when n=3 are:
%e A384294   a0--a1--a2--b2--c1--b1--c0--d0--d1--d2--c2--b0--a0,
%e A384294   a0--a1--a2--b2--c2--d2--d0--d1--c1--b1--c0--b0--a0,
%e A384294   a0--a1--b1--c0--b0--c2--d2--d0--d1--c1--b2--a2--a0,
%e A384294   a0--a1--b1--c1--d1--d2--d0--c0--b0--c2--b2--a2--a0,
%e A384294   a0--b0--c0--d0--d1--d2--c2--b2--c1--b1--a1--a2--a0,
%e A384294   a0--b0--c2--b2--c1--d1--d2--d0--c0--b1--a1--a2--a0.
%t A384294 a[n_]:=2LucasL[n]-2+If[Mod[n, 3]==2, 2n, 0]; Array[a,41,3]
%Y A384294 Cf. A000032 (Lucas numbers).
%K A384294 nonn,easy
%O A384294 3,1
%A A384294 _Don Knuth_, May 24 2025