A377586 Numbers of directed Hamiltonian paths in the complete 4-partite graph K_{n,n,n,n}.

24, 13824, 53529984, 751480602624, 27917203599360000, 2267561150913576960000, 354252505303682314076160000, 97087054992658680467800719360000, 43551509948777170973522371396239360000, 30293653795894300342540281328749772800000000

Offset: 1

Author

Zlatko Damijanic, Nov 02 2024

Keywords

• nonn

Links

• Zlatko Damijanic, Table of n, a(n) for n = 1..117
• L. Q. Eifler, K. B. Reid Jr., and D. P. Roselle, Sequences with adjacent elements unequal, Aequationes Mathematicae 6 (2-3), 1971; see also.

Crossrefs

Cf. A190918, A234365, A322013, A322093.

Programs

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}]

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

Formula

a(n) = 24 * n!^4 * A190918(n).

a(n) = n!^4 * A322093(n,4).