A378241 Numbers of directed Hamiltonian cycles in the complete 4-partite graph K_{n,n,n,n}.
6, 1488, 3667680, 37744330752, 1106491456512000, 74213488705904640000, 9872975878366503813120000, 2355966665497190945783808000000, 935825492908108988335792827924480000, 584053924678169568704863421815848960000000
Offset: 1
Keywords
Links
- P. Horak and L. Tovarek, On Hamiltonian cycles of complete n-partite graphs, Mathematica Slovaca, vol. 29 (1979), 43-47.
- Eric Weisstein's World of Mathematics, Complete k-Partite Graph.
- Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Programs
-
Mathematica
Table[Sum[Sum[Sum[Sum[ (2n - i - j - 1)! 2^(2i) 3^j (n!)^4/(j!) * (3n - 3i - 3j - 2d)!/((2i + j - n + d)! (n - j - d)! (2n - 3i - 2j - d)!) * (2n - 2i - 2j - 2e)!/(e! (d - e)! (2n - 2i - 2j - d - e)! (n - i - j - d + e)! ((n - i - j - e)!)^2), {e, Max[0, i + j - n + d], Min[d, 2n - 2i - 2j - d]}], {d, Max[0, n - j - 2i], Min[n - j, 2n - 3i - 2j]}], {i, 0, Floor[2(n - j)/3]}], {j, 0, n}], {n, 1, 10}] Table[(n!)^4 Expand[Hypergeometric1F1[1 - n, 2, x]^4 x^3] /. x^p_ :> p!, {n, 10}] (* Eric W. Weisstein, Feb 20 2025 *) -
Python
from math import factorial as fact def a(n): # Using formula found in Horak et al. return sum(sum(sum(sum( fact(2*n-i-j-1)*pow(2,2*i)*pow(3,j)*pow(fact(n),4)//fact(j) * fact(3*n-3*i-3*j-2*d)//(fact(2*i+j-n+d)*fact(n-j-d)*fact(2*n-3*i-2*j-d)) * fact(2*n-2*i-2*j-2*e)//(fact(e)*fact(d-e)*fact(2*n-2*i-2*j-d-e)*fact(n-i-j-d+e)*pow(fact(n-i-j-e),2)) for e in range(max(0,i+j-n+d), min(d,2*n-2*i-2*j-d)+1)) for d in range(max(0,n-j-2*i), min(n-j,2*n-3*i-2*j)+1)) for i in range(int(2*(n-j)/3)+1)) for j in range(n+1)) print([a(n) for n in range(1,11)])
Formula
a(n) = 3!*(n-1)!*(n!)^3*A369923(n,4). - Andrew Howroyd, Nov 20 2024
a(n) = 2*A381326(n). - Eric W. Weisstein, Feb 20 2025