cp's OEIS Frontend

A372261 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.

%I A372261 #34 Jun 14 2024 12:17:14
%S A372261 1,1,2,6,1,4,18,14,78,426,1,8,54,46,330,2286,230,1902,15402,122190,1,
%T A372261 16,162,146,1374,12090,1066,10554,101502,951546,6902,76110,822954,
%U A372261 8724078,90768378,1,32,486,454,5658,63198,4718,57054,657210,7290942,41506,525642,6495534,78463434,928340190
%N A372261 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 A372261 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 A372261 Alois P. Heinz, <a href="/A372261/b372261.txt">Rows n = 0..40, flattened</a>
%H A372261 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 A372261 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 A372261 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H A372261 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Multipartite graph</a>
%e A372261 Triangle of triangles T(n,k,j) begins:
%e A372261     1;
%e A372261   ;
%e A372261     1;
%e A372261     2,    6;
%e A372261   ;
%e A372261     1;
%e A372261     4,   18;
%e A372261    14,   78,   426;
%e A372261   ;
%e A372261     1;
%e A372261     8,   54;
%e A372261    46,  330,  2286;
%e A372261   230, 1902, 15402, 122190;
%e A372261   ;
%e A372261   ...
%p A372261 g:= proc(n) option remember; `if`(n=0, 1, add(
%p A372261       expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
%p A372261     end:
%p A372261 T:= proc() option remember; local q, l, b; q, l, b:= -1, [args],
%p A372261       proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
%p A372261         (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
%p A372261       end; abs(b(0, nops(l)))
%p A372261     end:
%p A372261 seq(seq(seq(T(n, k, j), j=0..k), k=0..n), n=0..5);
%t A372261 g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
%t A372261 T[n_, k_, j_] := T[n, k, j] = Module[{q = -1, l = {n, k, j}, b},
%t A372261    b[n0_, j0_] := b[n0, j0] = If[j0 == 1, Product[q - i, {i, 0, n0 - 1}]*
%t A372261    (q - n0)^n, Sum[b[n0 + m, j0 - 1]*Coefficient[g[l[[j0]]], x, m],
%t A372261    {m, 0, l[[j0]]}]];
%t A372261 Abs[b[0, 3]]];
%t A372261 Table[Table[Table[T[n, k, j], {j, 0, k}], {k, 0, n}], {n, 0, 5}] // Flatten (* _Jean-François Alcover_, Jun 14 2024, after _Alois P. Heinz_ *)
%Y A372261 T(n,k,0) for k=0..9 give: A000012, A000079, A027649, A027650, A027651, A283811, A283812, A283813, A284032, A284033.
%Y A372261 T(n,n,n) gives A370961.
%Y A372261 T(n,n,0) gives A048163(n+1).
%Y A372261 T(n+1,n,0) gives A188634(n+1).
%Y A372261 T(n,1,1) gives A008776.
%Y A372261 T(n,2,2) gives A370960.
%Y A372261 Cf. A099594, A212220, A267383, A372254.
%K A372261 nonn,look,tabf
%O A372261 0,3
%A A372261 _Alois P. Heinz_, Apr 24 2024