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
Keywords
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
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
Extensions
Terms a(6) onward from Max Alekseyev, Nov 10 2007
Comments