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

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

Offset

1,3

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.

Formula

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

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

Prog

(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

Crossrefs

See A003436 for labeled case.

See also A278990, A007474.

Sequence in context: A185310 A143883 A346427 * A192410 A270518 A359950

Adjacent sequences: A003434 A003435 A003436 * A003438 A003439 A003440

Keyword

nonn,nice

Author

N. J. A. Sloane

Status

approved