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

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

Offset

3,1

Links

Vaclav Kotesovec, Table of n, a(n) for n = 3..200 (terms 3..50 from Andrew Howroyd)

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

Prog

(PARI) B(n)=polcoef(1/(1 - x*y*(2/(1 - x) - 1)) + O(x*x^n), n)
a(n)={my(v=Vecrev(B(n))); 2*n^2*sum(k=1, n, my(t=v[1+k]*(k-1)!); t*(t + if(k>1, v[k]*(k-2)!)))} \\ Andrew Howroyd, Jan 10 2025

Crossrefs

Cf. A130130, A234628, A266213, A270047.

Sequence in context: A052783 A112002 A004033 * A056271 A000920 A052779

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 prepended by Andrew Howroyd, Feb 14 2016

a(11)-a(16) from Andrew Howroyd, Feb 14 2016

a(1)-a(2) removed by Andrew Howroyd, Jan 10 2025

Status

approved