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

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

Offset

0,4

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.

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

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<#<Last[set]&], Select[set, #>i+1&]]}];
Table[Length[twounifll[Range[n]]], {n, 0, 14, 2}] (* Gus Wiseman, Feb 27 2019 *)

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.

Sequence in context: A261053 A192407 A000858 * A307504 A371362 A276316

Adjacent sequences: A003433 A003434 A003435 * A003437 A003438 A003439

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

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

Status

approved