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

Author

Eric W. Weisstein, Apr 10 2007

Keywords

• nonn

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

Crossrefs

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

Programs

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

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

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

Extensions

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