A370961 -id:A370961 - cp's OEIS frontend

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.

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

Offset: 0

Alois P. Heinz, Jan 13 2016

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

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

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, Acyclic orientation
Wikipedia, Turán graph

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.
Bisection of column k=2 gives A048163.
Trisection of column k=3 gives A370961.
a(n^2,n) gives A372084.

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);

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 *)

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 *)

A372326 Number A(n,k) of acyclic orientations of the Turán graph T(k*n,n); square array A(n,k), n>=0, k>=1, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 14, 6, 1, 1, 1, 230, 426, 24, 1, 1, 1, 6902, 122190, 24024, 120, 1, 1, 1, 329462, 90768378, 165392664, 2170680, 720, 1, 1, 1, 22934774, 138779942046, 4154515368024, 457907248920, 287250480, 5040, 1

Offset: 0

Alois P. Heinz, Apr 27 2024

The Turán graph T(k*n,n) is the complete n-partite graph K_{k,...,k}.

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,   1,       1,            1,                  1, ...
  1,   2,      14,          230,               6902, ...
  1,   6,     426,       122190,           90768378, ...
  1,  24,   24024,    165392664,      4154515368024, ...
  1, 120, 2170680, 457907248920, 495810323060597880, ...

Alois P. Heinz, Antidiagonals n = 0..42, flattened
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
Wikipedia, Turán graph

Columns k=0-2 give: A000012, A000142, A033815.
Rows n=0+1,2-3 give: A000012, A048163(k+1), A370961.
Main diagonal gives A372084.
Cf. A267383.

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, [k$n, 0],
      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(A(n, d-n), n=0..d), d=0..10);

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 = -1, l, b}, l = Append[Table[k, {n}], 0];
   b[nn_, j_] := b[nn, j] = If[j == 1, Product[q - i, {i, 0, nn - 1}]*
   (q - nn)^l[[1]], Sum[b[nn + m, j - 1]*Coefficient[g[l[[j]]], x, m],
   {m, 0, l[[j]]}]];
   Abs[b[0, Length[l]]]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jun 09 2024, after Alois P. Heinz *)

A(n,k) = A267383(k*n,n).

A212220 Triangle T(n,k), n>=0, 0<=k<=3n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete tripartite graph K_(n,n,n), highest powers first.

Original entry on oeis.org

1, 1, -3, 2, 0, 1, -12, 58, -137, 154, -64, 0, 1, -27, 324, -2223, 9414, -24879, 39528, -33966, 11828, 0, 1, -48, 1064, -14244, 126936, -784788, 3409590, -10329081, 21197804, -27779384, 20648794, -6476644, 0, 1, -75, 2650, -58100, 878200, -9632440, 78681510

Offset: 0

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. The chromatic polynomial of K_(n,n,n) has 3*n+1 = A016777(n) coefficients.

			2 example graphs:             +-------------+
.                             | +-------+   |
.                             +-o---o---o   |
.                                \ / \ / \ /
.                                 X   X   X
.                                / \ / \ / \
.              o---o---o      +-o---o---o   |
.              +-------+      | +-------+   |
.                             +-------------+
Graph:         K_(1,1,1)        K_(2,2,2)
Vertices:          3                6
Edges:             3               12
The complete tripartite graph K_(1,1,1) is the cycle graph C_3 with chromatic polynomial q*(q-1)*(q-2) = q^3 -3*q^2 +2*q => [1, -3, 2, 0].
Triangle T(n,k) begins:
  1;
  1,   -3,    2,       0;
  1,  -12,   58,    -137,     154,       -64,         0;
  1,  -27,  324,   -2223,    9414,    -24879,     39528, ...
  1,  -48, 1064,  -14244,  126936,   -784788,   3409590, ...
  1,  -75, 2650,  -58100,  878200,  -9632440,  78681510, ...
  1, -108, 5562, -180585, 4123350, -70008186, 912054348, ...
  ...

Alois P. Heinz, Rows n = 0..58, flattened
Anatol N. Kirillov, On some quadratic algebras. I 1/2: Combinatorics of Dunkl and Gaudin elements, Schubert, Grothendieck, Fuss-Catalan, universal Tutte and reduced polynomials, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 002, 172 p. (2016).
Eric Weisstein's World of Mathematics, Complete Tripartite Graph
Wikipedia, Acyclic orientation
Wikipedia, Chromatic Polynomial
Wikipedia, Multipartite graph

Columns k=0-1 give: A000012, (-1)*A033428.
Row sums and last elements of rows give: A000007.
Row lengths give: A016777.
Cf. A008277, A182553, A212221, A370961.

P:= proc(n) option remember;
       expand(add(add(Stirling2(n, k) *Stirling2(n, m)
       *mul(q-i, i=0..k+m-1) *(q-k-m)^n, m=0..n), k=0..n))
    end:
T:= n-> seq(coeff(P(n), q, 3*n-k), k=0..3*n):
seq(T(n), n=0..6);

P[n_] := P[n] = 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}]];
T[n_] := Table[Coefficient[P[n], q, 3*n - k], {k, 0, 3*n}];
Array[T, 6] // Flatten (* Jean-François Alcover, May 29 2018, from Maple *)

T(n,k) = [q^(3*n-k)] Sum_{k,m=0..n} S2(n,k) * S2(n,m) * (q-k-m)^n * Product_{i=0..k+m-1} (q-i) with S2 = A008277.

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

T(0,0)=1 prepended by Alois P. Heinz, May 02 2024

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

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

Original entry on oeis.org

14, 78, 426, 2286, 12090, 63198, 327306, 1682766, 8601690, 43768638, 221910186, 1121897646, 5659111290, 28494757278, 143272715466, 719565670926, 3610655860890, 18104646725118, 90728875495146, 454467461514606, 2275631193410490, 11391336159448158, 57009415513961226, 285258058278100686, 1427134339747920090

Offset: 0

N. J. A. Sloane, Apr 04 2024

nonn

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

Cf. A370961.

Row n=2 of A372254.

Further terms from Don Knuth, Apr 07 2024

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

A372326 Number A(n,k) of acyclic orientations of the Turán graph T(k*n,n); square array A(n,k), n>=0, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212220 Triangle T(n,k), n>=0, 0<=k<=3n, read by rows: row n gives the coefficients of the chromatic polynomial of the complete tripartite graph K_(n,n,n), highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

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

Views

Author

Keywords

Links

Crossrefs

Extensions