A212220 -id:A212220 - cp's OEIS frontend

A370961 a(n) = number of acyclic orientations of the complete tripartite graph K_{n,n,n}.

1, 6, 426, 122190, 90768378, 138779942046, 379578822373866, 1689637343582548590, 11434884125767376107098, 111765072808554847704145086, 1515592947854931941485836600906, 27609710924806869786487193747541390, 658043992934027491354757341987635993018

Offset: 0

N. J. A. Sloane, Apr 04 2024

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..155 (terms n = 1..16 from Don Knuth)
Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024. See (19.2).

Cf. A212220, A266858, A267383, A370960.
Main diagonal of A372254.
Row n=3 of A372326.

a(n) = A266858(3n) = A267383(3n,3). - Alois P. Heinz, Apr 17 2024

a(n) = Sum_{k=0..3n} (-1)^k * A212220(n,k). - Alois P. Heinz, May 02 2024

More terms from Don Knuth, Apr 07 2024

a(0)=1 prepended by Alois P. Heinz, Apr 17 2024

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.

Original entry on oeis.org

1, 1, 2, 1, 6, 14, 1, 18, 78, 230, 1, 54, 426, 1902, 6902, 1, 162, 2286, 15402, 76110, 329462, 1, 486, 12090, 122190, 822954, 4553166, 22934774, 1, 1458, 63198, 951546, 8724078, 61796298, 381523758, 2193664790, 1, 4374, 327306, 7290942, 90768378, 823457454, 6241779786, 42700751022, 276054834902

Offset: 0

Alois P. Heinz, Apr 24 2024

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.

			Square array A(n,k) begins:
       1,       1,        1,         1,           1,            1, ...
       2,       6,       18,        54,         162,          486, ...
      14,      78,      426,      2286,       12090,        63198, ...
     230,    1902,    15402,    122190,      951546,      7290942, ...
    6902,   76110,   822954,   8724078,    90768378,    928340190, ...
  329462, 4553166, 61796298, 823457454, 10779805722, 138779942046, ...

Alois P. Heinz, Rows n = 0..140, flattened
Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024. See (19.2).
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Multipartite graph

Rows n=0-2 give: A000012, A008776, A370960.
Column k=0 gives A048163(n+1).
Main diagonal gives A370961.
Cf. A212220, A267383, A372261.

g:= proc(n) option remember; `if`(n=0, 1, add(
      expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
    end:
A:= proc(n, k) option remember; local q, l, b; q, l, b:= -1, [n$2, k],
      proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
        (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
      end; abs(b(0, 3))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..9);

g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n-j]]*Binomial[n-1, j-1], {j, 1, n}]];
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]]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 9}] // Flatten (* Jean-François Alcover, Apr 25 2024, after Alois P. Heinz *)

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.

Original entry on oeis.org

1, 1, 2, 6, 1, 4, 18, 14, 78, 426, 1, 8, 54, 46, 330, 2286, 230, 1902, 15402, 122190, 1, 16, 162, 146, 1374, 12090, 1066, 10554, 101502, 951546, 6902, 76110, 822954, 8724078, 90768378, 1, 32, 486, 454, 5658, 63198, 4718, 57054, 657210, 7290942, 41506, 525642, 6495534, 78463434, 928340190

Offset: 0

Alois P. Heinz, Apr 24 2024

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.

			Triangle of triangles T(n,k,j) begins:
    1;
  ;
    1;
    2,    6;
  ;
    1;
    4,   18;
   14,   78,   426;
  ;
    1;
    8,   54;
   46,  330,  2286;
  230, 1902, 15402, 122190;
  ;
  ...

Alois P. Heinz, Rows n = 0..40, flattened
Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024. See (19.2).
Richard P. Stanley, Acyclic Orientations of Graphs, Discrete Mathematics, 5 (1973), pages 171-178, doi:10.1016/0012-365X(73)90108-8
Wikipedia, Acyclic orientation
Wikipedia, Multipartite graph

T(n,k,0) for k=0..9 give: A000012, A000079, A027649, A027650, A027651, A283811, A283812, A283813, A284032, A284033.
T(n,n,n) gives A370961.
T(n,n,0) gives A048163(n+1).
T(n+1,n,0) gives A188634(n+1).
T(n,1,1) gives A008776.
T(n,2,2) gives A370960.
Cf. A099594, A212220, A267383, A372254.

g:= proc(n) option remember; `if`(n=0, 1, add(
      expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
    end:
T:= proc() option remember; local q, l, b; q, l, b:= -1, [args],
      proc(n, j) option remember; `if`(j=1, mul(q-i, i=0..n-1)*
        (q-n)^l[1], add(b(n+m, j-1)*coeff(g(l[j]), x, m), m=0..l[j]))
      end; abs(b(0, nops(l)))
    end:
seq(seq(seq(T(n, k, j), j=0..k), k=0..n), n=0..5);

g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
T[n_, k_, j_] := T[n, k, j] = Module[{q = -1, l = {n, k, j}, b},
   b[n0_, j0_] := b[n0, j0] = If[j0 == 1, Product[q - i, {i, 0, n0 - 1}]*
   (q - n0)^n, Sum[b[n0 + m, j0 - 1]*Coefficient[g[l[[j0]]], x, m],
   {m, 0, l[[j0]]}]];
Abs[b[0, 3]]];
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 *)

A266858 Number of acyclic orientations of the Turán graph T(n,3).

Original entry on oeis.org

1, 1, 2, 6, 18, 78, 426, 2286, 15402, 122190, 951546, 8724078, 90768378, 928340190, 10779805722, 138779942046, 1759271695338, 24739709631678, 379578822373866, 5743346972756526, 94864142045862282, 1689637343582548590, 29717468115957434586, 563879701735681033998

Offset: 0

Alois P. Heinz, Jan 04 2016

nonn

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.

Alois P. Heinz, Table of n, a(n) for n = 0..465
P. J. Cameron, C. A. Glass, R. U. Schumacher, Acyclic orientations and poly-Bernoulli numbers, arXiv:1412.3685 [math.CO], 2014-2018.
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

Column k=3 of A267383.
Cf. A182553, A212220, A266695.
Trisection gives A370961.

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]]];
a[n_] := A[n, 3];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Aug 20 2018, after Alois P. Heinz *)

a(n) ~ n! / (2*(1 - log(3/2)) * 3^n * (log(3/2))^(n+1)). - Vaclav Kotesovec, Feb 18 2017

A212221 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is 1/(2*n) times the number of n-colorings of the complete tripartite graph K_(k,k,k).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 1, 3, 0, 0, 1, 12, 6, 0, 0, 1, 30, 78, 10, 0, 0, 1, 66, 474, 340, 15, 0, 0, 1, 138, 2238, 4780, 1095, 21, 0, 0, 1, 282, 9546, 46420, 32955, 2856, 28, 0, 0, 1, 570, 38958, 385660, 617775, 168546, 6412, 36

Offset: 1

Alois P. Heinz, May 06 2012

The complete tripartite graph K_(n,n,n) has 3*n vertices and 3*n^2 = A033428(n) edges; see A212220 for example. The chromatic polynomial of K_(n,n,n) has 3*n+1 = A016777(n) coefficients.

			Square array A(n,k) begins:
   0,    0,     0,      0,       0,         0,          0, ...
   0,    0,     0,      0,       0,         0,          0, ...
   1,    1,     1,      1,       1,         1,          1, ...
   3,   12,    30,     66,     138,       282,        570, ...
   6,   78,   474,   2238,    9546,     38958,     155994, ...
  10,  340,  4780,  46420,  385660,   2995540,   22666780, ...
  15, 1095, 32955, 617775, 9248595, 123920295, 1569542955, ...

Alois P. Heinz, Antidiagonals n = 1..100, flattened
Eric Weisstein's World of Mathematics, Complete Tripartite Graph
Wikipedia, Chromatic Polynomial

Rows 1+2,3-4 give: A000004, A000012, A089143(n-1) = 1/2*A182464(n-2) = 1/3*A182467(n-2).
Columns 1-2 give: A000217(n-2), 1/(2*n)*A115400(n).
Cf. A008277, A016777, A033428, A212220, A282247.

P:= proc(n) option remember;
      unapply(expand(add(add(Stirling2(n, k) *Stirling2(n, m)
       *mul(q-i, i=0..k+m-1) *(q-k-m)^n, m=1..n), k=1..n)), q)
    end:
A:= (n, k)-> P(k)(n)/(2*n):
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);

p[n_] := p[n] = Function[q, Expand[Sum[Sum[StirlingS2[n, k] * StirlingS2[n, m] * Product[q-i, {i, 0, k+m-1}]*(q-k-m)^n, {m, 1, n}], {k, 1, n}]]]; a[n_, k_] := p[k][n]/(2*n); Table[Table[a[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

A(n,k) = 1/(2*n) * Sum_{j,m=1..k} S2(k,j) * S2(k,m) * (n-j-m)^k * Product_{i=0..j+m-1} (n-i) with S2 = A008277.

A(n,n) = A282247(n).

cp's OEIS Frontend

A370961 a(n) = number of acyclic orientations of the complete tripartite graph K_{n,n,n}.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A266858 Number of acyclic orientations of the Turán graph T(n,3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A212221 Square array A(n,k), n>=1, k>=1, read by antidiagonals: A(n,k) is 1/(2*n) times the number of n-colorings of the complete tripartite graph K_(k,k,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula