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

2, 24, 720, 13824, 383000, 14804640, 764340024, 50913153536, 4256161751448, 436618291524000, 53955264479804600, 7908071556041000064, 1356709951589099693976, 269380212536429979520928, 61297096735652845698099000, 15847986814197933588682229760

Offset

1,1

Comments

This graph is isomorphic to the circulant graph on 2n vertices where u,v are adjacent iff |u-v|=2 or |u-v| 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)+(k-1)!*b(n,k-1)) where b(n,0)=0, b(n,k)=Sum_{ j=1..n-k+1 } j*A130130(j)*A266213(k-1,n-j-k+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