|
|
A054653
|
|
Number of acyclic orientations of the Hamming graph (K_3) x (K_n).
|
|
1
|
|
|
1, 6, 204, 19164, 3733056, 1288391040, 712770186240, 589563294888960, 692610802412175360, 1110893919113884631040, 2357555468242103997235200, 6453187419589244410090291200, 22305345996450386267133758668800
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
This number is equivalent to the number of plans (i.e. structural solutions) of the open shop problem with n jobs and 3 machines - see problems in scheduling theory.
|
|
REFERENCES
|
M. Harborth, Structural analysis of shop scheduling problems, PhD thesis, Otto-von-Guericke-Univ. Magdeburg, GCA-Verlag, 1999 (in German)
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (-1)^n*(z!n!/(((z-n)!)^3)*Sum[If[a+b+c*n, (-1)^b*2^c*((z-n+a)!)^2/(a!c!) *Binomial[3z-3n+3a+b+2, b], 0], {c, 0, n}, {b, 0, n}, {a, 0, n}]) with z=-1.
|
|
MATHEMATICA
|
Table[n!*Evaluate[(-1)^n*FunctionExpand[z!n!/(((z-n)!)^3)*Sum[If[a+b+c*n, (-1 )^b*2^c*((z-n+a)!)^2/(a!c!)*Binomial[3z-3n+3a+b+2, b], 0], {c, 0, n}, {b, 0, n}, {a, 0, n}]]/.z->-1]/n!, {n, 0, 15}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
M. Harborth (Martin.Harborth(AT)vt.siemens.de)
|
|
STATUS
|
approved
|
|
|
|