login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A129348 Number of (directed) Hamiltonian circuits in the cocktail party graph of order n. 4

%I

%S 0,2,32,1488,112512,12771840,2036229120,434469611520,119619533537280,

%T 41303040523960320,17481826772405452800,8902337068174698086400,

%U 5370014079716477003366400,3786918976243761421064601600,3087031512410698159166482022400,2880726660365605475506018320384000

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

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

%C The cocktail party graph may also be called the n-octohedron, n-orthoplex or n dimensional cross polytope. - _Andrew Howroyd_, May 14 2017

%H Max Alekseyev, <a href="/A129348/b129348.txt">Table of n, a(n) for n = 1..100</a>

%H Marko R. Riedel, Math.Stackexchange.com <a href="http://math.stackexchange.com/questions/1913728/">Proof of asymptotic (saddle point method) and closed form (inclusion-exclusion)</a>

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>

%F 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

%F 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

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

%F For n>=2, a(n) = (-1 + 2 n)! Hypergeometric1F1[-n, 1 - 2 n, -2]. - _Eric W. Weisstein_, Mar 29 2014

%F a(n) = A003435(n) / (2*n) = A003436(n) * (n-1)! * 2^(n-1). - _Andrew Howroyd_, May 14 2017

%p a:= proc(n) option remember; `if`(n<3, n*(n-1),

%p ((136*n^3-608*n^2+762*n-470) *a(n-1)

%p +4*(n-2)*(14*n^2+29*n-193) *a(n-2)

%p -80*(n-2)*(n-3)*(n-4) *a(n-3)) /(34*n-101))

%p end:

%p seq(a(n), n=0..20); # _Alois P. Heinz_, Feb 09 2014

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

%t Table[Piecewise[{{(-1 + 2 n)! Hypergeometric1F1[-n, 1 - 2 n, -2],

%t n > 1}}], {n, 16}] (* _Eric W. Weisstein_, Mar 29 2014 *)

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

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

%K nonn

%O 1,2

%A _Eric W. Weisstein_, Apr 10 2007

%E Terms a(6) onward from _Max Alekseyev_, Nov 10 2007

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 17:05 EST 2019. Contains 319335 sequences. (Running on oeis4.)