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

6, 12, 30, 34, 56, 108, 150, 244, 418, 642, 1040, 1712, 2726, 4412, 7174, 11554, 18696, 30292, 48950, 79204, 128202, 207362, 335520, 542936, 878406, 1421292, 2299758, 3720994, 6020696, 9741756, 15762390, 25504084, 41266546, 66770562, 108037040, 174807680, 282844646, 457652252, 740496982, 1198149154, 1938646056

Offset: 3

Author

Don Knuth, May 24 2025

Keywords

• nonn
• easy

Comments

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

When n=5 it is isomorphic to the graph of the dodecahedron, which Hamilton used when he first considered "Hamiltonian cycles".

Examples

			The a[3]=6 cycles when n=3 are:
  a0--a1--a2--b2--c1--b1--c0--d0--d1--d2--c2--b0--a0,
  a0--a1--a2--b2--c2--d2--d0--d1--c1--b1--c0--b0--a0,
  a0--a1--b1--c0--b0--c2--d2--d0--d1--c1--b2--a2--a0,
  a0--a1--b1--c1--d1--d2--d0--c0--b0--c2--b2--a2--a0,
  a0--b0--c0--d0--d1--d2--c2--b2--c1--b1--a1--a2--a0,
  a0--b0--c2--b2--c1--d1--d2--d0--c0--b1--a1--a2--a0.
		

References

• Donald E. Knuth, Prefascicle 8a of The Art of Computer Programming (planned to become part of Volume 4C).

Links

• Don Knuth, Table of n, a(n) for n = 3..100
• Index entries for linear recurrences with constant coefficients, signature (1,1,2,-2,-2,-1,1,1).

Crossrefs

Cf. A000032 (Lucas numbers).

Programs

Mathematica

a[n_]:=2LucasL[n]-2+If[Mod[n, 3]==2, 2n, 0]; Array[a,41,3]

Formula

a(n) = 2*Lucas(n) - 2 + 2*n*[Mod(n,3)==2], where [ ] denotes the Iverson bracket.

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.