This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003435 Number of directed Hamiltonian circuits on n-octahedron with a marked starting node. (Formerly M4578) 3

%I M4578

%S 8,192,11904,1125120,153262080,28507207680,6951513784320,

%T 2153151603671040,826060810479206400,384600188992919961600,

%U 213656089636192754073600,139620366072628402087526400,106033731334825319789808844800

%N Number of directed Hamiltonian circuits on n-octahedron with a marked starting node.

%C Also called the relaxed menage problem (cf. A000179).

%C These are labeled and the order and starting point matter.

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

%H Vincenzo Librandi, <a href="/A003435/b003435.txt">Table of n, a(n) for n = 2..100</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 (1986), no. 7, 514-519.

%H D. Singmaster, <a href="/A003435/a003435_1.pdf">Enumerating unlabeled Hamiltonian circuts</a>, Preprint (1974).

%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 D. Singmaster, <a href="/A003435/a003435.pdf">Letter to N. J. A. Sloane, May 1975</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CocktailPartyGraph.html">Cocktail Party Graph</a>

%F For n >= 2, a(n) = Sum_{k=0..n}(-1)^k*binomial(n, k)*((2*n)/(2*n-k))*2^k*(2*n-k)!.

%F Conjecture: a(n) +(-4*n^2 + 2*n - 5)*a(n-1) + 2*(n-1)*(4*n-17)*a(n-2) + 12*(n-1)*(n-2)*a(n-3) = 0. - _R. J. Mathar_, Oct 02 2013

%F Recurrence: (2*n-3)*a(n) = 2*n*(4*n^2 - 8*n + 5)*a(n-1) + 4*(n-1)*n*(2*n-1)*a(n-2). - _Vaclav Kotesovec_, Feb 12 2014

%F a(n) ~ sqrt(Pi) * 2^(2*n+1) * n^(2*n+1/2) / exp(2*n+1). - _Vaclav Kotesovec_, Feb 12 2014

%F a(n) = -(-2)^(n+1)*n!*hypergeom([n, -n], [], 1/2). - _Peter Luschny_, Nov 10 2016

%e n=2: label vertices of a square 1,2,3,4. Then the 8 Hamiltonian circuits are 1234, 1432, 2341, 2143, 3412, 3214, 4123, 4321; so a(2) = 8.

%t a[n_] := 2^n*n!*(2n-1)!!*Hypergeometric1F1[-n, 1-2n, -2]; Table[ a[n], {n, 2, 14}] (* _Jean-François Alcover_, Nov 04 2011 *)

%o (PARI) a(n)=sum(k=0,n,(-1)^k*binomial(n,k)*((2*n)/(2*n-k))*2^k*(2*n-k)!) \\ _Charles R Greathouse IV_, Nov 04 2011

%Y Cf. A003436, A003437, A129348.

%K nonn,nice,easy

%O 2,1

%A _N. J. A. Sloane_

%E Name made more precise by _Andrew Howroyd_, May 14 2017

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.