This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003436 Number of inequivalent labeled Hamiltonian circuits on n-octahedron. Interlacing chords joining 2n points on circle.
(Formerly M3638)
0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897, 4704612119, 108897613826, 2737023412199, 74236203425281, 2161288643251828, 67228358271588991, 2225173863019549229, 78087247031912850686, 2896042595237791161749 (list; graph; refs; listen; history; text; internal format)



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


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


Vincenzo Librandi, Table of n, a(n) for n = 1..200

F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994

Bogart, Kenneth P. and Doyle, Peter G., Nonsexist solution of the menage problem, Amer. Math. Monthly 93:7 (1986), 514-519.

Robert Cori, 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, Alexander Omelchenko, Enumeration of Labelled and Unlabelled Hamiltonian Cycles in Complete k-partite Graphs, arXiv:1709.03218 [math.CO], 2017.

E. Krasko, A. Omelchenko, Enumeration of Chord Diagrams without Loops and Parallel Chords, arXiv preprint arXiv:1601.05073 [math.CO], 2016.

E. Krasko, 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.


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+1)*2*hypergeom([n+1, -n-1], [], 1/2)) for n>=1. - Peter Luschny, Nov 10 2016


A003436 := proc(n)

    if n = 1 then



        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=0, 0, -2*(-1)^n*hypergeom([n+1, -n-1], [], 1/2)):

seq(simplify(A003436(n)), n=0..18); # Peter Luschny, Nov 10 2016


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 *)


Cf. A003435, A129348. A003437 gives unlabeled case.

First differences of A000806.

Sequence in context: A261053 A192407 A000858 * A276316 A199683 A114475

Adjacent sequences:  A003433 A003434 A003435 * A003437 A003438 A003439




N. J. A. Sloane



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 10:53 EST 2019. Contains 319271 sequences. (Running on oeis4.)