|
%I M3638 #96 Feb 27 2019 17:48:43
%S 1,0,1,4,31,293,3326,44189,673471,11588884,222304897,4704612119,
%T 108897613826,2737023412199,74236203425281,2161288643251828,
%U 67228358271588991,2225173863019549229,78087247031912850686,2896042595237791161749,113184512236563589997407
%N Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.
%C Also called the relaxed ménage problem (cf. A000179).
%C 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 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 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A003436/b003436.txt">Table of n, a(n) for n = 0..200</a>
%H F. R. Bernhart & N. J. A. Sloane, <a href="/A006343/a006343.pdf">Emails, April-May 1994</a>
%H Bogart, Kenneth P. and Doyle, Peter G., <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 Robert Cori, 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 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 Evgeniy Krasko, Igor Labutin, 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 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 Gus Wiseman, <a href="/A003436/a003436.png">The a(5) = 293 interlacing chord diagrams</a>.
%F a(n) = A003435(n)/(n!*2^n).
%F 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 G.f.: x+(1-x)/(1+x)* Sum_{n>=0} A001147(n)*(x/(1+x)^2)^n. - _Vladeta Jovovic_, Jun 27 2007
%F a(n) ~ 2^(n+1/2)*n^n/exp(n+1). - _Vaclav Kotesovec_, Aug 13 2013
%F a(n) = (-1)^(n+1)*2*hypergeom([n+1, -n-1], [], 1/2)) for n>=1. - _Peter Luschny_, Nov 10 2016
%p A003436 := proc(n)
%p if n = 1 then
%p 0;
%p else
%p add( (-1)^k*binomial(n,k)*2*n/(2*n-k)*2^k*(2*n-k)!/2^n/n!,k=0..n) ;
%p end if;
%p end proc: # _R. J. Mathar_, Dec 11 2013
%p A003436 := n-> `if`(n=0,0,-2*(-1)^n*hypergeom([n+1, -n-1], [], 1/2)):
%p seq(simplify(A003436(n)),n=0..18); # _Peter Luschny_, Nov 10 2016
%t a[n_] := (2*n-1)!! * Hypergeometric1F1[-n, 1-2*n, -2]; a[1] = 0; Table[a[n], {n, 1, 19}] (* _Jean-François Alcover_, Apr 05 2013 *)
%t 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 Table[Length[twounifll[Range[n]]],{n,0,14,2}] (* _Gus Wiseman_, Feb 27 2019 *)
%Y Cf. A003435, A129348. A003437 gives unlabeled case.
%Y First differences of A000806.
%Y Column k=2 of A324428.
%Y Cf. A000179, A000296, A000699, A001147, A005493, A170941, A190823, A278990, A306386, A306419, A322402, A324011, A324172, A324173.
%K nonn,easy,nice
%O 0,4
%A _N. J. A. Sloane_
%E a(0)=1 prepended by _Gus Wiseman_, Feb 27 2019
|
