A003437 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.