cp's OEIS Frontend

A003436 Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.

%I A003436 M3638 #107 Aug 01 2024 10:54:17
%S A003436 1,0,1,4,31,293,3326,44189,673471,11588884,222304897,4704612119,
%T A003436 108897613826,2737023412199,74236203425281,2161288643251828,
%U A003436 67228358271588991,2225173863019549229,78087247031912850686,2896042595237791161749,113184512236563589997407
%N A003436 Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.
%C A003436 Also called the relaxed ménage problem (cf. A000179).
%C A003436 a(n) can be seen as a subset of the unordered pairings of the first 2n integers (A001147) with forbidden pairs (1,2n) and (i,i+1) for all i in [1,2n-1] (all adjacent integers modulo 2n). The linear version of this constraint is A000806. - _Olivier Gérard_, Feb 08 2011
%C A003436 Number of perfect matchings in the complement of C_{2n} where C_{2n} is the cycle graph on 2n vertices. - _Andrew Howroyd_, Mar 15 2016
%C A003436 Also the number of 2-uniform set partitions of {1...2n} containing no two cyclically successive vertices in the same block. - _Gus Wiseman_, Feb 27 2019
%D A003436 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003436 Vincenzo Librandi, <a href="/A003436/b003436.txt">Table of n, a(n) for n = 0..200</a>
%H A003436 F. R. Bernhart & N. J. A. Sloane, <a href="/A006343/a006343.pdf">Emails, April-May 1994</a>
%H A003436 Kenneth P. Bogart and Peter G. Doyle, <a href="https://math.dartmouth.edu/~doyle/docs/menage/menage/menage.html">Nonsexist solution of the menage problem</a>, Amer. Math. Monthly 93:7 (1986), 514-519.
%H A003436 Robert Cori and G. Hetyei, <a href="https://arxiv.org/abs/1710.09992">Counting partitions of a fixed genus</a>, arXiv preprint arXiv:1710.09992 [math.CO], 2017.
%H A003436 M. Hazewinkel and V. V. Kalashnikov, <a href="http://oai.cwi.nl/oai/asset/4970/04970D.pdf">Counting Interlacing Pairs on the Circle</a>, CWI report AM-R9508 (1995)
%H A003436 Evgeniy Krasko, Igor Labutin, and Alexander Omelchenko, <a href="https://arxiv.org/abs/1709.03218">Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete k-partite Graphs</a>, arXiv:1709.03218 [math.CO], 2017.
%H A003436 E. Krasko and 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 A003436 E. Krasko and 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 A003436 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 A003436 Gus Wiseman, <a href="/A003436/a003436.png">The a(5) = 293 interlacing chord diagrams</a>.
%F A003436 a(n) = A003435(n)/(n!*2^n).
%F A003436 a(n) = 2*n*a(n-1)-2*(n-3)*a(n-2)-a(n-3) for n>4. [Corrected by Vasu Tewari, Apr 11 2010, and by _R. J. Mathar_, Oct 02 2013]
%F A003436 G.f.: x + ((1-x)/(1+x)) * Sum_{n>=0} A001147(n)*(x/(1+x)^2)^n. - _Vladeta Jovovic_, Jun 27 2007
%F A003436 a(n) ~ 2^(n+1/2)*n^n/exp(n+1). - _Vaclav Kotesovec_, Aug 13 2013
%F A003436 a(n) = (-1)^n*2*hypergeom([n, -n], [], 1/2) for n >= 2. - _Peter Luschny_, Nov 10 2016
%p A003436 A003436 := proc(n) local k;
%p A003436       if n = 0 then 1
%p A003436     elif n = 1 then 0
%p A003436     else add( (-1)^k*binomial(n,k)*2*n/(2*n-k)*2^k*(2*n-k)!/2^n/n!,k=0..n) ;
%p A003436     end if;
%p A003436 end proc: # _R. J. Mathar_, Dec 11 2013
%p A003436 A003436 := n-> `if`(n<2, 1-n, (-1)^n*2*hypergeom([n, -n], [], 1/2)):
%p A003436 seq(simplify(A003436(n)), n=0..18); # _Peter Luschny_, Nov 10 2016
%t A003436 a[n_] := (2*n-1)!! * Hypergeometric1F1[-n, 1-2*n, -2]; a[1] = 0;
%t A003436 Table[a[n], {n, 0, 19}] (* _Jean-François Alcover_, Apr 05 2013 *)
%t A003436 twounifll[{}]:={{}};twounifll[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@twounifll[Complement[set,s]]]/@Table[{i,j},{j,If[i==1,Select[set,2<#<Last[set]&],Select[set,#>i+1&]]}];
%t A003436 Table[Length[twounifll[Range[n]]],{n,0,14,2}] (* _Gus Wiseman_, Feb 27 2019 *)
%Y A003436 Cf. A003435, A129348. A003437 gives unlabeled case.
%Y A003436 First differences of A000806.
%Y A003436 Column k=2 of A324428.
%Y A003436 Cf. A000179, A000296, A000699, A001147, A005493, A170941, A190823, A278990, A306386, A306419, A322402, A324011, A324172, A324173.
%K A003436 nonn,easy,nice
%O A003436 0,4
%A A003436 _N. J. A. Sloane_
%E A003436 a(0)=1 prepended by _Gus Wiseman_, Feb 27 2019