cp's OEIS Frontend

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

%I A003435 M4578 #56 Feb 16 2025 08:32:27
%S A003435 8,192,11904,1125120,153262080,28507207680,6951513784320,
%T A003435 2153151603671040,826060810479206400,384600188992919961600,
%U A003435 213656089636192754073600,139620366072628402087526400,106033731334825319789808844800
%N A003435 Number of directed Hamiltonian circuits on n-octahedron with a marked starting node.
%C A003435 Also called the relaxed menage problem (cf. A000179).
%C A003435 These are labeled and the order and starting point matter.
%D A003435 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003435 Vincenzo Librandi, <a href="/A003435/b003435.txt">Table of n, a(n) for n = 2..100</a>
%H A003435 Kenneth P. Bogart and Peter G. Doyle, <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 A003435 D. Singmaster, <a href="/A003435/a003435_1.pdf">Enumerating unlabeled Hamiltonian circuts</a>, Preprint (1974).
%H A003435 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 A003435 D. Singmaster, <a href="/A003435/a003435.pdf">Letter to N. J. A. Sloane, May 1975</a>
%H A003435 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CocktailPartyGraph.html">Cocktail Party Graph</a>
%F A003435 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 A003435 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 A003435 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 A003435 a(n) ~ sqrt(Pi) * 2^(2*n+1) * n^(2*n+1/2) / exp(2*n+1). - _Vaclav Kotesovec_, Feb 12 2014
%F A003435 a(n) = -(-2)^(n+1)*n!*hypergeom([n, -n], [], 1/2). - _Peter Luschny_, Nov 10 2016
%e A003435 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.
%p A003435 A003435 := n->add((-1)^k*binomial(n,k)*((2*n)/(2*n-k))*2^k*(2*n-k)!,k=0..n);
%t A003435 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 A003435 (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
%o A003435 (Magma) [(&+[ (-1)^k*2^(k+1)*n*Binomial(n, k)*Factorial(2*n-k-1): k in [0..n]]) : n in [2..20]]; // _G. C. Greubel_, Nov 17 2022
%o A003435 (SageMath) [sum( (-1)^k*2^(k+1)*n*binomial(n, k)*factorial(2*n-k-1) for k in (0..n)) for n in (2..20)] # _G. C. Greubel_, Nov 17 2022
%Y A003435 Cf. A003436, A003437, A129348.
%K A003435 nonn,nice,easy
%O A003435 2,1
%A A003435 _N. J. A. Sloane_
%E A003435 Name made more precise by _Andrew Howroyd_, May 14 2017