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,1

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.

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

Cf. A190918, A234365, A322013, A322093.

Sequence in context: A338527 A284985 A013729 * A159729 A341801 A028694

Adjacent sequences: A377583 A377584 A377585 * A377587 A377588 A377589

Keyword

nonn

Author

Zlatko Damijanic, Nov 02 2024

Status

approved