login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(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)
10
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)
OFFSET

1,3

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

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 = 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.

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

MAPLE

A003436 := proc(n)

    if 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=0, 0, -2*(-1)^n*hypergeom([n+1, -n-1], [], 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, 1, 19}] (* Jean-François Alcover, Apr 05 2013 *)

CROSSREFS

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

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 01:09 EST 2018. Contains 317279 sequences. (Running on oeis4.)