A003437 - OEIS

%I M1781 #54 Jul 28 2020 11:17:46

%S 0,1,2,7,29,196,1788,21994,326115,5578431,107026037,2269254616,

%T 52638064494,1325663757897,36021577975918,1050443713185782,

%U 32723148860301935,1084545122297249077,38105823782987999742,1414806404051118314077

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

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

%H Gheorghe Coserea, <a href="/A003437/b003437.txt">Table of n, a(n) for n = 1..300</a>

%H Kristin DeSplinter, Satyan L. Devadoss, Jordan Readyhough, and Bryce Wimberly, <a href="https://arxiv.org/abs/2007.13266">Unfolding cubes: nets, packings, partitions, chords</a>, arXiv:2007.13266 [math.CO], 2020.

%H S. Jablan, R. Sazdanovic, <a href="http://www.scipress.org/journals/forma/abstract/2201/22010005.html">Knots, Links, and Self-avoiding curves</a>, Forma 22 (1) (2007) 5-13. In the denominator on page 8, n-k should read 2n-k.

%H E. Krasko, A. Omelchenko, <a href="http://arxiv.org/abs/1601.05073">Enumeration of Chord Diagrams without Loops and Parallel Chords</a>, arXiv preprint arXiv:1601.05073 [math.CO], 2016.

%H E. Krasko, A. Omelchenko, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p43">Enumeration of Chord Diagrams without Loops and Parallel Chords</a>, The Electronic Journal of Combinatorics, 24(3) (2017), #P3.43.

%H D. Singmaster, <a href="http://dx.doi.org/10.1016/0095-8956(75)90069-6">Hamiltonian circuits on the n-dimensional octahedron</a>, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.

%H Evert Stenlund, <a href="http://www.evertstenlund.se/knots/On%20the%20Vassiliev%20Invariant.pdf">On the Vassiliev Invariants</a>, June 2017.

%F a(n) ~ 2^(n-3/2) * n^(n-1) / exp(n+1). - _Vaclav Kotesovec_, Dec 10 2016

%t nn = 20; M = Array[0&, {2nn, 2nn}];

%t 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]]];

%t Mset[n_, k_, v_] := (M[[n, k]] = v);

%t 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]]]];

%t A007474[n_] := Sum[EulerPhi[d] (Mget[2n/d, d] - Mget[2n/d - 2, d]), {d, Divisors[2n]}]/(2n);

%t a[n_] := A007474[n]/2 + (Mget[n, 2] - Mget[n-1, 2] + Mget[n-2, 2])/4;

%t Array[a, nn] (* _Jean-François Alcover_, Aug 12 2018, after _Gheorghe Coserea_ *)

%o (PARI)

%o N = 20; M = matrix(2*N, 2*N);

%o Mget(n,k) = { if (n<0, 0, n==0, 1, n==1, 1-(k%2), n==2, k-(k%2), M[n,k]) };

%o Mset(n,k,v) = { M[n,k] = v;};

%o Minit() = {

%o   my(tmp = 0);

%o   for (n=3, 2*N, for(k=1, 2*N,

%o     tmp = if (k%2, k*(n-1) * Mget(n-2, k) + Mget(n-4, k),

%o     Mget(n-1, k) + k*(n-1) * Mget(n-2, k) - Mget(n-3, k) + Mget(n-4, k));

%o     Mset(n, k, tmp)));

%o };

%o Minit();

%o A007474(n) = sumdiv(2*n, d, eulerphi(d) * (Mget(2*n/d, d) - Mget(2*n/d-2, d)))/(2*n);

%o a(n) = A007474(n)/2 + (Mget(n,2) - Mget(n-1,2) + Mget(n-2,2))/4;

%o vector(N, n, a(n))  \\ _Gheorghe Coserea_, Dec 10 2016

%Y See A003436 for labeled case.

%Y See also A278990, A007474.

%K nonn,nice

%O 1,3

%A _N. J. A. Sloane_