login
A377586
Numbers of directed Hamiltonian paths in the complete 4-partite graph K_{n,n,n,n}.
2
24, 13824, 53529984, 751480602624, 27917203599360000, 2267561150913576960000, 354252505303682314076160000, 97087054992658680467800719360000, 43551509948777170973522371396239360000, 30293653795894300342540281328749772800000000
OFFSET
1,1
LINKS
L. Q. Eifler, K. B. Reid Jr., and D. P. Roselle, Sequences with adjacent elements unequal, Aequationes Mathematicae 6 (2-3), 1971; see also.
FORMULA
a(n) = 24 * n!^4 * A190918(n).
a(n) = n!^4 * A322093(n,4).
MATHEMATICA
Table[n!^4 * SeriesCoefficient[1/(1 - Sum[x[i]/(1 + x[i]), {i, 1, 4}]), Sequence @@ Table[{x[i], 0, n}, {i, 1, 4}]], {n, 1, 10}]
PROG
(Python)
from math import factorial as fact, comb
from itertools import combinations_with_replacement
def a(n):
# Using modified formula for counting sequences found in Eifler et al.
result = 0
fn = fact(n)
for i, j, k in combinations_with_replacement(range(1, n+1), 3):
patterns = [(3, 0, 0)] if i == j == k else \
[(2, 0, 1)] if i == j != k else \
[(1, 2, 0)] if i != j == k else [(1, 1, 1)]
for a, b, c in patterns:
s = a*i + b*j + c*k
num = fact(3)
den = fact(a) * fact(b) * fact(c)
if a:
for _ in range(a): num, den = num * comb(n-1, i-1), den * fact(i)
if b:
for _ in range(b): num, den = num * comb(n-1, j-1), den * fact(j)
if c:
for _ in range(c): num, den = num * comb(n-1, k-1), den * fact(k)
num *= comb(s + 1, n) * fact(s)
result += (1 if (3*n - s) % 2 == 0 else -1) * (num // den)
for _ in range(4): result *= fn
return result
print([a(n) for n in range(1, 11)]) # Zlatko Damijanic, Nov 18 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Zlatko Damijanic, Nov 02 2024
STATUS
approved