A129348 Number of (directed) Hamiltonian circuits in the cocktail party graph of order n.

0, 2, 32, 1488, 112512, 12771840, 2036229120, 434469611520, 119619533537280, 41303040523960320, 17481826772405452800, 8902337068174698086400, 5370014079716477003366400, 3786918976243761421064601600, 3087031512410698159166482022400, 2880726660365605475506018320384000

Offset

1,2

Comments

Also, the number of ways (up to rotations) to seat n married couples at a circular table with no spouses next to each other. Cf. A007060, A193639. - Geoffrey Critzer, Feb 09 2014

The cocktail party graph may also be called the n-octahedron, n-orthoplex or n-dimensional cross polytope. - Andrew Howroyd, May 14 2017

Links

Max Alekseyev, Table of n, a(n) for n = 1..100

Marko R. Riedel, Math.Stackexchange.com Proof of asymptotic (saddle point method) and closed form (inclusion-exclusion)

Eric Weisstein's World of Mathematics, Cocktail Party Graph

Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Formula

For n>=2, a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)*(2*n-1-k)!*2^k. - Geoffrey Critzer, Feb 09 2014

Recurrence (for n>=4): (2*n-3)*a(n) = 2*(n-1)*(4*n^2 - 8*n + 5)*a(n-1) + 4*(n-2)*(n-1)*(2*n-1)*a(n-2). - Vaclav Kotesovec, Feb 09 2014

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

For n>=2, a(n) = (-1 + 2 n)! Hypergeometric1F1[-n, 1 - 2 n, -2]. - Eric W. Weisstein, Mar 29 2014

a(n) = A003435(n) / (2*n) = A003436(n) * (n-1)! * 2^(n-1). - Andrew Howroyd, May 14 2017

Maple

a:= proc(n) option remember; `if`(n<3, n*(n-1),
     ((136*n^3-608*n^2+762*n-470) *a(n-1)
       +4*(n-2)*(14*n^2+29*n-193) *a(n-2)
       -80*(n-2)*(n-3)*(n-4) *a(n-3)) /(34*n-101))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Feb 09 2014

Mathematica

Prepend[Table[Sum[(-1)^i Binomial[n, i] (2n - 1 - i)! 2^i, {i, 0, n}], {n, 2, 16}], 0] (* Geoffrey Critzer, Feb 09 2014 *)
Table[Piecewise[{{(-1 + 2 n)! Hypergeometric1F1[-n, 1 - 2 n, -2],
    n > 1}}], {n, 16}] (* Eric W. Weisstein, Mar 29 2014 *)

Prog

(PARI) { A129348(n) = sum(m=0, n-1, sum(k=1, n-m, (-1)^k * binomial(n-1, m) * binomial(n-m-1, k-1) * 2^(k-1) * ([0, k-1, 2*(n-m-k); 1, k-2, 2*(n-m-k); 1, k-1, 2*(n-m-k-1)]^(2*n))[1, 1] ) + sum(k=0, n-m, (-1)^k * binomial(n-1, m) * binomial(n-m-1, k) * 2^(k-1) * ([0, k, 2*(n-m-k-1); 2, k-1, 2*(n-m-k-1); 2, k, 2*(n-m-k-2)]^(2*n))[1, 1] ) ) } \\ Max Alekseyev, Dec 22 2013

Crossrefs

Cf. A003435, A003436, A003437, A007060, A167987.

Sequence in context: A012209 A295418 A172286 * A280211 A087084 A193269

Adjacent sequences: A129345 A129346 A129347 * A129349 A129350 A129351

Keyword

nonn

Author

Eric W. Weisstein, Apr 10 2007

Extensions

Terms a(6) onward from Max Alekseyev, Nov 10 2007

Status

approved