

A137891


Number of (directed) Hamiltonian paths in the graph join C_n + C_n of two cycles.


4



2, 24, 720, 13824, 383000, 14804640, 764340024, 50913153536, 4256161751448, 436618291524000, 53955264479804600, 7908071556041000064, 1356709951589099693976, 269380212536429979520928, 61297096735652845698099000, 15847986814197933588682229760
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

This graph is isomorphic to the circulant graph on 2n vertices where u,v are adjacent iff uv=2 or uv is odd. This sequence should not be confused with A268838, the number of Hamiltonian paths in C_n X C_n. The sequence can be computed through an analysis of the partitions of n. (See attached C# code for details).  Andrew Howroyd, Feb 14 2016


LINKS

Andrew Howroyd and Vaclav Kotesovec, Table of n, a(n) for n = 1..200 (terms 1..50 from Andrew Howroyd)
Andrew Howroyd, C# software related to this sequence
Eric Weisstein's World of Mathematics, Graph Join
Eric Weisstein's World of Mathematics, Hamiltonian Path
Index entries for sequences related to graphs, Hamiltonian


FORMULA

a(n) = Sum_ { k=1..n } 2*k!*b(n,k)*(k!*b(n,k)+(k1)!*b(n,k1)) where b(n,0)=0, b(n,k)=Sum_{ j=1..nk+1 } j*A130130(j)*A266213(k1,njk+1) for k>0, n<>2.  Andrew Howroyd, Feb 14 2016
a(n) ~ c * n!^2, where c = A270047 = 42.12277421168156081166292550105956... .  Vaclav Kotesovec, Mar 08 2016


MATHEMATICA

b[n_, k_] := If[k == 0, 0, Sum[j*Min[2, j] * Sum[ Binomial[n  j  k, kk  1]*Binomial[k  1, kk]*2^kk, {kk, 0, Min[k  1, n  j  k + 1]}], {j, 1, n  k + 1}]];
Flatten[{{2, 24}, Table[Sum[2*k!*b[n, k]*(k!*b[n, k] + (k  1)!*b[n, k  1]), {k, 1, n}], {n, 3, 20}]}] (* Vaclav Kotesovec, Mar 08 2016, after Andrew Howroyd *)


CROSSREFS

Cf. A268838 (number of directed Hamiltonian paths in the torus grid graph C_n X C_n).
Cf. A270047.
Sequence in context: A279331 A354378 A119699 * A188959 A093459 A279236
Adjacent sequences: A137888 A137889 A137890 * A137892 A137893 A137894


KEYWORD

nonn


AUTHOR

Eric W. Weisstein, Feb 20 2008


EXTENSIONS

a(6)a(7) from Eric W. Weisstein, Dec 16 2013
a(8)a(10) from Eric W. Weisstein, Dec 24 2013
a(1)=2 and a(2)=24 inserted by Andrew Howroyd, Feb 14 2016
a(11)a(16) from Andrew Howroyd, Feb 14 2016


STATUS

approved



