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

1, 0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897, 4704612119, 108897613826, 2737023412199, 74236203425281, 2161288643251828, 67228358271588991, 2225173863019549229, 78087247031912850686, 2896042595237791161749, 113184512236563589997407

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Also called the relaxed ménage problem (cf. A000179).

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

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

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

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
• Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93:7 (1986), 514-519.
• Robert Cori and G. Hetyei, Counting partitions of a fixed genus, arXiv preprint arXiv:1710.09992 [math.CO], 2017.
• M. Hazewinkel and V. V. Kalashnikov, Counting Interlacing Pairs on the Circle, CWI report AM-R9508 (1995)
• Evgeniy Krasko, Igor Labutin, and Alexander Omelchenko, Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete k-partite Graphs, arXiv:1709.03218 [math.CO], 2017.
• E. Krasko and A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, arXiv preprint arXiv:1601.05073 [math.CO], 2016.
• E. Krasko and 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.
• Gus Wiseman, The a(5) = 293 interlacing chord diagrams.

Crossrefs

Cf. A003435, A129348. A003437 gives unlabeled case.

First differences of A000806.

Column k=2 of A324428.

Cf. A000179, A000296, A000699, A001147, A005493, A170941, A190823, A278990, A306386, A306419, A322402, A324011, A324172, A324173.

Programs

Maple

A003436 := proc(n) local k;
      if n = 0 then 1
    elif n = 1 then 0
    else add( (-1)^k*binomial(n,k)*2*n/(2*n-k)*2^k*(2*n-k)!/2^n/n!,k=0..n) ;
    end if;
end proc: # R. J. Mathar, Dec 11 2013
A003436 := n-> `if`(n<2, 1-n, (-1)^n*2*hypergeom([n, -n], [], 1/2)):
seq(simplify(A003436(n)), n=0..18); # Peter Luschny, Nov 10 2016

Mathematica

a[n_] := (2*n-1)!! * Hypergeometric1F1[-n, 1-2*n, -2]; a[1] = 0;
Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Apr 05 2013 *)
twounifll[{}]:={{}};twounifll[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@twounifll[Complement[set,s]]]/@Table[{i,j},{j,If[i==1,Select[set,2<#i+1&]]}];
Table[Length[twounifll[Range[n]]],{n,0,14,2}] (* Gus Wiseman, Feb 27 2019 *)

Formula

a(n) = A003435(n)/(n!*2^n).

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]

G.f.: x + ((1-x)/(1+x)) * Sum_{n>=0} A001147(n)*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 27 2007

a(n) ~ 2^(n+1/2)*n^n/exp(n+1). - Vaclav Kotesovec, Aug 13 2013

a(n) = (-1)^n*2*hypergeom([n, -n], [], 1/2) for n >= 2. - Peter Luschny, Nov 10 2016

Extensions

a(0)=1 prepended by Gus Wiseman, Feb 27 2019