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
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
-
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 *)
A370613
Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n into distinct parts.
Original entry on oeis.org
1, 1, 1, 5, 9, 63, 509, 2959, 22453, 247949, 3080991, 28988331, 407320739, 5122243495, 82583577967, 1430027615585, 22556817627789, 395098668828675, 7979894546677853, 154786744386253387, 3355612019167352821, 78865333300205585345, 1769663675666499515751
Offset: 0
-
g:= proc(n) option remember; `if`(n=0, 1, add(
expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
end:
b:= proc(t, n, i) option remember; `if`(i*(i+1)/2 abs(b(0, n$2)):
seq(a(n), n=0..22);
A370614
Triangle T(n,k) in which row n lists in increasing order the number of acyclic orientations of complete multipartite graphs K_lambda, where lambda is a partition of n into distinct parts; triangle T(n,k), n>=0, k = 1..A000009(n), read by rows.
Original entry on oeis.org
1, 1, 1, 1, 4, 1, 8, 1, 16, 46, 1, 32, 146, 330, 1, 64, 454, 1066, 1374, 1, 128, 1394, 4718, 5658, 10554, 1, 256, 4246, 20266, 23118, 41506, 57054, 101502, 1, 512, 12866, 85310, 93930, 237686, 302730, 525642, 657210, 1165104, 1, 1024, 38854, 354106, 380094
Offset: 0
Triangle T(n,k) begins:
1;
1;
1;
1, 4;
1, 8;
1, 16, 46;
1, 32, 146, 330;
1, 64, 454, 1066, 1374;
1, 128, 1394, 4718, 5658, 10554;
1, 256, 4246, 20266, 23118, 41506, 57054, 101502;
...
-
g:= proc(n) option remember; `if`(n=0, 1, add(
expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
end:
h:= 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:
b:= proc(n, i, l) `if`(i*(i+1)/2 sort(b(n$2, [0]))[]:
seq(T(n), n=0..12);
A372395
Total number of acyclic orientations in all complete multipartite graphs K_lambda, where lambda ranges over all partitions of n.
Original entry on oeis.org
1, 1, 3, 11, 65, 411, 3535, 31081, 337185, 3846557, 50329253, 691740489, 10725769171, 172411994899, 3050277039465, 56428854605627, 1124781474310649, 23349607769846667, 518744693882444419, 11949343411110856153, 291921874093876965453, 7395266131906154621501
Offset: 0
-
g:= proc(n) option remember; `if`(n=0, 1, add(
expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
end:
b:= proc(t, n, i) option remember; `if`(n=0, t!*(-1)^t,
`if`(i<1, 0, b(t, n, i-1)+add(coeff(g(i), x, m)*
b(t+m, n-i, min(n-i, i)), m=0..i)))
end:
a:= n-> abs(b(0, n$2)):
seq(a(n), n=0..21);
-
g[n_] := g[n] = If[n == 0, 1, Sum[Expand[x*g[n - j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
b[t_, n_, i_] := b[t, n, i] = If[n == 0, t!*(-1)^t, If[i < 1, 0, b[t, n, i - 1] + Sum[Coefficient[g[i], x, m]*b[t + m, n - i, Min[n - i, i]], {m, 0, i}]]];
a[n_] := Abs[b[0, n, n]];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Jul 24 2024, after Alois P. Heinz *)
A372396
Triangle T(n,k) in which row n lists in increasing order the number of acyclic orientations of complete multipartite graphs K_lambda, where lambda is a partition of n; triangle T(n,k), n>=0, k = 1..A000041(n), read by rows.
Original entry on oeis.org
1, 1, 1, 2, 1, 4, 6, 1, 8, 14, 18, 24, 1, 16, 46, 54, 78, 96, 120, 1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720, 1, 64, 454, 486, 1066, 1374, 1536, 1902, 2286, 2616, 3000, 3216, 3720, 4320, 5040, 1, 128, 1394, 1458, 4718, 5658, 6144, 6902, 10554, 12090
Offset: 0
Triangle T(n,k) begins:
1;
1;
1, 2;
1, 4, 6;
1, 8, 14, 18, 24;
1, 16, 46, 54, 78, 96, 120;
1, 32, 146, 162, 230, 330, 384, 426, 504, 600, 720;
...
-
g:= proc(n) option remember; `if`(n=0, 1, add(
expand(x*g(n-j))*binomial(n-1, j-1), j=1..n))
end:
h:= 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:
b:= proc(n, i, l) `if`(n=0 or i=1, [h([l[], 1$n, 0])],
[b(n-i, min(n-i, i), [l[], i])[], b(n, i-1, l)[]])
end:
T:= n-> sort(b(n$2, []))[]:
seq(T(n), n=0..10);
Showing 1-5 of 5 results.
Comments