cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A372254 Number A(n,k) of acyclic orientations of the complete tripartite graph K_{n,n,k}; square array A(n,k), n>=0, k>=0, read by antidiagonals.

This page as a plain text file.
%I A372254 #29 May 02 2024 16:53:42
%S A372254 1,1,2,1,6,14,1,18,78,230,1,54,426,1902,6902,1,162,2286,15402,76110,
%T A372254 329462,1,486,12090,122190,822954,4553166,22934774,1,1458,63198,
%U A372254 951546,8724078,61796298,381523758,2193664790,1,4374,327306,7290942,90768378,823457454,6241779786,42700751022,276054834902
%N A372254 Number A(n,k) of acyclic orientations of the complete tripartite graph K_{n,n,k}; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%C A372254 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 A372254 Alois P. Heinz, <a href="/A372254/b372254.txt">Rows n = 0..140, flattened</a>
%H A372254 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 A372254 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 A372254 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%H A372254 Wikipedia, <a href="https://en.wikipedia.org/wiki/Multipartite_graph">Multipartite graph</a>
%e A372254 Square array A(n,k) begins:
%e A372254        1,       1,        1,         1,           1,            1, ...
%e A372254        2,       6,       18,        54,         162,          486, ...
%e A372254       14,      78,      426,      2286,       12090,        63198, ...
%e A372254      230,    1902,    15402,    122190,      951546,      7290942, ...
%e A372254     6902,   76110,   822954,   8724078,    90768378,    928340190, ...
%e A372254   329462, 4553166, 61796298, 823457454, 10779805722, 138779942046, ...
%p A372254 g:= proc(n) option remember; `if`(n=0, 1, add(
%p A372254       expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
%p A372254     end:
%p A372254 A:= proc(n, k) option remember; local q, l, b; q, l, b:= -1, [n$2, k],
%p A372254       proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
%p A372254         (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
%p A372254       end; abs(b(0, 3))
%p A372254     end:
%p A372254 seq(seq(A(n, d-n), n=0..d), d=0..9);
%t A372254 g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n-j]]*Binomial[n-1, j-1], {j, 1, n}]];
%t A372254 A[n_, k_] := A[n, k] = Module[{q, l, b}, {q, l} = {-1, {n, n, k}}; b[n0_, j_] := b[n0, j] = If[j == 1, Product[q-i, {i, 0, n0-1}]*(q-n0)^l[[1]], Sum[b[n0 + m, j-1]*Coefficient[g[l[[j]]], x, m], {m, 0, l[[j]]}]]; Abs[b[0, 3]]];
%t A372254 Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 9}] // Flatten (* _Jean-François Alcover_, Apr 25 2024, after _Alois P. Heinz_ *)
%Y A372254 Rows n=0-2 give: A000012, A008776, A370960.
%Y A372254 Column k=0 gives A048163(n+1).
%Y A372254 Main diagonal gives A370961.
%Y A372254 Cf. A212220, A267383, A372261.
%K A372254 nonn,tabl
%O A372254 0,3
%A A372254 _Alois P. Heinz_, Apr 24 2024