A003437 Number of unlabeled Hamiltonian circuits on n-octahedron (cross polytope); also number of circular chord diagrams with n chords, modulo symmetries.

0, 1, 2, 7, 29, 196, 1788, 21994, 326115, 5578431, 107026037, 2269254616, 52638064494, 1325663757897, 36021577975918, 1050443713185782, 32723148860301935, 1084545122297249077, 38105823782987999742, 1414806404051118314077

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Gheorghe Coserea, Table of n, a(n) for n = 1..300
• Kristin DeSplinter, Satyan L. Devadoss, Jordan Readyhough, and Bryce Wimberly, Unfolding cubes: nets, packings, partitions, chords, arXiv:2007.13266 [math.CO], 2020.
• S. Jablan, R. Sazdanovic, Knots, Links, and Self-avoiding curves, Forma 22 (1) (2007) 5-13. In the denominator on page 8, n-k should read 2n-k.
• E. Krasko, A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, arXiv preprint arXiv:1601.05073 [math.CO], 2016.
• E. Krasko, A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, The Electronic Journal of Combinatorics, 24(3) (2017), #P3.43.
• D. Singmaster, Hamiltonian circuits on the n-dimensional octahedron, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.
• Evert Stenlund, On the Vassiliev Invariants, June 2017.

Crossrefs

See A003436 for labeled case.

See also A278990, A007474.

Programs

Mathematica

nn = 20; M = Array[0&, {2nn, 2nn}];
Mget[n_, k_] := Which[n < 0, 0, n==0, 1, n==1, 1-Mod[k, 2], n==2, k - Mod[k, 2], True, M[[n, k]]];
Mset[n_, k_, v_] := (M[[n, k]] = v);
Minit = Module[{tmp = 0}, For[n = 3, n <= 2nn, n++, For[k = 1, k <= 2nn, k++, tmp = If[OddQ[k], k(n-1) Mget[n-2, k] + Mget[n-4, k], Mget[n-1, k] + k(n-1) Mget[n-2, k] - Mget[n-3, k] + Mget[n-4, k]]; Mset[n, k, tmp]]]];
A007474[n_] := Sum[EulerPhi[d] (Mget[2n/d, d] - Mget[2n/d - 2, d]), {d, Divisors[2n]}]/(2n);
a[n_] := A007474[n]/2 + (Mget[n, 2] - Mget[n-1, 2] + Mget[n-2, 2])/4;
Array[a, nn] (* Jean-François Alcover, Aug 12 2018, after Gheorghe Coserea *)

PARI

N = 20; M = matrix(2*N, 2*N);
Mget(n,k) = { if (n<0, 0, n==0, 1, n==1, 1-(k%2), n==2, k-(k%2), M[n,k]) };
Mset(n,k,v) = { M[n,k] = v;};
Minit() = {
  my(tmp = 0);
  for (n=3, 2*N, for(k=1, 2*N,
    tmp = if (k%2, k*(n-1) * Mget(n-2, k) + Mget(n-4, k),
    Mget(n-1, k) + k*(n-1) * Mget(n-2, k) - Mget(n-3, k) + Mget(n-4, k));
    Mset(n, k, tmp)));
};
Minit();
A007474(n) = sumdiv(2*n, d, eulerphi(d) * (Mget(2*n/d, d) - Mget(2*n/d-2, d)))/(2*n);
a(n) = A007474(n)/2 + (Mget(n,2) - Mget(n-1,2) + Mget(n-2,2))/4;
vector(N, n, a(n))  \\ Gheorghe Coserea, Dec 10 2016

Formula

a(n) ~ 2^(n-3/2) * n^(n-1) / exp(n+1). - Vaclav Kotesovec, Dec 10 2016