|
%I #30 May 02 2024 16:46:33
%S 1,1,2,6,1,4,18,14,78,426,1,8,54,46,330,2286,230,1902,15402,122190,1,
%T 16,162,146,1374,12090,1066,10554,101502,951546,6902,76110,822954,
%U 8724078,90768378,1,32,486,454,5658,63198,4718,57054,657210,7290942,41506,525642,6495534,78463434,928340190
%N Number T(n,k,j) of acyclic orientations of the complete tripartite graph K_{n,k,j}; triangle of triangles T(n,k,j), n>=0, k=0..n, j=0..k, read by rows.
%C 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.
%H Alois P. Heinz, <a href="/A372261/b372261.txt">Rows n = 0..40, flattened</a>
%H Don Knuth, <a href="http://cs.stanford.edu/~knuth/papers/poly-Bernoulli.pdf">Parades and poly-Bernoulli bijections</a>, Mar 31 2024. See (19.2).
%H Richard P. Stanley, <a href="http://dx.doi.org/10.1016/0012-365X(73)90108-8">Acyclic Orientations of Graphs</a>, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Multipartite graph</a>
%e Triangle of triangles T(n,k,j) begins:
%e 1;
%e ;
%e 1;
%e 2, 6;
%e ;
%e 1;
%e 4, 18;
%e 14, 78, 426;
%e ;
%e 1;
%e 8, 54;
%e 46, 330, 2286;
%e 230, 1902, 15402, 122190;
%e ;
%e ...
%p g:= proc(n) option remember; `if`(n=0, 1, add(
%p expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
%p end:
%p T:= proc() option remember; local q, l, b; q, l, b:= -1, [args],
%p proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
%p (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
%p end; abs(b(0, nops(l)))
%p end:
%p seq(seq(seq(T(n, k, j), j=0..k), k=0..n), n=0..5);
%Y T(n,k,0) for k=0..9 give: A000012, A000079, A027649, A027650, A027651, A283811, A283812, A283813, A284032, A284033.
%Y T(n,n,n) gives A370961.
%Y T(n,n,0) gives A048163(n+1).
%Y T(n+1,n,0) gives A188634(n+1).
%Y T(n,1,1) gives A008776.
%Y T(n,2,2) gives A370960.
%Y Cf. A099594, A212220, A267383, A372254.
%K nonn,look,tabf,new
%O 0,3
%A _Alois P. Heinz_, Apr 24 2024
|
