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

8, 192, 11904, 1125120, 153262080, 28507207680, 6951513784320, 2153151603671040, 826060810479206400, 384600188992919961600, 213656089636192754073600, 139620366072628402087526400, 106033731334825319789808844800

Offset

2,1

Comments

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

These are labeled and the order and starting point matter.

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

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

D. Singmaster, Enumerating unlabeled Hamiltonian circuts, Preprint (1974).

D. Singmaster, Hamiltonian circuits on the n-dimensional octahedron, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 1-4.

D. Singmaster, Letter to N. J. A. Sloane, May 1975

Eric Weisstein's World of Mathematics, Cocktail Party Graph

Formula

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

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

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

a(n) ~ sqrt(Pi) * 2^(2*n+1) * n^(2*n+1/2) / exp(2*n+1). - Vaclav Kotesovec, Feb 12 2014

a(n) = -(-2)^(n+1)*n!*hypergeom([n, -n], [], 1/2). - Peter Luschny, Nov 10 2016

Example

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.

Maple

A003435 := n->add((-1)^k*binomial(n, k)*((2*n)/(2*n-k))*2^k*(2*n-k)!, k=0..n);

Mathematica

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

Prog

(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
(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
(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

Crossrefs

Cf. A003436, A003437, A129348.

Sequence in context: A268095 A058873 A052734 * A071303 A128406 A265269

Adjacent sequences: A003432 A003433 A003434 * A003436 A003437 A003438

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

Name made more precise by Andrew Howroyd, May 14 2017

Status

approved