|
| |
|
|
A267383
|
|
Number A(n,k) of acyclic orientations of the Turán graph T(n,k); square array A(n,k), n>=0, k>=1, read by antidiagonals.
|
|
12
|
|
|
|
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 2, 6, 14, 1, 1, 1, 2, 6, 18, 46, 1, 1, 1, 2, 6, 24, 78, 230, 1, 1, 1, 2, 6, 24, 96, 426, 1066, 1, 1, 1, 2, 6, 24, 120, 504, 2286, 6902, 1, 1, 1, 2, 6, 24, 120, 600, 3216, 15402, 41506, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,9
|
|
|
COMMENTS
|
An acyclic orientation is an assignment of a direction to each edge such that no cycle in the graph is consistently oriented. Stanley showed that the number of acyclic orientations of a graph G is equal to the absolute value of the chromatic polynomial X_G(q) evaluated at q=-1.
Conjecture: In general, column k > 1 is asymptotic to n! / ((k-1) * (1 - log(k/(k-1)))^((k-1)/2) * k^n * (log(k/(k-1)))^(n+1)). - Vaclav Kotesovec, Feb 18 2017
|
|
|
LINKS
|
Alois P. Heinz, Antidiagonals n = 0..140, flattened
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Turán graph
|
|
|
EXAMPLE
|
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, ...
1, 2, 2, 2, 2, 2, 2, ...
1, 4, 6, 6, 6, 6, 6, ...
1, 14, 18, 24, 24, 24, 24, ...
1, 46, 78, 96, 120, 120, 120, ...
1, 230, 426, 504, 600, 720, 720, ...
1, 1066, 2286, 3216, 3720, 4320, 5040, ...
|
|
|
MAPLE
|
A:= proc(n, k) option remember; local b, l, q; q:=-1;
l:= [floor(n/k)$(k-irem(n, k)), ceil(n/k)$irem(n, k)];
b:= proc(n, j) option remember; `if`(j=1, (q-n)^l[1]*
mul(q-i, i=0..n-1), add(b(n+m, j-1)*
Stirling2(l[j], m), m=0..l[j]))
end; forget(b);
abs(b(0, k))
end:
seq(seq(A(n, 1+d-n), n=0..d), d=0..14);
|
|
|
MATHEMATICA
|
A[n_, k_] := A[n, k] = Module[{ b, l, q}, q = -1; l = Join[Array[Floor[n/k] &, k - Mod[n, k]], Array[ Ceiling[n/k] &, Mod[n, k]]]; b[nn_, j_] := b[nn, j] = If[j == 1, (q - nn)^l[[1]]*Product[q - i, {i, 0, nn - 1}], Sum[b[nn + m, j - 1]*StirlingS2[l[[j]], m], {m, 0, l[[j]]}]]; Abs[b[0, k]]]; Table[Table[A[n, 1 + d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)
|
|
|
CROSSREFS
|
Columns k=1-10 give: A000012, A266695, A266858, A267384, A267385, A267386, A267387, A267388, A267389, A267390.
Main diagonal gives A000142.
A(2n,n) gives A033815.
A(n,ceiling(n/2)) gives A161132.
Sequence in context: A287214 A287216 A145515 * A332648 A272896 A188919
Adjacent sequences: A267380 A267381 A267382 * A267384 A267385 A267386
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Alois P. Heinz, Jan 13 2016
|
|
|
STATUS
|
approved
|
| |
|
|
